Szpilrajn extension theorem

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 strict 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.

Contents 1 Definitions and statement 2 Proof 3 Other extension theorems 4 See also 5 References 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 xin X;} it is transitive if {displaystyle xRy{text{ and }}yRz} imply {displaystyle xRz} for all {displaystyle x,y,zin X;} it is antisymmetric if {displaystyle xRy{text{ and }}yRx} imply {displaystyle x=y} for all {displaystyle x,yin X;} and it is a connex relation if {displaystyle xRy{text{ or }}yRx} holds for all {displaystyle x,yin 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,yin 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, if a partial order does not compare {displaystyle x} and {displaystyle y,} it can be extended by first adding the pair {displaystyle (x,y)} and then performing the transitive closure, 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 {displaystyle x} and {displaystyle y} are incomparable is changed to make them comparable. This is done 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 is done on a single pair of incomparable elements {displaystyle x} and {displaystyle y,} 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 of partial orders containing {displaystyle R,} 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 {displaystyle R} 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 {displaystyle {mathcal {C}}} be such a chain, and it remains to show that the union of its elements, {displaystyle bigcup {mathcal {C}},} is an upper bound for {displaystyle {mathcal {C}}} which is in the poset: {displaystyle {mathcal {C}}} contains the original relation {displaystyle R} since every element of {displaystyle {mathcal {C}}} is a partial order containing {displaystyle R.} Next, it is shown that {displaystyle bigcup {mathcal {C}}} is a transitive relation. Suppose that {displaystyle (x,y)} and {displaystyle (y,z)} are in {displaystyle bigcup {mathcal {C}},} so that there exist {displaystyle S,Tin {mathcal {C}}} such that {displaystyle (x,y)in S{text{ and }}(y,z)in T.} Since {displaystyle {mathcal {C}}} is a chain, either {displaystyle Ssubseteq T{text{ or }}Tsubseteq S.} Suppose {displaystyle Ssubseteq T;} the argument for when {displaystyle Tsubseteq S} is similar. Then {displaystyle (x,y)in T.} Since all relations produced by our process are transitive, {displaystyle (x,z)} is in {displaystyle T} and therefore also in {displaystyle bigcup {mathcal {C}}.} Similarly, it can be shown that {displaystyle bigcup {mathcal {C}}} is antisymmetric.

Therefore by Zorn's lemma the set of partial orders containing {displaystyle R} has a maximal element {displaystyle Q,} and it remains only to show that {displaystyle Q} is total. Indeed if {displaystyle Q} 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 {displaystyle R} and strictly contains {displaystyle Q,} contradicting that {displaystyle Q} is maximal. {displaystyle Q} is therefore a total order containing {displaystyle R,} completing the proof.

Other extension theorems Arrow stated that every preorder (reflexive and transitive relation) can be extended to a total preorder (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 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.

See also Linear extension – Mathematical ordering of a partial order References ^ 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. Categories: Axiom of choiceTheorems in the foundations of mathematicsOrder theory