# Szpilrajn extension theorem

{{ safesubst:#invoke:Unsubst||$N=Tone |date=__DATE__ |$B=
{{#invoke:Message box|ambox}}
}}
Template:Inappropriate person
In mathematics, the **Szpilrajn extension theorem**, due to Template:Harvs (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, given a binary relation *R* that is irreflexive and transitive it is always possible to find an extension of the relation (i.e. a relation *T* that strictly includes *R*) which is asymmetric, negatively transitive and connected.

First of all, we need some definitions to be clear upon the terminology we will use speaking about relations with particular properties.

## Definition (negative transitivity)

Given a binary relation on a generic set , we say that is **negatively transitive** if

Note that negative transitivity can also be rewritten as :, simply using the fact that can be rewritten as

## Definition (connection)

Given a binary relation on a generic set , we say that R is *connected (weakly)* if : either or .

## Properties

This properties on binary relations can be easily checked by definition:

- R is
*irreflexive*and*transitive*R is*asymmetric*.^{[1]} - R is
*asymmetric*,*transitive*and*connected*R is*negatively transitive*.

To enounce precisely the theorem, we need yet a couple of definitions and a useful, simple lemma.

## Definition (strict orders)

- A binary relation R is said to be a
*strict partial order*if it is irreflexive and transitive, and it is a*strict order*if it is*asymmetric*,*negatively transitive*and*complete*.

## Lemma

Let R be a strict partial order on X. Then there exists another binary relation T on X which is still a strict partial order and extends R, hence:

This lemma can be easily proved, by taking such that , which exists since the relation is not connected.

we can define another relation:

Finally, set which is trivially an extension of R and another strict partial order on X.

## Theorem (Szpilrajn's extension theorem)

Let *R* be a strict partial order on a set *X*. Then there exists a relation *T* that extends *R* and is a strict order on *X*.

## Proof

We want to show the existence of a maximal element in with respect to set inclusion.

To do this, we will use Zorn's Lemma. First of all we want to verify the hypothesis of the Lemma, hence that any chain (respect to inclusion) of admits an upper bound in .

Define

Clearly is an upper bound to the chain, but we have to show that , hence that is another strict partial order which extends R.

Obviously it contains R, as all contains R, and it is irreflexive, as , since any

We have to show that is transitive and here we use the chain properties of .

As is defined as a union of sets, there exists

But is a chain with respect to inclusion, hence it holds that or vice versa, so that the two couples of elements of X both belong to the same set in the union, and that set is a transitive relation; then also is in that set, hence in .

Applying Zorn's Lemma, we deduce that admits an upper bound with respect to set inclusion; let's call T that bound.

T has to be a complete relation, as if it was not, we could construct (exactly as in the preceding Lemma) another binary relation which strictly extends (strictly includes) T and is a strict partial order, so yet another element of , contradicting that T is a maximal of .

So *T* is an irreflexive, transitive and complete binary relation on *X*. But as we observed above, irreflexivity and transitivity give asymmetry that, with transitivity and completeness, give negative transitivity.

Hence *T* is a strict order on *X* that extends the partial order *R*.

## References

- ↑ {{#invoke:citation/CS1|citation |CitationClass=book }} Lemma 1.1 (iv). Note that this source refers to asymmetric relations as "strictly antisymmetric".

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}