View source for Comparability

{{Short description|Property of elements related by inequalities}}
{{More citations needed|date=December 2021}}{{Wiktionary|comparability}}
{{See also|Comparison (mathematics)}}
[[File:Infinite lattice of divisors.svg|thumb|[[Hasse diagram]] of the [[natural number]]s, partially ordered by "''x''≤''y'' if ''x'' [[divides]] ''y''". The numbers 4 and 6 are incomparable, since neither divides the other.]]
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 <math>P</math> is by definition any subset <math>R</math> of <math>P \times P.</math> Given <math>x, y \in P,</math> <math>x R y</math> is written if and only if <math>(x, y) \in R,</math> in which case <math>x</math> is said to be '''{{em|related}}''' to <math>y</math> by <math>R.</math> 
An element <math>x \in P</math> is said to be '''{{em|<math>R</math>-comparable}}''', or '''{{em|comparable}}''' ({{em|with respect to <math>R</math>}}), to an element <math>y \in P</math> if <math>x R y</math> or <math>y R x.</math>  
Often, a symbol indicating comparison, such as <math>\,<\,</math> (or <math>\,\leq\,,</math> <math>\,>,\,</math> <math>\geq,</math> and many others) is used instead of <math>R,</math> in which case <math>x < y</math> is written in place of <math>x R y,</math> which is why the term "comparable" is used. 

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

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

== Example ==

A [[Total order|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 {{em|comparability}} and {{em|incomparability}} are [[Symmetric relation|symmetric]], that is <math>x</math> is comparable to <math>y</math> if and only if <math>y</math> is comparable to <math>x,</math> and likewise for incomparability.

== Comparability graphs ==
{{main article|Comparability graph}}
The comparability graph of a partially ordered set <math>P</math> has as vertices the elements of <math>P</math> and has as edges precisely those pairs <math>\{ x, y \}</math> of elements for which <math>x\ \overset{<}{\underset{>}{=}}\ y</math>.<ref>{{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}}.</ref>

== Classification ==

When [[Class (set theory)|classifying]] mathematical objects (e.g., [[topological space]]s), 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 [[T1 space|T<sub>1</sub>]] and [[Hausdorff space|T<sub>2</sub>]] criteria are comparable, while the T<sub>1</sub> and [[Sober space|sobriety]] criteria are not.

== See also ==
* {{annotated link|Strict weak ordering}}, a partial ordering in which incomparability is a [[transitive relation]]

==References==

{{reflist}}

==External links==

* {{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]]