incomparabilities

Incomparabilities refer to pairs of elements in a partially ordered set (poset) that are not comparable under the given order. Specifically, elements x and y are incomparable if neither x ≤ y nor y ≤ x holds. If every pair of distinct elements in a poset is comparable, the poset is a total (or linear) order and there are no incomparabilities.

Key properties include that incomparability is symmetric and irreflexive, but not transitive: x and y may be incomparable while y and z are incomparable, yet x and z could be comparable or incomparable. Incomparability is central to the study of structure within posets and relates to notions such as chains and antichains.

Antichains are sets in which every pair of elements is incomparable. The size of the largest antichain in a poset is called its width. Dilworth’s theorem connects width to the minimum number of chains needed to cover the poset. The concept of incomparability also leads to the incomparability graph: a graph whose vertices are the elements of the poset and whose edges connect pairs of incomparable elements. Its complement is the comparability graph, which connects pairs that are comparable.

Common examples include the divisibility poset, where two numbers are incomparable if neither divides the other, and the subset lattice of a finite set, where two subsets are incomparable if neither is contained in the other. In Boolean lattices, Sperner’s theorem describes the maximal size of an antichain.

While incomparability is a natural feature of many posets, the existence of joins (least upper bounds) or meets (greatest lower bounds) for incomparable elements depends on the specific poset and is not implied by incomparability alone.