Comparability Explained

See also: Comparison (mathematics). 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

P is by definition any subset R of P x P. Given x, y \in P, x R y is written if and only if (x, y) \in R, in which case x is said to be to y by R. An element x \in P is said to be , or , to an element y \in P if x R y or y R x. Often, a symbol indicating comparison, such as < (or \leq, >, \geq, and many others) is used instead of R, in which case x < y is written in place of x R y, which is why the term "comparable" is used.

Comparability with respect to

R induces a canonical binary relation on P ; specifically, the induced by R is defined to be the set of all pairs (x, y) \in P x P such that x is comparable to y ; that is, such that at least one of x R y and y R x is true. Similarly, the on P induced by R is defined to be the set of all pairs (x, y) \in P x P such that x is incomparable to y; that is, such that neither x R y nor y R x is true.

If the symbol

< is used in place of \leq then comparability with respect to < is sometimes denoted by the symbol \overset{<}{\underset{>}{ = }} , and incomparability by the symbol \cancel{\overset{<}{\underset{>}{ = }}} .Thus, for any two elements x and y of a partially ordered set, exactly one of x \overset{<}{\underset{>}{ = }} y and x \cancel{\overset{<}{\underset{>}{ = }}}y 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

x is comparable to y if and only if y is comparable to x, and likewise for incomparability.

Comparability graphs

See main article: article and Comparability graph. The comparability graph of a partially ordered set

P has as vertices the elements of P and has as edges precisely those pairs \{ x, y \} of elements for which x \overset{<}{\underset{>}{ = }} y .^[1]

Classification

When classifying mathematical objects (e.g., topological spaces), 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 T₁ and T₂ criteria are comparable, while the T₁ and sobriety criteria are not.

See also

• , a partial ordering in which incomparability is a transitive relation

External links

• Web site: PlanetMath: partial order. 6 April 2010. 11 July 2012. https://web.archive.org/web/20120711031419/http://planetmath.org/encyclopedia/PartialOrder.html. dead.

Notes and References

1. .