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.

A binary relation on a set

is by definition any subset

is said to be related to

-comparable, or comparable (with respect to

Often, a symbol indicating comparison, such as

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 comparability relation induced by

is defined to be the set of all pairs

is comparable to

Similarly, the incomparability relation on

is defined to be the set of all pairs

then comparability with respect to

is sometimes denoted by the symbol

, and incomparability by the symbol

of a partially ordered set, exactly one of

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.

Both of the relations comparability and incomparability are symmetric, that is

and likewise for incomparability.

The comparability graph of a partially ordered set

has as vertices the elements of

and has as edges precisely those pairs

[2] When classifying mathematical objects (e.g., topological spaces), two criteria 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.