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.