comparability

A binary relation on a set $P$ is by definition any subset $R$ of $P\; \backslash times\; P.$ Given $x,\; y\; \backslash in\; P,$ $x\; R\; y$ is written if and only if $(x,\; y)\; \backslash in\; R,$ in which case $x$ is said to be {{em|related}} to $y$ by $R.$

An element $x\; \backslash in\; P$ is said to be {{em|$R$-comparable}}, or {{em|comparable}} ({{em|with respect to $R$}}), to an element $y\; \backslash in\; P$ if $x\; R\; y$ or $y\; R\; x.$

Often, a symbol indicating comparison, such as (or $\backslash ,\backslash leq\backslash ,,$ $\backslash ,>,\backslash ,$ $\backslash geq,$ and many others) is used instead of $R,$ in which case 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 {{em|comparability relation}} induced by $R$ is defined to be the set of all pairs $(x,\; y)\; \backslash in\; P\; \backslash times\; 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 {{em|incomparability relation}} on $P$ induced by $R$ is defined to be the set of all pairs $(x,\; y)\; \backslash in\; P\; \backslash times\; 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 $\backslash ,\backslash leq\backslash ,$ then comparability with respect to is sometimes denoted by the symbol , and incomparability by the symbol .{{citation|title=Combinatorics and Partially Ordered Sets:Dimension Theory | authorlink=William T. Trotter|first=William T.|last=Trotter|publisher=Johns Hopkins Univ. Press|year=1992|pages=3}}{{Failed verification|date=March 2025|reason=The reference uses ⊥ for comparable and ‖ for incomparable}}

Thus, for any two elements $x$ and $y$ of a partially ordered set, exactly one of and is true.

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 {{em|comparability}} and {{em|incomparability}} are symmetric, that is $x$ is comparable to $y$ if and only if $y$ is comparable to $x,$ and likewise for incomparability.

{{main article|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 $\backslash \{\; x,\; y\; \backslash \}$ of elements for which .{{citation|title=A characterization of comparability graphs and of interval graphs|first1=P. C.|last1=Gilmore|first2=A. J.|last2=Hoffman|author2-link=Alan Hoffman (mathematician)|journal=Canadian Journal of Mathematics|volume=16|year=1964|pages=539–548|doi=10.4153/CJM-1964-055-5|doi-access=free}}.

When classifying mathematical objects (e.g., topological spaces), two {{em|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.

• {{annotated link|Strict weak ordering}}, a partial ordering in which incomparability is a transitive relation

{{reflist}}

• {{cite web|url=http://planetmath.org/encyclopedia/PartialOrder.html|title=PlanetMath: partial order|author=|date=|publisher=|access-date=6 April 2010|archive-date=11 July 2012|archive-url=https://web.archive.org/web/20120711031419/http://planetmath.org/encyclopedia/PartialOrder.html|url-status=dead}}

{{Order theory}}

Category:Binary relations

Category:Order theory