Szpilrajn extension theorem

In mathematics, the Szpilrajn extension theorem (also called the order-extension principle), proved by Edward Szpilrajn in 1930,[1] 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. The theorem states that every strict partial order is contained in a total order. Intuitively, the theorem states that a comparison between elements that leaves some pairs incomparable can be extended in such a way every element is either less than or greater than another.

Definitions and statement

A binary relation R on a set X is formally defined as a set of ordered pairs (x,y) of elements of X, and we often abbreviate (x,y) ∈ R as xRy.

A relation is irreflexive if xRx holds for no element x ∈ X; it is transitive if xRy and yRz imply xRz for all x, y, z ∈ X; and it is a connex relation if either xRy or yRx holds for all x, y ∈ X. A strict partial order is an irreflexive and transitive relation, and a total order is a strict partial order that is also a connex relation.

A relation R is contained in another relation S when all ordered pairs in R also appear in S, i.e. xRy implies xSy for all x, y ∈ X. The extension theorem states that every relation R that is irreflexive and transitive (i.e. a strict partial order) is contained in another relation S which is irreflexive and transitive but also connex so that it is a total order.

Proof

The theorem is proved in two steps. First, if a strict partial order does not compare x and y, it can be extended by first adding the pair (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 strict partial order where a pair of elements x and y are incomparable is changed to make them comparable. This is done by first adding the pair xRy to the relation, which may result in a non-transitive relation, and then restoring transitivity by adding all pairs qRy such that qRx, all pairs xRp such that yRp, and all pairs qRp such that qRx and yRp. This is done on a single pair of incomparable elements x and y, but produces a relation that is still irreflexive and transitive and that strictly contains the original one. Other pairs of elements may still be incomparable, in which case we can repeat this process.

The extension theorem is then proved by showing that the poset of strict partial orders containing 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 R such that given any two of these relations, one is contained in the other.

To apply Zorn's lemma we need to show that every chain has an upper bound in the poset. Let ${\mathcal {C}}$ be such a chain, and we show that the union of its elements, $\bigcup {\mathcal {C}}$ , is an upper bound for ${\mathcal {C}}$ which is in the poset: ${\mathcal {C}}$ contains the original relation R since every element of ${\mathcal {C}}$ is a strict partial order containing R. Next we show that $\bigcup {\mathcal {C}}$ is a transitive relation. Suppose that (x,y) and (y,z) are in $\bigcup {\mathcal {C}}$ , so that there exist $S,T\in {\mathcal {C}}$ such that $(x,y)\in S$ and $(y,z)\in T$ . Since ${\mathcal {C}}$ is a chain we have either S⊆T or T⊆S. Suppose S⊆T; the argument for when T⊆S is similar. Then we also have $(x,y)\in T$ . Since all relations produced by our process are transitive, (x,z) is in T, and therefore in $\bigcup {\mathcal {C}}$ .

Therefore by Zorn's lemma the set of strict partial orders containing R has a maximal element Q, and it remains only to show that Q is total. Indeed if Q had a pair of incomparable elements then we could apply our process to it, leading to another strict partial order that contains R and strictly contains Q, contradicting that Q is maximal. Q is therefore a total order containing R, completing the proof.

Other extension theorems

Arrow stated that every preorder (reflexive and transitive relation) can be extended to a total order (reflexitive, transitive and connex relation), and this claim was later proved by Hansson.
Suzumura proved that a binary relation can be extended to a total order if and only if it is Suzumura-consistent, which means that there is no cycle of elements such that xRy for every pair of consecutive elements (x,y), and there is some pair of consecutive elements (x,y) such that yRx does not hold.

gollark: I believe Gradle is famed for taking ages.

gollark: You can add on extra stuff, it works pretty reliably, it's quite well integrated, and very simple to use.

gollark: I quite like Rust's `cargo`.

gollark: Java project tooling seems very annoying.

gollark: IPR?

References

Marczewski, 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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Marczewski, 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.