From Wikipedia, the free encyclopedia
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.
Rigorous definition[edit]A binary relation on a set P {\displaystyle P} is by definition any subset R {\displaystyle R} of P × P . {\displaystyle P\times P.} Given x , y ∈ P , {\displaystyle x,y\in P,} x R y {\displaystyle xRy} is written if and only if ( x , y ) ∈ R , {\displaystyle (x,y)\in R,} in which case x {\displaystyle x} is said to be related to y {\displaystyle y} by R . {\displaystyle R.} An element x ∈ P {\displaystyle x\in P} is said to be R {\displaystyle R} -comparable, or comparable (with respect to R {\displaystyle R} ), to an element y ∈ P {\displaystyle y\in P} if x R y {\displaystyle xRy} or y R x . {\displaystyle yRx.} Often, a symbol indicating comparison, such as < {\displaystyle <} (or ≤ , {\displaystyle \leq ,} > , {\displaystyle >,} ≥ , {\displaystyle \geq ,} and many others) is used instead of R , {\displaystyle R,} in which case x < y {\displaystyle x<y} is written in place of x R y , {\displaystyle xRy,} which is why the term "comparable" is used.
Comparability with respect to R {\displaystyle R} induces a canonical binary relation on P {\displaystyle P} ; specifically, the comparability relation induced by R {\displaystyle R} is defined to be the set of all pairs ( x , y ) ∈ P × P {\displaystyle (x,y)\in P\times P} such that x {\displaystyle x} is comparable to y {\displaystyle y} ; that is, such that at least one of x R y {\displaystyle xRy} and y R x {\displaystyle yRx} is true. Similarly, the incomparability relation on P {\displaystyle P} induced by R {\displaystyle R} is defined to be the set of all pairs ( x , y ) ∈ P × P {\displaystyle (x,y)\in P\times P} such that x {\displaystyle x} is incomparable to y ; {\displaystyle y;} that is, such that neither x R y {\displaystyle xRy} nor y R x {\displaystyle yRx} is true.
If the symbol < {\displaystyle <} is used in place of ≤ {\displaystyle \leq } then comparability with respect to < {\displaystyle <} is sometimes denoted by the symbol = > < {\displaystyle {\overset {<}{\underset {>}{=}}}} , and incomparability by the symbol = > < {\displaystyle {\cancel {\overset {<}{\underset {>}{=}}}}\!} .[1][failed verification] Thus, for any two elements x {\displaystyle x} and y {\displaystyle y} of a partially ordered set, exactly one of x = > < y {\displaystyle x\ {\overset {<}{\underset {>}{=}}}\ y} and x = > < y {\displaystyle x{\cancel {\overset {<}{\underset {>}{=}}}}y} 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 comparability and incomparability are symmetric, that is x {\displaystyle x} is comparable to y {\displaystyle y} if and only if y {\displaystyle y} is comparable to x , {\displaystyle x,} and likewise for incomparability.
Comparability graphs[edit]The comparability graph of a partially ordered set P {\displaystyle P} has as vertices the elements of P {\displaystyle P} and has as edges precisely those pairs { x , y } {\displaystyle \{x,y\}} of elements for which x = > < y {\displaystyle x\ {\overset {<}{\underset {>}{=}}}\ y} .[2]
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.
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4