Szpilrajn extension theorem

In mathematics, the Szpilrajn extension theorem, due to Edward Szpilrajn (1930) (later called Edward Marczewski), 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 into a total order, where:

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.

A binary relation R over a set S is formally defined as a set of pairs of elements ‹ x,y › where x, y ∈ S. The condition ‹ x,y › ∈ R is generally abbreviated xRy.

A relation is irreflexive if xRx holds for no element x ∈ S. It is transitive if xRy and yRz imply xRz. It is total if either xRy or yRx holds for every pair of elements x and y of S.

If a relation R is contained in another T then every pair in the first is also in the second. As a result, xRy implies xTy, which can be taken as an alternative definition of containment.

The extension theorem tells that every relation R that is non-reflexive and transitive (a strict partial order) is contained in another T that is still non-reflexive and transitive but also total (a total order).

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; 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 obtained 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, as well as 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 because at least the pair xRy has been added. Some other pairs of elements may still be incomparable, but the change can be performed on it again.

...
Wikipedia