Szpilrajn extension theorem

From formulasearchengine
Jump to navigation Jump to search

{{ 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

where by we mean

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 .

Say that R is strictly connected or complete if .

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:

such that and T is another strict partial order on X.

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

Naming:

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

Let , P is a strict partial order on X.

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 .

Let be a chain 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

is irreflexive,

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

Let such that iff .

As is defined as a union of sets, there exists

such that .

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

  1. {{#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 }}