## Cantor never bores (1)

Given a set of countable sets $$K$$, such that $$K$$ is totally ordered by inclusion, videlicet for every $$A,B\in K$$ either $$A\subseteq B$$ or $$A\supseteq B$$. Intuitively, for at every step in this chain one element at least must be added, one expects the set $$K$$ to be countable as well.

Suppose $$K$$ is countable. Then the union, $$\bigcup K$$ is a countable union of countable sets, hence countable. (Suppose $$k: \mathbb N \to K$$ is an enumeration of $$K$$ and $$f_i: \mathbb N \to k(i)$$ enumerations of the elements of the chain. Then $$f_0(0), f_1(0), f_0(1), f_2(0), f_1(1), f_0(2), \ldots$$ enumerates $$\bigcup K$$.)

Thus $$\bigcup K$$ is an upper bound of $$K$$. In the poset of countable subsets of some set $$U$$, of which $$\bigcup K$$ is a subset, every non-empty chain has an upper bound. Hence, using Zorn’s lemma there is a maximal element, say $$M$$.

Suppose $$U$$ is uncountable, then there exists a $$\star \in U \backslash M$$. $$M \cup \{\star\}$$ is most definitely also countable and $$M \subset M \cup \{\star\}$$ which contradicts $$M$$’s maximality. We are forced to conclude that there exists an uncountable chain of countable sets.

Cantor’s set theory keeps surprising.

Update: an example of such a chain is the set of the countable ordinals.

Another update: a “more concrete” example are the downsets in $$\mathbb Q$$ without the empty set and $$\mathbb Q$$ itself. These downsets correspond to real numbers, see Dedekind Cuts.