Szpilrajn extension theorem

In order theory, the Szpilrajn extension theorem (also called the order-extension principle), proved by Edward Szpilrajn in 1930,^[1] 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.

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

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

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

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 ${\displaystyle x}${\displaystyle x} and ${\displaystyle y}${\displaystyle y}. Then the order is extended by first adding the pair ${\displaystyle xRy}${\displaystyle xRy} to the relation, which may result in a non-transitive relation, and then restoring transitivity by adding all pairs ${\displaystyle qRp}${\displaystyle qRp} such that ${\displaystyle qRx{\text{ and }}yRp.}${\displaystyle qRx{\text{ and }}yRp.} 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 ${\displaystyle R}${\displaystyle R} 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 ${\displaystyle R}${\displaystyle R}, 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 ${\displaystyle {\mathcal {C}}}${\displaystyle {\mathcal {C}}} can be found as the union of the relations in the chain, ${\displaystyle \textstyle \bigcup {\mathcal {C}}}${\displaystyle \textstyle \bigcup {\mathcal {C}}}. This union is a relation that extends ${\displaystyle R}${\displaystyle R}, since every element of ${\displaystyle {\mathcal {C}}}${\displaystyle {\mathcal {C}}} is a partial order having ${\displaystyle R}${\displaystyle R} as a subset. Next, it is shown that ${\displaystyle \textstyle \bigcup {\mathcal {C}}}${\displaystyle \textstyle \bigcup {\mathcal {C}}} is a transitive relation. Suppose that ${\displaystyle (x,y)}${\displaystyle (x,y)} and ${\displaystyle (y,z)}${\displaystyle (y,z)} are in ${\displaystyle \textstyle \bigcup {\mathcal {C}},}${\displaystyle \textstyle \bigcup {\mathcal {C}},} so that there exist ${\displaystyle S,T\in {\mathcal {C}}}${\displaystyle S,T\in {\mathcal {C}}} such that ${\displaystyle (x,y)\in S}${\displaystyle (x,y)\in S} and ${\displaystyle (y,z)\in T}${\displaystyle (y,z)\in T}. Because ${\displaystyle {\mathcal {C}}}${\displaystyle {\mathcal {C}}} is a chain, one of ${\displaystyle S}${\displaystyle S} or ${\displaystyle T}${\displaystyle T} must extend the other and contain both ${\displaystyle (x,y)}${\displaystyle (x,y)} and ${\displaystyle (y,z)}${\displaystyle (y,z)}, and by its transitivity it also contains ${\displaystyle (x,z)}${\displaystyle (x,z)}, as does the union. Similarly, it can be shown that ${\displaystyle \textstyle \bigcup {\mathcal {C}}}${\displaystyle \textstyle \bigcup {\mathcal {C}}} is antisymmetric. Thus, ${\displaystyle \textstyle \bigcup {\mathcal {C}}}${\displaystyle \textstyle \bigcup {\mathcal {C}}} is an extension of ${\displaystyle R}${\displaystyle R}, so it belongs to the poset of extensions of ${\displaystyle R}${\displaystyle R}, and is an upper bound for ${\displaystyle {\mathcal {C}}}${\displaystyle {\mathcal {C}}}.

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

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.^[2]

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.^[3]

Arrow stated that every preorder (reflexive and transitive relation) can be extended to a total preorder (transitive and connex relation).^[4] This claim was later proved by Hansson.^{[5] [6]}

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 ${\displaystyle xRy}${\displaystyle xRy} for every pair of consecutive elements ${\displaystyle (x,y),}${\displaystyle (x,y),} and there is some pair of consecutive elements ${\displaystyle (x,y)}${\displaystyle (x,y)} in the cycle for which ${\displaystyle yRx}${\displaystyle yRx} does not hold.^[6]

• Axiom of choice
• Order theory
• Theorems in the foundations of mathematics

• CS1 French-language sources (fr)
• Articles with short description
• Short description is different from Wikidata
• Articles containing proofs