3Posets and Zorn's lemma
II Logic and Set Theory
3.2 Zorn’s lemma and axiom of choice
Recall that in the proof of Zorn’s, we picked
x
, then picked
x
′
, then picked
x
′′
,
ad infinitum. Here we are making arbitrary choices of
x
′
. In particular, we have
made infinitely many arbitrary choices.
We did the same in IA Numbers and Sets, when proving a countable union
of countable sets is countable, because we chose, for each
A
n
, a listing of
A
n
,
and then count them diagonally. We needed to make a choice because each
A
n
has a lot of possible listings, and we have to pick exactly one.
In terms of “rules for producing sets”, we are appealing to the axiom of choice,
which states that you can pick an element of each
A
i
whenever
{A
i
:
i ∈ I}
is a
family of non-empty sets. Formally,
Axiom (Axiom of choice). Given any family
{A
i
:
i ∈ I}
of non-empty sets,
there is a choice function f : i →
S
A
i
such that f(i) ∈ A
i
.
This is of a different character from the other set-building rules (e.g. unions
and power sets exist). The difference is that the other rules are concrete. We
know exactly what
A ∪ B
is, and there is only one possible candidate for what
A ∪ B
might be. “Union” uniquely specifies what it produces. However, the
choice function is not.
{A
i
:
i ∈ I}
can have many choice functions, and the
axiom of choice does not give us a solid, explicit choice function. We say the
axiom of choice is non-constructive.
We are not saying that it’s wrong, but it’s weird. For this reason, it is often
of interest to ask “Did I use AC?” and “Do I need AC?”.
(It is important to note that the Axiom of Choice is needed only to make
infinite choices. It is trivially true if
|I|
= 1, since
A
=
∅
by definition means
∃x ∈ A. We can also do it for two sets. Similarly, for |I| finite, we can do it by
induction. However, in general, AC is required to make infinite choices, i.e. it
cannot be deduced from the other axioms of set theory)
In the proof of Zorn’s we used Choice. However, do we need it? Is it possible
to prove it without Choice?
The answer is it is necessary, since we can deduce AC from Zorn’s. In other
words, we can write down a proof of AC from Zorn’s, using only the other
set-building rules.
Theorem. Zorn’s Lemma ⇔ Axiom of choice.
As in the past uses of Zorn’s lemma, we have a big scary choice function to
produce. We know that we can do it for small cases, such as when
|I|
= 1. So we
start with small attempts and show that the maximal attempt is what we want.
Proof.
We have already proved that AC
⇒
Zorn. We now proved the other way
round.
Given a family
{A
i
:
i ∈ I}
of non-empty sets. We say a partial choice
function is a function
f
:
J →
S
i∈I
A
i
(for some
J ⊆ I
) such that
f
(
j
)
∈ A
for
all j ∈ J.
Let
X
=
{
(
J, f
) :
f is a partial choice function with domain J}
. We order
by extension, i.e. (
J, f
)
≤
(
J
′
, f
′
) iff
J ⊆ J
′
and
f
′
agrees with
f
when both are
defined.
Given a chain
{
(
J
k
, f
k
) :
k ∈ K}
, we have an upper bound
(
S
J
k
,
S
f
k
)
, ie
the function obtained by combining all functions in the chain. So by Zorn’s, it
has a maximal element (J, f ).
Suppose
J
=
I
. Then pick
i ∈ I \ J
. Then pick
x ∈ A
i
. Set
J
′
=
J ∪ {i}
and
f
′
=
f ∪ {
(
i, x
)
}
. Then this is greater than (
J, f
). This contradicts the
maximality of (
J, f
). So we must have
J
=
I
, i.e.
f
is a full choice function.
We have shown that Zorn’s lemma is equivalent to the Axiom of Choice.
There is a third statement that is also equivalent to both of these:
Theorem (Well-ordering theorem). Axiom of choice
⇒
every set
X
can be
well-ordered.
This might be very surprising at first for, say
X
=
R
, since there is no obvious
way we can well-order
R
. However, it is much less surprising given Hartogs’
lemma, since Hartogs’ lemma says that there is a (well-ordered) ordinal even
bigger than R. So well-ordering R shouldn’t be hard.
Proof.
The idea is to pick an element from
X
and call it the first; pick another
element and call it the second, and continue transfinitely until we pick everything.
For each
A ⊆ X
with
A
=
X
, we let
y
A
be an element of
X \A
. Here we are
using Choice to pick out y
A
.
Define
x
α
recursively: Having defined
x
β
for all
β < α
, if
{x
β
:
β < α}
=
X
,
then stop. Otherwise, set
x
α
=
y
{x
β
:β<α}
, ie pick
x
α
to be something not yet
chosen.
We must stop at some time. Otherwise, we have injected
γ
(
X
) (ie the ordinal
larger than
X
) into
X
, which is a contradiction. So when stop, we have bijected
X
with an well-ordered set (i.e.
I
α
, where
α
is when you’ve stopped). Hence we
have well-ordered X.
Did we need AC? Yes, trivially.
Theorem. Well-ordering theorem ⇒ Axiom of Choice.
Proof.
Given non-empty sets
{A
i
:
i ∈ I}
, well-order
S
A
i
. Then define
f
(
i
) to
be the least element of A
i
.
Our conclusion is:
Axiom of Choice ⇔ Zorn’s lemma ⇔ Well-ordering theorem.
Before we end, we need to do a small sanity check: we showed that these three
statements are equivalents using a lot of ordinal theory. Our proofs above make
sense only if we did not use AC when building our ordinal theory. Fortunately,
we did not, apart from the remark that
ω
1
is not a countable supremum — which
used the fact that a countable union of countable sets is countable.