Comparability

---

title: "Comparability" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["binary-relations", "order-theory"] description: "Property of elements related by inequalities" topic_path: "general/binary-relations" source: "https://en.wikipedia.org/wiki/Comparability" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

::summary Property of elements related by inequalities ::

::figure[src="https://upload.wikimedia.org/wikipedia/commons/e/e6/Infinite_lattice_of_divisors.svg" caption="[[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 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 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 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 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 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 x R y and y R x 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 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{\overset{}{=}}}!. Thus, for any two elements x and y of a partially ordered set, exactly one of x\ \overset{}{=}}\ y and x \cancel{\overset{}{=}}}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

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 { x, y } of elements for which x\ \overset{}{=}}\ 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.

References

References

1. Trotter, William T.. (1992). "Combinatorics and Partially Ordered Sets:Dimension Theory". Johns Hopkins Univ. Press.
2. (1964). "A characterization of comparability graphs and of interval graphs". Canadian Journal of Mathematics.

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::