View source for Szpilrajn extension theorem

{{Short description|Mathematical result on order relations}}
In [[Order theory|order theory]], the '''Szpilrajn extension theorem''' (also called the '''order-extension principle'''), proved by Edward Szpilrajn in 1930,{{r|szpilrain}} states that every partial order is contained in a [[Total order|total order]]. Intuitively, the theorem says that any method of [[Comparability|comparing]] elements that leaves some pairs incomparable can be [[Linear extension|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|axiom of choice]] in the form of [[Zorn's lemma]] to find a maximal set with certain properties.

== Definitions and statement ==

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

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

This argument shows that Zorn's lemma may be applied to the poset of extensions of <math>R</math>, producing a maximal element <math>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|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.{{r|moore}}

The Szpilrajn extension theorem together with another consequence of the axiom of choice, the principle that every total order has a [[Cofinal (mathematics)|cofinal]] [[Well-order|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.{{r|howard-rubin}}

== Other extension theorems ==

[[Biography:Kenneth Arrow|Arrow]] stated that every [[Preorder|preorder]] (reflexive and transitive relation) can be extended to a [[Weak ordering|total preorder]] (transitive and connex relation).{{r|arrow}} This claim was later proved by Hansson.{{r|hansson|cato}}

Suzumura proved that a binary relation can be extended to a total preorder if and only if it is {{em|Suzumura-consistent}}, which means that there is no cycle of elements such that <math>xRy</math> for every pair of consecutive elements <math>(x, y),</math> and there is some pair of consecutive elements <math>(x, y)</math> in the cycle for which <math>yRx</math> does not hold.{{r|cato}}

==References==
{{reflist|refs=

<ref name=arrow>{{citation
 | contribution = IV.3: Quasi-orderings and compatible weak orderings
 | edition = 3rd
 | isbn = 978-0-300-18698-7
 | page = 64
 | publisher = Yale University Press
 | title = Social Choice and Individual Values
 | year = 2012}}</ref>

<ref name=cato>{{citation
 | last = Cato | first = Susumu
 | date = August 2011
 | doi = 10.1111/j.1467-999x.2011.04130.x
 | issue = 2
 | journal = Metroeconomica
 | pages = 235–249
 | title = Szpilrajn, Arrow and Suzumura: concise proofs of extension theorems and an extension
 | volume = 63}}</ref>

<ref name=hansson>{{citation
 | last = Hansson | first = Bengt
 | doi = 10.1007/BF00484979
 | issue = 4
 | journal = Synthese
 | jstor = 20114617
 | pages = 443–458
 | title = Choice structures and preference relations
 | volume = 18
 | year = 1968}}; see Lemma 3</ref>

<ref name=howard-rubin>{{citation
 | last1 = Howard | first1 = Paul
 | contribution = Note 121
 | doi = 10.1090/surv/059
 | isbn = 0-8218-0977-6
 | location = Providence, Rhode Island
 | mr = 1637107
 | page = 299
 | publisher = American Mathematical Society
 | series = Mathematical Surveys and Monographs
 | title = Consequences of the Axiom of Choice
 | volume = 59
 | year = 1998}}</ref>

<ref name=moore>{{citation
 | last = Moore | first = Gregory H.
 | doi = 10.1007/978-1-4613-9478-5
 | isbn = 0-387-90670-3
 | location = New York
 | mr = 679315
 | page = 222
 | publisher = Springer-Verlag
 | series = Studies in the History of Mathematics and Physical Sciences
 | title = Zermelo's Axiom of Choice: Its Origins, Development, and Influence
 | url = https://books.google.com/books?id=kJrhBwAAQBAJ&pg=PA222
 | volume = 8
 | year = 1982}}</ref>

<ref name=szpilrain>{{citation
 | doi = 10.4064/fm-16-1-386-389 | doi-access = free
 | journal = Fundamenta Mathematicae
 | language = French
 | pages = 386–389
 | title = Sur l'extension de l'ordre partiel
 | url = http://matwbn.icm.edu.pl/ksiazki/fm/fm16/fm16125.pdf
 | volume = 16
 | year = 1930}}</ref>

}}


[[Category:Articles containing proofs]]
[[Category:Axiom of choice]]
[[Category:Order theory]]
[[Category:Theorems in the foundations of mathematics]]

{{Sourceattribution|Szpilrajn extension theorem}}