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

Comparability with respect to $R$ induces a canonical binary relation on $P$ ; specifically, the comparability relation induced by $R$ is defined to be the set of all pairs $(x,y)\in P\times P$ such that $x$ is comparable to $y$ ; that is, such that at least one of $xRy$ and $yRx$ is true. Similarly, the incomparability relation on $P$ induced by $R$ is defined to be the set of all pairs $(x,y)\in P\times P$ such that $x$ is incomparable to $y;$ that is, such that neither $xRy$ nor $yRx$ 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 comparability and incomparability are symmetric, that is $x$ is comparable to $y$ if and only if $y$ is comparable to $x,$ and likewise for incomparability.

## Comparability graphs

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$ .

## 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 T1 and T2 criteria are comparable, while the T1 and sobriety criteria are not.