In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, two elements ''x'' and ''y'' of a set ''P'' are said to be comparable with respect to a
binary relation
In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over Set (mathematics), sets and is a new set of ordered pairs consisting of ele ...
≤ 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
In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over Set (mathematics), sets and is a new set of ordered pairs consisting of ele ...
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.
Example
A
totally ordered
In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X:
# a \leq a ( reflexive) ...
set is a
partially ordered set
In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a Set (mathematics), set. A poset consists of a set toget ...
in which any two elements are comparable. The
Szpilrajn extension theorem
In order theory, the Szpilrajn extension theorem (also called the order-extension principle), proved by Edward Szpilrajn in 1930,. states that every strict partial order is contained in a total order. Intuitively, the theorem says that any method ...
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 grc, συμμετρία "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 precise definiti ...
, that is
is comparable to
if and only if
is comparable to
and likewise for incomparability.
Comparability graphs
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
.
[.]
Classification
When
classifying mathematical objects (e.g.,
topological space
In mathematics, a topological space is, roughly speaking, a geometrical space in which closeness is defined but cannot necessarily be measured by a numeric distance. More specifically, a topological space is a set whose elements are called points ...
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 criteria are comparable, while the T
1 and
sobriety
Sobriety is the condition of not having any measurable levels or effects from alcohol or drugs. Sobriety is also considered to be the natural state of a human being at birth. A person in a state of sobriety is considered sober. Organizations o ...
criteria are not.
See also
* , a partial ordering in which incomparability is a
transitive relation
In mathematics, a relation on a set is transitive if, for all elements , , in , whenever relates to and to , then also relates to . Each partial order as well as each equivalence relation needs to be transitive.
Definition
A homog ...
References
External links
*
{{Order theory
Binary relations
Order theory