Cantor's proof and Zorn's lemma

Question

In Cantor's proof, that the real numbers are uncountable he uses the fact that, we are able to always construct an element which doesn't belong to the given list of numbers.

What if we add those numbers one after another and kept doing that.Notice that the lists create partially ordered set with inclusion as comparator. Any chain has an upper bound which is the union of all lists in that chain. So according to Zorn's lemma there should exist a maximal element(list), which is the list that we are looking for.

Obviously there is a problem with my reasoning, but I don't understand where is it. Can anyone show me the pitfall of my reasoning?

Answer 1

Your partial order $\mathbb{P}$ is (something like) countable subsets of $\mathbb{R}$, ordered by inclusion. You are right that, if $\mathbb{P}$ has a maximal element, then $\mathbb{R}$ is countable.

So does $\mathbb{P}$ have a maximal element? Well, by Zorn's Lemma it would ... if every chain in $\mathbb{P}$ had an upper bound. Here you write

Any chain has an upper bound which is the union of all lists in that chain.

But this isn't true! The union of a chain in $\mathbb{P}$ is a set of reals, but not necessarily a countable set of reals - and $\mathbb{P}$ only contains countable sets of reals. So the union of a chain in $\mathbb{P}$ need not be an element of $\mathbb{P}$.

The union of a countable chain in $\mathbb{P}$ will indeed be an element of $\mathbb{P}$ - but not every chain in $\mathbb{P}$ is countable, and Zorn's Lemma needs every chain to have an upper bound in the poset.

Answer 2

There are two problems here.

1. You think about countable subsets, because the diagonal argument is working only on countable sets. But a countable set is not a list, which is the enumeration as well. Increasing the list means working with countable ordinals, rather than functions from $\Bbb N$, otherwise you cannot extend anything because a list is a function with domain $\Bbb N$... so how you're going to extend it?

   Once you only work with countable sets, then your argument fails for the same reason that $\Bbb R$ is not finite. Look at the set of finite sets of reals, there every finite chain has an upper bound, but the every chain. There are certainly infinite chains without upper bounds.

   You could ask what would happen if we require that every chain is countable and has an upper bound. Well, this is certainly consistent without the axiom of choice. But this can only happen in models where the axiom of choice fails, and therefore Zorn's lemma is no longer applicable.

2. Even if you somehow could extend the diagonalization argument beyond $\Bbb N$ and work with the ordinals and not the natural numbers (this is doable under things like Martin's Axiom, which can be thought of as a form of extended diagonalization), you still have a chain without an upper bound: well-order the reals in the least order type possible, and look at the initial segments of this order. These define a chain of "small list" without an upper bound.