Comparability

Short description: Property of elements related by inequalities

Hasse diagram of the natural numbers, 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.

## Contents

* 1 Rigorous definition
* 2 Example
* 3 Properties
* 4 Comparability graphs
* 5 Classification
* 6 See also
* 7 References
* 8 External links

## Rigorous definition

A binary relation on a set P is by definition any subset R of P×P. Given x,y∈P, xRy is written if and only if (x,y)∈R, in which case x is said to be related to y by R. An element x∈P is said to be R-comparable, or comparable (with respect to R), to an element y∈P if xRy or yRx. Often, a symbol indicating comparison, such as < (or ≤, >, ≥, 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)∈P×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)∈P×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 ≤ then comparability with respect to < is sometimes denoted by the symbol =><, and incomparability by the symbol =><.[1] Thus, for any two elements x and y of a partially ordered set, exactly one of x =>< y and x=><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 =>< 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 T1 and T2 criteria are comparable, while the T1 and sobriety criteria are not.

## See also

## References

1. ↑ Trotter, William T. (1992), Combinatorics and Partially Ordered Sets:Dimension Theory, Johns Hopkins Univ. Press, pp. 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, http://www.cms.math.ca/cjm/v16/p539, retrieved 2010-01-01 .

## External links

* "PlanetMath: partial order". http://planetmath.org/encyclopedia/PartialOrder.html.

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Comparability. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Comparability&oldid=209314"