# Posets and Zorn's lemma

Definition 4..1 (Poset)

A partially ordered set or poset is a pair where is a set and is a relation on satisfying:

1. Reflexivity: , .
2. Antisymmetry: if and then , .
3. Transitivity: if and then , .

Write for and . Alternatively in terms of , , and implies .

Example 4..2   , and are posets (in fact total orders).

Example 4..3   where ( means divides ) is not a poset.

Example 4..4   a set. with if .

Definition 4..5 (Hasse diagram)

A Hasse diagram for a poset is a drawing of the points in the poset with an upwards line from to if covers (meaning and ).

Sometimes a Hasse diagram can be drawn for an infinite poset. For example but has an empty Hasse diagram.

Definition 4..6 (Chain)

A chain in a poset is a set that is totally ordered ( have or ).

For example in any subset, like is a chain. Note that a chain need not be countable.

Definition 4..7 (Antichain)

An antichain is a subset in which no two distinct elements are comparable. , neither nor .

Definition 4..8 (Upper bound)

For and , say is an upper bound for if .

Definition 4..9 (Least upper bound, supremum, )

is a least upper bound for if is an upper bound for and every upper bound for satisfies .

Clearly unique if it exists. Write the supremum or join of .

Definition 4..10 (Complete)

A poset is complete if every set has a supremum.

Observation 4..11

Every complete poset has a greatest element, and a least element .

Definition 4..12 (Monotone, order preserving)

A function , a poset, is monotone or order preserving if implies .

Theorem 4..13 (Knaster-Tarski fixed point theorem)

a complete poset, order preserving. Then has a fixed point.

Proof. Let . Possibly .

Claim. If then . Proof. so as order preserving. So .

Let .

Claim. . True if an upper bound for (so ). If , so . But so . So is an upper bound for .

So in by first claim. So but second claim showed so .

Corollary 4..14 (Schröder-Bernstein theorem)

have injections and then biject.

Proof. Want partitions and such that bijects with and bijects with .

Then define obvious bijection by taking on and on .

Set , , , . Consider . complete. Define . . Then is order preserving so it has a fixed point by Knaster-Tarski.

Definition 4..15 (Chain-complete)

A (non-empty) poset is chain-complete if every non-empty chain has a supremum.

Observation 4..16

Not all functions on chain-complete posets have fixed points. Any function on an anti-chain is order preserving.

Observation 4..17

The non-empty condition is a little pedantic but necessary.

Definition 4..18 (Inflationary)

is inflationary if .

Not necessarily related to order preserving.

Theorem 4..19 (Bourbaki-Witt theorem)

is a chain-complete poset, inflationary. Then has a fixed point.

Proof. This proof is like battling Godzilla on a tightrope, it has to be carefully choreographed. Although the theorem seems fairly plausible, it has many big consequences.

Fix . Say closed if

1. implies
2. a non-empty chain in implies .

Note that any intersection of closed sets is closed.

Let is closed. Therefore if then .

Assume is a chain. Let . Then as is closed. Therefore . So . So as inflationary. So done.

Claim. is a chain.

Say is normal if then .

There are two properties of normality we want prove. All are normal. Secondly, it should satisfy the condition we might naturally describe as normal'': if normal then either or .

Once we have done this, we are finished. , or . So is a chain.

Claim. If normal then either or .

Proof of claim. Let or . Will show is closed. Any closed subset of is so closed implies .

1. . ( ).

2. Given we need . So have or and want or .

If then as is normal.
If then .
If then

So .

3. Given a (non-empty) chain , want .

If all have then certainly because a supremum. Otherwise some has and not so as . So . So .

So closed, so closed subset of smallest possible closed set so .

Claim. Every is normal.

Proof of claim. Let is normal . We will show that is closed so .

is closed:

1. No has . So is normal, .

2. Given normal want normal. So must show implies . By first claim implies . So or . So or (because is normal).

3. Given a (non-empty) chain need . That is, we need that if then .

