A partially ordered set or poset is a pair where is a set and is a relation on satisfying:
Write for and . Alternatively in terms of , , and implies .
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.
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.
An antichain is a subset in which no two distinct elements are comparable. , neither nor .
For and , say is an upper bound for if .
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 .
A poset is complete if every set has a supremum.
Every complete poset has a greatest element, and a least element .
A function , a poset, is monotone or order preserving if implies .
a complete poset, order preserving. Then has a fixed point.
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 .
have injections and then biject.
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.
A (non-empty) poset is chain-complete if every non-empty chain has a supremum.
Not all functions on chain-complete posets have fixed points. Any function on an anti-chain is order preserving.
The non-empty condition is a little pedantic but necessary.
is inflationary if .
Not necessarily related to order preserving.
is a chain-complete poset, inflationary. Then has a fixed point.
Fix . Say closed if
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 .
If then
as is normal.
If then
.
If
then
So .
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:
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.
``Now forget the proof'' - Dr Leader
Given a poset an element is maximal if no has .
Every chain-complete poset has a maximal element.
Very non-obvious theorem which trivially implies Bourbaki-Witt ( maximal implies ).
Let be any poset and let be the collection of all chains of ordered by inclusion. Then is chain complete.
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.
Every poset has a maximal chain.
Let be a (non-empty) poset in which every chain has an upper bound. Then has a maximal element.
Non-emptiness actually not needed as it follows from the condition that every chain has an upper bound.
Every vector space has a basis.
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.
Let for any . Then consistent implies has a model.
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.
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.
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