3Posets and Zorn's lemma
II Logic and Set Theory
3.3 Bourbaki-Witt theorem*
Finally, we’ll quickly present a second (non-examinable) fixed-point theorem.
This time, we are concerned about chain-complete posets and inflationary
functions.
Definition (Chain-complete poset). We say a poset
X
is chain-complete if
X = ∅ and every non-empty chain has a supremum.
Example.
– Every complete poset is chain-complete.
–
Any finite (non-empty) poset is chain complete, since every chain is finite
and has a greatest element.
– {A ⊆ V
:
A is linearly independent}
for any vector space
V
is chain-
complete, as shown in the proof that every vector space has a basis.
Definition (Inflationary function). A function
f
:
X → X
is inflationary if
f(x) ≥ x for all x.
Theorem (Bourbaki-Witt theorem). If
X
is chain-complete and
f
:
X → X
is
inflationary, then f has a fixed point.
This is follows instantly from Zorn’s, since
X
has a maximal element
x
, and
since
f
(
x
)
≥ x
, we must have
f
(
x
) =
x
. However, we can prove Bourbaki-Witt
without choice. In the proof of Zorn’s, we had to “pick” and
x
1
> x
0
. Here, we
can simply let
x
0
f
7−→ x
1
f
7−→ x
2
f
7−→ x
3
···
Since each chain has a supremum instead of an upper bound, we also don’t need
Choice to pick our favorite upper bound of each chain.
Then we can do the same proof as Zorn’s to find a fixed point.
We can view this as the “AC-free” part of Zorn’s. It can be used to prove
Zorn’s lemma, but the proof is totally magic.