Szpilrajn extension theorem

Short description: Mathematical result on order relations

In order theory, the Szpilrajn extension theorem (also called the order-extension principle), proved by Edward Szpilrajn in 1930, 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. The theorem is one of many examples of the use of the axiom of choice in the form of Zorn's lemma to find a maximal set with certain properties.

Definitions and statement

A binary relation [math]\displaystyle{ R }[/math] on a set [math]\displaystyle{ X }[/math] is formally defined as a set of ordered pairs [math]\displaystyle{ (x, y) }[/math] of elements of [math]\displaystyle{ X, }[/math] and [math]\displaystyle{ (x, y) \in R }[/math] is often abbreviated as [math]\displaystyle{ xRy. }[/math]

A relation is reflexive if [math]\displaystyle{ xRx }[/math] holds for every element [math]\displaystyle{ x \in X; }[/math] it is transitive if [math]\displaystyle{ xRy \text{ and } yRz }[/math] imply [math]\displaystyle{ xRz }[/math] for all [math]\displaystyle{ x, y, z \in X; }[/math] it is antisymmetric if [math]\displaystyle{ xRy \text{ and } yRx }[/math] imply [math]\displaystyle{ x = y }[/math] for all [math]\displaystyle{ x, y \in X; }[/math] and it is a connex relation if [math]\displaystyle{ xRy \text{ or } yRx }[/math] holds for all [math]\displaystyle{ x, y \in X. }[/math] A partial order is, by definition, a reflexive, transitive and antisymmetric relation. A total order is a partial order that is connex.

A relation [math]\displaystyle{ R }[/math] is contained in another relation [math]\displaystyle{ S }[/math] when all ordered pairs in [math]\displaystyle{ R }[/math] also appear in [math]\displaystyle{ S; }[/math] that is,[math]\displaystyle{ xRy }[/math] implies [math]\displaystyle{ xSy }[/math] for all [math]\displaystyle{ x, y \in X. }[/math] The extension theorem states that every relation [math]\displaystyle{ R }[/math] that is reflexive, transitive and antisymmetric (that is, a partial order) is contained in another relation [math]\displaystyle{ S }[/math] which is reflexive, transitive, antisymmetric and connex (that is, a total order).

Proof

The theorem is proved in two steps. First, one shows that, if a partial order does not compare some two elements, it can be extended to an order with a superset of comparable pairs. A maximal partial order cannot be extended, by definition, so it follows from this step that a maximal partial order must be a total order. In the second step, Zorn's lemma is applied to find a maximal partial order that extends any given partial order.

For the first step, suppose that a given partial order does not compare [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math]. Then the order is extended by first adding the pair [math]\displaystyle{ xRy }[/math] to the relation, which may result in a non-transitive relation, and then restoring transitivity by adding all pairs [math]\displaystyle{ qRp }[/math] such that [math]\displaystyle{ qRx \text{ and } yRp. }[/math] This produces a relation that is still reflexive, antisymmetric and transitive and that strictly contains the original one. It follows that if the partial orders extending [math]\displaystyle{ R }[/math] are themselves partially ordered by extension, then any maximal element of this extension order must be a total order.

Next it is shown that the poset of partial orders extending [math]\displaystyle{ R }[/math], ordered by extension, has a maximal element. The existence of such a maximal element is proved by applying Zorn's lemma to this poset. Zorn's lemma states that a partial order in which every chain has an upper bound has a maximal element. A chain in this poset is a set of relations in which, for every two relations, one extends the other. An upper bound for a chain [math]\displaystyle{ \mathcal{C} }[/math] can be found as the union of the relations in the chain, [math]\displaystyle{ \textstyle\bigcup \mathcal{C} }[/math]. This union is a relation that extends [math]\displaystyle{ R }[/math], since every element of [math]\displaystyle{ \mathcal{C} }[/math] is a partial order having [math]\displaystyle{ R }[/math] as a subset. Next, it is shown that [math]\displaystyle{ \textstyle\bigcup \mathcal{C} }[/math] is a transitive relation. Suppose that [math]\displaystyle{ (x, y) }[/math] and [math]\displaystyle{ (y, z) }[/math] are in [math]\displaystyle{ \textstyle\bigcup \mathcal{C}, }[/math] so that there exist [math]\displaystyle{ S, T \in \mathcal{C} }[/math] such that [math]\displaystyle{ (x, y) \in S }[/math] and [math]\displaystyle{ (y, z) \in T }[/math]. Because [math]\displaystyle{ \mathcal{C} }[/math] is a chain, one of [math]\displaystyle{ S }[/math] or [math]\displaystyle{ T }[/math] must extend the other and contain both [math]\displaystyle{ (x, y) }[/math] and [math]\displaystyle{ (y, z) }[/math], and by its transitivity it also contains [math]\displaystyle{ (x,z) }[/math], as does the union. Similarly, it can be shown that [math]\displaystyle{ \textstyle\bigcup \mathcal{C} }[/math] is antisymmetric. Thus, [math]\displaystyle{ \textstyle\bigcup \mathcal{C} }[/math] is an extension of [math]\displaystyle{ R }[/math], so it belongs to the poset of extensions of [math]\displaystyle{ R }[/math], and is an upper bound for [math]\displaystyle{ \mathcal{C} }[/math].

This argument shows that Zorn's lemma may be applied to the poset of extensions of [math]\displaystyle{ R }[/math], producing a maximal element [math]\displaystyle{ Q }[/math]. By the first step this maximal element must be a total order, completing the proof.

Strength

Some form of the axiom of choice is necessary in proving the Szpilrajn extension theorem. The extension theorem implies the axiom of finite choice: if the union of a family of finite sets is given the empty partial order, and this is extended to a total order, the extension defines a choice from each finite set, its minimum element in the total order. Although finite choice is a weak version of the axiom of choice, it is independent of Zermelo–Fraenkel set theory without choice.

The Szpilrajn extension theorem together with another consequence of the axiom of choice, the principle that every total order has a cofinal well-order, can be combined to prove the full axiom of choice. With these assumptions, one can choose an element from any given set by extending its empty partial order, finding a cofinal well-order, and choosing the minimum element from that well-ordering.

Other extension theorems

Arrow stated that every preorder (reflexive and transitive relation) can be extended to a total preorder (transitive and connex relation). 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 Suzumura-consistent, which means that there is no cycle of elements such that [math]\displaystyle{ xRy }[/math] for every pair of consecutive elements [math]\displaystyle{ (x, y), }[/math] and there is some pair of consecutive elements [math]\displaystyle{ (x, y) }[/math] in the cycle for which [math]\displaystyle{ yRx }[/math] does not hold.