Comparability
Encyclopedia
In mathematics
, any two elements x and y of a set P that is partially ordered by a binary relation ≤ are comparable when either x ≤ y or y ≤ x. If it is not the case that x and y are comparable, then they are called incomparable.
A totally ordered
set is exactly a partially ordered set in which every pair of elements is comparable.
It follows immediately from the definitions of comparability and incomparability that both relations are symmetric
, that is x is comparable to y if and only if y is comparable to x, and likewise for incomparability.
Thus, for any pair of elements x and y of a partially ordered set, exactly one of the following is true,
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.
mathematical objects (e.g., topological space
s), two criteria are said to be comparable when the objects that obey one criterion constitute a subset of the objects that obey the other. For example, the T1
and T2
criteria are comparable, while the T1 and sobriety
criteria are not.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, any two elements x and y of a set P that is partially ordered by a binary relation ≤ are comparable when either x ≤ y or y ≤ x. If it is not the case that x and y are comparable, then they are called incomparable.
A totally ordered
Total order
In set theory, a total order, linear order, simple order, or ordering is a binary relation on some set X. The relation is transitive, antisymmetric, and total...
set is exactly a partially ordered set in which every pair of elements is comparable.
It follows immediately from the definitions of comparability and incomparability that both relations are symmetric
Symmetric relation
In mathematics, a binary relation R over a set X is symmetric if it holds for all a and b in X that if a is related to b then b is related to a.In mathematical notation, this is:...
, that is x is comparable to y if and only if y is comparable to x, and likewise for incomparability.
Notation
Comparability is denoted by the symbol ⊥, and incomparability by the symbol ||.Thus, for any pair of elements x and y of a partially ordered set, exactly one of the following is true,
- x ⊥ y, or
- x || y.
Comparability graphs
The comparability graphComparability graph
In graph theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order...
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.
Classification
When classifyingClass (set theory)
In set theory and its applications throughout mathematics, a class is a collection of sets which can be unambiguously defined by a property that all its members share. The precise definition of "class" depends on foundational context...
mathematical objects (e.g., topological space
Topological space
Topological spaces are mathematical structures that allow the formal definition of concepts such as convergence, connectedness, and continuity. They appear in virtually every branch of modern mathematics and are a central unifying notion...
s), two criteria are said to be comparable when the objects that obey one criterion constitute a subset of the objects that obey the other. For example, the T1
T1 space
In topology and related branches of mathematics, a T1 space is a topological space in which, for every pair of distinct points, each has an open neighborhood not containing the other. An R0 space is one in which this holds for every pair of topologically distinguishable points...
and T2
Hausdorff space
In topology and related branches of mathematics, a Hausdorff space, separated space or T2 space is a topological space in which distinct points have disjoint neighbourhoods. Of the many separation axioms that can be imposed on a topological space, the "Hausdorff condition" is the most frequently...
criteria are comparable, while the T1 and sobriety
Sober space
In mathematics, a sober space is a topological spacesuch that every irreducible closed subset of X is the closure of exactly one point of X: that is, has a unique generic point.-Properties and examples :...
criteria are not.