In
order theory
Order theory is a branch of mathematics that investigates the intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article intr ...
, the Szpilrajn extension theorem (also called the order-extension principle), proved by
Edward Szpilrajn in 1930,
[.] states that every
strict partial order
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. A poset consists of a set together with a binary r ...
is contained in a
total order
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 ...
. 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. The theorem is one of many examples of the use of the
axiom of choice
In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collection ...
in the form of
Zorn's lemma to find a maximal set with certain properties.
Definitions and statement
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 sets and is a new set of ordered pairs consisting of elements in and in ...
on a set
is formally defined as a set of ordered pairs
of elements of
and
is often abbreviated as
A relation is
reflexive if
holds for every element
it is
transitive if
imply
for all
it is
antisymmetric if
imply
for all
and it is a
connex relation
In mathematics, a relation on a set is called connected or total if it relates (or "compares") all pairs of elements of the set in one direction or the other while it is called strongly connected if it relates pairs of elements.
As described ...
if
holds for all
A partial order is, by definition, a reflexive, transitive and antisymmetric relation. A total order is a partial order that is connex.
A relation
is contained in another relation
when all ordered pairs in
also appear in
that is,
implies
for all
The extension theorem states that every relation
that is reflexive, transitive and antisymmetric (that is, a partial order) is contained in another relation
which is reflexive, transitive, antisymmetric and connex (that is, a total order).
Proof
The theorem is proved in two steps. First, if a partial order does not compare
and
it can be extended by first adding the pair
and then performing the
transitive closure
In mathematics, the transitive closure of a binary relation on a set is the smallest relation on that contains and is transitive. For finite sets, "smallest" can be taken in its usual sense, of having the fewest related pairs; for infinite ...
, and second, since this operation generates an ordering that strictly contains the original one and can be applied to all pairs of incomparable elements, there exists a relation in which all pairs of elements have been made comparable.
The first step is proved as a preliminary lemma, in which a partial order where a pair of elements
and
are incomparable is changed to make them comparable. This is done by first adding the pair
to the relation, which may result in a non-transitive relation, and then restoring transitivity by adding all pairs
such that
This is done on a single pair of incomparable elements
and
and produces a relation that is still reflexive, antisymmetric and transitive and that strictly contains the original one.
Next it is shown that the
poset
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. A poset consists of a set together with a binary r ...
of partial orders containing
ordered by inclusion, has a maximal element. The existence of such a maximal element is proved by applying
Zorn's lemma to this poset. A chain in this poset is a set of relations containing
such that given any two of these relations, one is contained in the other.
To apply Zorn's lemma, it must be shown that every chain has an upper bound in the poset. Let
be such a chain, and it remains to show that the union of its elements,
is an upper bound for
which is in the poset:
contains the original relation
since every element of
is a partial order containing
Next, it is shown that
is a transitive relation. Suppose that
and
are in
so that there exist
such that
Since
is a chain, either
Suppose
the argument for when
is similar. Then
Since all relations produced by our process are transitive,
is in
and therefore also in
Similarly, it can be shown that
is antisymmetric.
Therefore by Zorn's lemma the set of partial orders containing
has a maximal element
and it remains only to show that
is total. Indeed if
had a pair of incomparable elements then it is possible to apply the process of the first step to it, leading to another strict partial order that contains
and strictly contains
contradicting that
is maximal.
is therefore a total order containing
completing the proof.
Other extension theorems
Arrow stated that every
preorder
In mathematics, especially in order theory, a preorder or quasiorder is a binary relation that is reflexive and transitive. Preorders are more general than equivalence relations and (non-strict) partial orders, both of which are special cas ...
(reflexive and transitive relation) can be extended to a
total preorder
In mathematics, especially order theory, a weak ordering is a mathematical formalization of the intuitive notion of a ranking of a set, some of whose members may be tied with each other. Weak orders are a generalization of totally ordered set ...
(transitive and connex relation), and this claim was later proved by Hansson.
Suzumura proved that a binary relation can be extended to a total preorder if and only if it is , which means that there is no cycle of elements such that
for every pair of consecutive elements
and there is some pair of consecutive elements
in the cycle for which
does not hold.
See also
*
References
{{Order theory
Articles containing proofs
Axiom of choice
Order theory
Theorems in the foundations of mathematics