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.

Definitions and statement

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

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

The extension theorem is then proved by showing that the set of strict partial orders containing R has some maximal element. If such an element had a pair of incomparable elements the transformation could be applied to it, resulting in a relation that strictly contains it. This would contradict maximality.

The existence of a maximal elements is proved via Zorn's lemma. In this context, it is applied to the set of all strict orders extending R, compared by set inclusion. A chain is therefore a sequence of relations, each extending R and contained in the following one. The lemma can be applied if every chain of relations extending R has an upper bound which is also a strict partial order extending R.

In other words, this upper bound should be a superset of the original relation, which is the case because every member of the chain contains it, and also a strict partial order: non-reflexive and transitive. The first holds because every element of the chain is a strict partial order, so none of the relations of the chain contains such a pair. Transitivity holds because the pairs ‹ x,y › and ‹ y,z › are in the union only if the first is in some relation of the chain and the second in some other. Being a chain, either the first relation is contained in the second or the second in the first. In the first case, ‹ x,y › is also in the second relation. Since all relations produced by the transformation are transitive, ‹ x,z › is in the second relation and therefore also in the union. A similar argument holds if the second relation is contained in the first.

By Zorn's lemma, the set of strict partial orders extending the original relation R has a maximal element Q, which is also a strict partial order extending R. This relation Q is proved to be total: if it had a pair of incomparable elements then the transformation could be applied to it, leading to another strict partial order that extends R and strictly contains Q, therefore contradicting the assumption that the Q is maximal in the set of strict partial orders extending R. This proves that Q has no pair of incomparable elements, in addition of being a strict partial order extending R. As a result, it is a total order extending R.

Other extension theorems

References

    This article is issued from Wikipedia - version of the Wednesday, November 11, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.