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 [math]\displaystyle{ P }[/math] is by definition any subset [math]\displaystyle{ R }[/math] of [math]\displaystyle{ P \times P. }[/math] Given [math]\displaystyle{ x, y \in P, }[/math] [math]\displaystyle{ x R y }[/math] is written if and only if [math]\displaystyle{ (x, y) \in R, }[/math] in which case [math]\displaystyle{ x }[/math] is said to be related to [math]\displaystyle{ y }[/math] by [math]\displaystyle{ R. }[/math] An element [math]\displaystyle{ x \in P }[/math] is said to be [math]\displaystyle{ R }[/math]-comparable, or comparable (with respect to [math]\displaystyle{ R }[/math]), to an element [math]\displaystyle{ y \in P }[/math] if [math]\displaystyle{ x R y }[/math] or [math]\displaystyle{ y R x. }[/math] Often, a symbol indicating comparison, such as [math]\displaystyle{ \,\lt \, }[/math] (or [math]\displaystyle{ \,\leq\,, }[/math] [math]\displaystyle{ \,\gt ,\, }[/math] [math]\displaystyle{ \geq, }[/math] and many others) is used instead of [math]\displaystyle{ R, }[/math] in which case [math]\displaystyle{ x \lt y }[/math] is written in place of [math]\displaystyle{ x R y, }[/math] which is why the term "comparable" is used.
Comparability with respect to [math]\displaystyle{ R }[/math] induces a canonical binary relation on [math]\displaystyle{ P }[/math]; specifically, the comparability relation induced by [math]\displaystyle{ R }[/math] is defined to be the set of all pairs [math]\displaystyle{ (x, y) \in P \times P }[/math] such that [math]\displaystyle{ x }[/math] is comparable to [math]\displaystyle{ y }[/math]; that is, such that at least one of [math]\displaystyle{ x R y }[/math] and [math]\displaystyle{ y R x }[/math] is true. Similarly, the incomparability relation on [math]\displaystyle{ P }[/math] induced by [math]\displaystyle{ R }[/math] is defined to be the set of all pairs [math]\displaystyle{ (x, y) \in P \times P }[/math] such that [math]\displaystyle{ x }[/math] is incomparable to [math]\displaystyle{ y; }[/math] that is, such that neither [math]\displaystyle{ x R y }[/math] nor [math]\displaystyle{ y R x }[/math] is true.
If the symbol [math]\displaystyle{ \,\lt \, }[/math] is used in place of [math]\displaystyle{ \,\leq\, }[/math] then comparability with respect to [math]\displaystyle{ \,\lt \, }[/math] is sometimes denoted by the symbol [math]\displaystyle{ \overset{\lt }{\underset{\gt }{=}} }[/math], and incomparability by the symbol [math]\displaystyle{ \cancel{\overset{\lt }{\underset{\gt }{=}}}\! }[/math].[1] Thus, for any two elements [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math] of a partially ordered set, exactly one of [math]\displaystyle{ x\ \overset{\lt }{\underset{\gt }{=}}\ y }[/math] and [math]\displaystyle{ x \cancel{\overset{\lt }{\underset{\gt }{=}}}y }[/math] 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 [math]\displaystyle{ x }[/math] is comparable to [math]\displaystyle{ y }[/math] if and only if [math]\displaystyle{ y }[/math] is comparable to [math]\displaystyle{ x, }[/math] and likewise for incomparability.
Comparability graphs
The comparability graph of a partially ordered set [math]\displaystyle{ P }[/math] has as vertices the elements of [math]\displaystyle{ P }[/math] and has as edges precisely those pairs [math]\displaystyle{ \{ x, y \} }[/math] of elements for which [math]\displaystyle{ x\ \overset{\lt }{\underset{\gt }{=}}\ y }[/math].[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
- ↑ Trotter, William T. (1992), Combinatorics and Partially Ordered Sets:Dimension Theory, Johns Hopkins Univ. Press, pp. 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, http://www.cms.math.ca/cjm/v16/p539, retrieved 2010-01-01.
External links
 |  |
