HOME

TheInfoList




In
mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and their changes (cal ...
, two elements ''x'' and ''y'' of a set ''P'' are said to be comparable with respect to a
binary relation Binary may refer to: Science and technology Mathematics * Binary number In mathematics and digital electronics Digital electronics is a field of electronics The field of electronics is a branch of physics and electrical engineeri ...
≤ 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 Binary may refer to: Science and technology Mathematics * Binary number In mathematics and digital electronics Digital electronics is a field of electronics The field of electronics is a branch of physics and electrical engineeri ...
on a set P is by definition any subset R of P \times P. Given x, y \in P, x R y is written if and only if (x, y) \in R, in which case x is said to be to y by R. An element x \in P is said to be , or (), to an element y \in P if x R y or y R x. Often, a symbol indicating comparison, such as \,<\, (or \,\leq\,, \,>,\, \geq, and many others) is used instead of R, in which case x < y is written in place of x R y, which is why the term "comparable" is used. Comparability with respect to R induces a canonical binary relation on P; specifically, the induced by R is defined to be the set of all pairs (x, y) \in P \times P such that x is comparable to y; that is, such that at least one of x R y and y R x is true. Similarly, the on P induced by R is defined to be the set of all pairs (x, y) \in P \times P such that x is incomparable to y; that is, such that neither x R y nor y R x is true. If the symbol \,<\, is used in place of \,\leq\, then comparability with respect to \,<\, is sometimes denoted by the symbol \overset, and incomparability by the symbol \cancel\!. Thus, for any two elements x and y of a partially ordered set, exactly one of x\ \overset\ y and x \cancely is true.


Example

A
totally ordered In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). I ...
set is a
partially ordered set upright=1.15, Fig.1 The Hasse diagram of the Power set, set of all subsets of a three-element set \, ordered by set inclusion, inclusion. Sets connected by an upward path, like \emptyset and \, are comparable, while e.g. \ and \ are not. In mathem ...
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 and are
symmetric Symmetry (from Greek συμμετρία ''symmetria'' "agreement in dimensions, due proportion, arrangement") in everyday language refers to a sense of harmonious and beautiful proportion and balance. In mathematics, "symmetry" has a more pre ...
, 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 \ of elements for which x\ \overset\ y..


Classification

When classifying mathematical objects (e.g.,
topological space In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no gener ...
s), 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 ⊂. For example, the T1 and
T2
T<sub>2</sub>
criteria are comparable, while the T1 and
sobriety Image:Breathalyzer test 0013.png, A midshipman is subjected to a random breathalyzer test to determine whether he is sober. Sobriety is the condition of not having any measurable levels or effects from alcohol or drugs. Sobriety is also considered ...
criteria are not.


See also

* , a partial ordering in which incomparability is a
transitive relation In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and t ...


References

{{reflist Binary relations Order theory