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.

See also: Comparison (mathematics)

Hasse diagram of the natural numbers, partially ordered by "x≤y if x divides y". The numbers 4 and 6 are incomparable, since neither divides the other.

Rigorous definition

A binary relation on a set ${\displaystyle P}$ is by definition any subset ${\displaystyle R}$ of ${\displaystyle P\times P.}$ Given ${\displaystyle x,y\in P,}$ ${\displaystyle xRy}$ is written if and only if ${\displaystyle (x,y)\in R,}$ in which case ${\displaystyle x}$ is said to be related to ${\displaystyle y}$ by ${\displaystyle R.}$ An element ${\displaystyle x\in P}$ is said to be ${\displaystyle R}$-comparable, or comparable (with respect to ${\displaystyle R}$), to an element ${\displaystyle y\in P}$ if ${\displaystyle xRy}$ or ${\displaystyle yRx.}$ Often, a symbol indicating comparison, such as ${\displaystyle \,<\,}$ (or ${\displaystyle \,\leq \,,}$ ${\displaystyle \,>,\,}$ ${\displaystyle \geq ,}$ and many others) is used instead of ${\displaystyle R,}$ in which case ${\displaystyle x<y}$ is written in place of ${\displaystyle xRy,}$ which is why the term "comparable" is used.

Comparability with respect to ${\displaystyle R}$ induces a canonical binary relation on ${\displaystyle P}$; specifically, the comparability relation induced by ${\displaystyle R}$ is defined to be the set of all pairs ${\displaystyle (x,y)\in P\times P}$ such that ${\displaystyle x}$ is comparable to ${\displaystyle y}$; that is, such that at least one of ${\displaystyle xRy}$ and ${\displaystyle yRx}$ is true. Similarly, the incomparability relation on ${\displaystyle P}$ induced by ${\displaystyle R}$ is defined to be the set of all pairs ${\displaystyle (x,y)\in P\times P}$ such that ${\displaystyle x}$ is incomparable to ${\displaystyle y;}$ that is, such that neither ${\displaystyle xRy}$ nor ${\displaystyle yRx}$ is true.

If the symbol ${\displaystyle \,<\,}$ is used in place of ${\displaystyle \,\leq \,}$ then comparability with respect to ${\displaystyle \,<\,}$ is sometimes denoted by the symbol ${\displaystyle {\overset {<}{\underset {>}{=}}}}$, and incomparability by the symbol ${\displaystyle {\cancel {\overset {<}{\underset {>}{=}}}}\!}$.^[1] Thus, for any two elements ${\displaystyle x}$ and ${\displaystyle y}$ of a partially ordered set, exactly one of ${\displaystyle x\ {\overset {<}{\underset {>}{=}}}\ y}$ and ${\displaystyle 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 comparability and incomparability are symmetric, that is ${\displaystyle x}$ is comparable to ${\displaystyle y}$ if and only if ${\displaystyle y}$ is comparable to ${\displaystyle x,}$ and likewise for incomparability.

Comparability graphs

Main article: Comparability graph

The comparability graph of a partially ordered set ${\displaystyle P}$ has as vertices the elements of ${\displaystyle P}$ and has as edges precisely those pairs ${\displaystyle \{x,y\}}$ of elements for which ${\displaystyle x\ {\overset {<}{\underset {>}{=}}}\ y}$.^[2]

Classification

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 T₁ and T₂ criteria are comparable, while the T₁ and sobriety criteria are not.

See also

• Strict weak ordering – Mathematical ranking of a setPages displaying short descriptions of redirect targets, a partial ordering in which incomparability is a transitive relation

References

1. Trotter, William T. (1992), Combinatorics and Partially Ordered Sets:Dimension Theory, Johns Hopkins Univ. Press, p. 3
2. Gilmore, P. C.; Hoffman, A. J. (1964), "A characterization of comparability graphs and of interval graphs", Canadian Journal of Mathematics, 16: 539–548, doi:10.4153/CJM-1964-055-5.

External links

• "PlanetMath: partial order". Archived from the original on 11 July 2012. Retrieved 6 April 2010.