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,$ $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<y$ 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 {>}{=}}}}\!$ .^[1] 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$ .^[2]

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 T₁ and T₂ criteria are comparable, while the T₁ and sobriety criteria are not.

References

^ Trotter, William T. (1992), Combinatorics and Partially Ordered Sets:Dimension Theory, Johns Hopkins Univ. Press, p. 3
^ Gilmore, P. C.; Hoffman, A. J. (1964), "A characterization of comparability graphs and of interval graphs", Canadian Journal of Mathematics, 16: 539–548, doi:10.4153/CJM-1964-055-5.

External links

"PlanetMath: partial order". Archived from the original on 11 July 2012. Retrieved 6 April 2010.

[1] Trotter, William T. (1992), Combinatorics and Partially Ordered Sets:Dimension Theory, Johns Hopkins Univ. Press, p. 3

[2] Gilmore, P. C.; Hoffman, A. J. (1964), "A characterization of comparability graphs and of interval graphs", Canadian Journal of Mathematics, 16: 539–548, doi:10.4153/CJM-1964-055-5.

[1]

[2]

v t e Order theory
Topics Glossary Category
Key concepts	Binary relation Boolean algebra Cyclic order Lattice Partial order Preorder Total order Weak ordering
Results	Boolean prime ideal theorem Cantor–Bernstein theorem Cantor's isomorphism theorem Dilworth's theorem Dushnik–Miller theorem Hausdorff maximal principle Knaster–Tarski theorem Kruskal's tree theorem Laver's theorem Mirsky's theorem Szpilrajn extension theorem Zorn's lemma
Properties & Types (list)	Antisymmetric Asymmetric Boolean algebra topics Completeness Connected Covering Dense Directed (Partial) Equivalence Foundational Heyting algebra Homogeneous Idempotent Lattice Bounded Complemented Complete Distributive Join and meet Reflexive Partial order Chain-complete Graded Eulerian Strict Prefix order Preorder Total Semilattice Semiorder Symmetric Total Tolerance Transitive Well-founded Well-quasi-ordering (Better) (Pre) Well-order
Constructions	Composition Converse/Transpose Lexicographic order Linear extension Product order Reflexive closure Series-parallel partial order Star product Symmetric closure Transitive closure
Topology & Orders	Alexandrov topology & Specialization preorder Ordered topological vector space Normal cone Order topology Order topology Topological vector lattice Banach Fréchet Locally convex Normed
Related	Antichain Cofinal Cofinality Comparability Graph Duality Filter Hasse diagram Ideal Net Subnet Order morphism Embedding Isomorphism Order type Ordered field Positive cone of an ordered field Ordered vector space Partially ordered Positive cone of an ordered vector space Riesz space Partially ordered group Positive cone of a partially ordered group Upper set Young's lattice