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.

Rigorous definition

A binary relation on a set $P$ is by definition any subset $R$ of $P \times P.$ Given $x, y \in P,$ $x R y$ is written if and only if $(x, y) \in R,$ in which case $x$ is said to be to $y$ by $R.$
An element $x \in P$ is said to be , or (), to an element $y \in P$ if $x R y$ or $y R x.$
Often, a symbol indicating comparison, such as $\,<\,$ (or $\,\leq\,,$ $\,>,\,$ $\geq,$ and many others) is used instead of $R,$ in which case $x < y$ 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 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 $x R y$ and $y R x$ is true.
Similarly, the 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 $x R y$ nor $y R x$ is true.

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

Classification

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

* , a partial ordering in which incomparability is a transitive relation

References

External links

*

{{Order theory

Binary relations
Order theory