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

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

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

The comparability graph of a partially ordered set ${\displaystyle P}${\displaystyle P} has as vertices the elements of ${\displaystyle P}${\displaystyle P} and has as edges precisely those pairs ${\displaystyle \{x,y\}}${\displaystyle \{x,y\}} of elements for which ${\displaystyle x\ {\overset {<}{\underset {>}{=}}}\ y}${\displaystyle x\ {\overset {<}{\underset {>}{=}}}\ y}.^[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 T₁ and T₂ criteria are comparable, while the T₁ and sobriety criteria are not.

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

• Partial Order at PlanetMath.

• Binary relations
• Order theory

• Articles with short description
• Short description is different from Wikidata
• Articles needing additional references from December 2021
• All articles needing additional references
• All articles with failed verification
• Articles with failed verification from March 2025
• Pages displaying short descriptions of redirect targets via Module:Annotated link