Comparability


In mathematics, two elements x and y of a set P are said to be comparable with respect to a binary relation ≤ if at least one of x ≤ y or y ≤ x is true. They are called incomparable if they are not comparable.

Rigorous definition

A binary relation on a set is by definition any subset of Given is written if and only if in which case is said to be ' to by
An element is said to be ', or ', to an element if or
Often, a symbol indicating comparison, such as is used instead of in which case is written in place of which is why the term "comparable" is used.
Comparability with respect to induces a canonical binary relation on ; specifically, the ' induced by is defined to be the set of all pairs such that is comparable to ; that is, such that at least one of and is true.
Similarly, the on induced by is defined to be the set of all pairs such that is incomparable to that is, such that neither nor is true.
If the symbol is used in place of then comparability with respect to is sometimes denoted by the symbol, and incomparability by the symbol.
Thus, for any two elements and of a partially ordered set, exactly one of and is true.

Example

A totally ordered set is a partially ordered set in which any two elements are comparable. The Szpilrajn extension theorem states that every partial order is contained in a total order. Intuitively, the theorem says that any method of comparing elements that leaves some pairs incomparable can be extended in such a way that every pair becomes comparable.

Properties

Both of the relations and are symmetric, that is is comparable to if and only if is comparable to and likewise for incomparability.

Comparability graphs

The comparability graph of a partially ordered set has as vertices the elements of and has as edges precisely those pairs of elements for which.

Classification

When classifying mathematical objects, two are said to be comparable when the objects that obey one criterion constitute a subset of the objects that obey the other, which is to say when they are comparable under the partial order ⊂. For example, the T1 and T2 criteria are comparable, while the T1 and sobriety criteria are not.