For cannot have (definition of supremum). So some has not , so by the first claim. So ( normal) so certainly .

So closed so . So is a chain.

Observation 4..20

Now forget the proof'' - Dr Leader

Definition 4..21 (Maximal element of a poset)

Given a poset an element is maximal if no has .

Corollary 4..22 (Every chain-complete poset has a maximal element)

Every chain-complete poset has a maximal element.

Observation 4..23

Very non-obvious theorem which trivially implies Bourbaki-Witt ( maximal implies ).

Proof. By contradiction. For each have with . Then the function is inflationary. So it has a fixed point. Contradiction.

Lemma 4..24 (One important chain-complete poset)

Let be any poset and let be the collection of all chains of ordered by inclusion. Then is chain complete.

Proof. Let be a chain in . is a chain in for all . Note that need not be countable. Further or .

Now let . is clearly a least upper bound for . We need to show that it is a chain.

Let . So and . So or . So related. So a chain.

Corollary 4..25 (Kuratowski's lemma)

Every poset has a maximal chain.

Proof. The set of chains of is a chain-complete poset.

Corollary 4..26 (Zorn's lemma)

Let be a (non-empty) poset in which every chain has an upper bound. Then has a maximal element.

Proof. Let be a maximal chain in . Let be an upper bound for . Then is maximal. If then is a chain properly containing . Contradiction.

Observation 4..27

Non-emptiness actually not needed as it follows from the condition that every chain has an upper bound.

Corollary 4..28 (Every vector space has a basis)

Every vector space has a basis.

Proof. Let is linearly independent ordered by inclusion. We seek the existence of maximal element using Zorn's lemma. Then we are done because if does not span it is not maximal.

1. is linearly independent. So . So .

2. Given a chain in we seek an upper bound . Let . Then so we just need (that is, linearly independent).

Suppose for some and not all zero. Have such that contains all the because is a chain. But this contradicts being linearly independent. So . So every chain has an upper bound.

Corollary 4..29 (Completeness theorem for L(P) when the set P of primitive propositions may be uncountable)

Let for any . Then consistent implies has a model.

Proof. Want , that is consistent, with or for all . Then done by setting .

Try to get a maximal consistent . Then for any have or consistent. So satisfies or for all .

Thus let consistent .

We want to use Zorn's lemma to show that has a maximal element.

1. since .

2. Given a non-empty chain in . Seek an upper bound . Let . Then . Just need .

as (and ).

Claim. consistent.

Proof of claim. Suppose . Then have with inconsistent. Have for some . But one of the contains the others because they are in the same chain, call this one . Then is inconsistent which is a contradiction.

So we can apply Zorn's lemma.

Observation 4..30 (Zorn's lemma and the axiom of choice)

In the proof of Zorn's lemma (i.e. more precisely the proof that chain-complete posets have maximal elements) we made an infinite number of arbitrary choices: for each we picked ''. Note that in the IA Numbers and Sets course the axiom of choice was used to simultaneously pick orderings for a countable number of sets.

The axiom of choice says: Given a set and a family of non-empty sets, there is a function such that .

This is different from the other rules that are used to build sets because it claims the existence of an object which is not necessarily specified uniquely.

Therefore it is sometimes interesting to see if a proof depends on the axiom of choice.

Note that the axiom of choice follows from the other axioms for finite sets but not for infinite ones. Furthermore it is not possible to deduce Axiom of Choice for infinite sets from the other axioms(?).

From Zorn's lemma we can deduce the axiom of choice. Given a family , define a partial choice function (PCF) with for some . Order partial choice functions with iff and on . Then the set of all PCFs is a poset on which we can apply Zorn's lemma to find a maximal PCF.

Zorn's lemma was hard to prove because Bourbaki-Witt was hard, not because the Axiom of Choice was used.

Furthermore Zorn's lemma is easy to prove from the Axiom of Choice using well-ordering and ordinals (chapter 6).

John Fremlin 2010-02-17