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. 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 to by An element is said to be , or (), 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 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 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 . Thus, for any two elements and of a partially ordered set, exactly one of and is true. 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. Both of the relations and are symmetric, that is is comparable to if and only if is comparable to and likewise for incomparability. Comparability graph 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 . When classifying mathematical objects (e.g., topological spaces), two 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 ⊂.