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.

Definitions and statement

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

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

This argument shows that Zorn's lemma may be applied to the poset of extensions of ${\displaystyle R}$, producing a maximal element ${\displaystyle Q}$. 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. ^[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]

Other extension theorems

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

References

1. Szpilrajn, Edward (1930), "Sur l'extension de l'ordre partiel" (PDF), Fundamenta Mathematicae (in French), 16: 386–389, doi: 10.4064/fm-16-1-386-389
2. Moore, Gregory H. (1982), Zermelo's Axiom of Choice: Its Origins, Development, and Influence, Studies in the History of Mathematics and Physical Sciences, vol. 8, New York: Springer-Verlag, p. 222, doi:10.1007/978-1-4613-9478-5, ISBN   0-387-90670-3, MR   0679315
3. Howard, Paul; Rubin, Jean E. (1998), "Note 121", Consequences of the Axiom of Choice, Mathematical Surveys and Monographs, vol. 59, Providence, Rhode Island: American Mathematical Society, p. 299, doi:10.1090/surv/059, ISBN   0-8218-0977-6, MR   1637107
4. Arrow, Kenneth J. (2012), "IV.3: Quasi-orderings and compatible weak orderings", Social Choice and Individual Values (3rd ed.), Yale University Press, p. 64, ISBN   978-0-300-18698-7
5. Hansson, Bengt (1968), "Choice structures and preference relations", Synthese, 18 (4): 443–458, doi:10.1007/BF00484979, JSTOR   20114617 ; see Lemma 3
6. Cato, Susumu (August 2011), "Szpilrajn, Arrow and Suzumura: concise proofs of extension theorems and an extension", Metroeconomica, 63 (2): 235–249, doi:10.1111/j.1467-999x.2011.04130.x