Comparability

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
Hasse diagram of the natural numbers, partially ordered by "xy 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 xy or yx is true. They are called incomparable if they are not comparable.

Rigorous definition[edit]

A binary relation on a set is by definition any subset of Given is written if and only if in which case is said to be related to by An element is said to be -comparable, or comparable (with respect to ), to an element if or Often, a symbol indicating comparison, such as (or and many others) is used instead of in which case is written in place of which is why the term "comparable" is used.

Comparability with respect to induces a canonical binary relation on ; specifically, the comparability relation induced by is defined to be the set of all pairs such that is comparable to ; that is, such that at least one of and is true. Similarly, the incomparability relation on induced by is defined to be the set of all pairs such that is incomparable to that is, such that neither nor is true.

If the symbol is used in place of then comparability with respect to is sometimes denoted by the symbol , and incomparability by the symbol .[1] Thus, for any two elements and of a partially ordered set, exactly one of and is true.

Example[edit]

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[edit]

Both of the relations comparability and incomparability are symmetric, that is is comparable to if and only if is comparable to and likewise for incomparability.

Comparability graphs[edit]

The comparability graph of a partially ordered set has as vertices the elements of and has as edges precisely those pairs of elements for which .[2]

Classification[edit]

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.

See also[edit]

References[edit]

"PlanetMath: partial order". Retrieved 6 April 2010.

  1. ^ Trotter, William T. (1992), Combinatorics and Partially Ordered Sets:Dimension Theory, Johns Hopkins Univ. Press, p. 3 CS1 maint: discouraged parameter (link)
  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.