Category: Maths

Cantor never bores (1)

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

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

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

Suppose [tex]U[/tex] is uncountable, then there exists a [tex]\star \in U \backslash M[/tex]. [tex]M \cup \{\star\}[/tex] is most definitely also countable and [tex]M \subset M \cup \{\star\}[/tex] which contradicts [tex]M[/tex]’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 [tex]\mathbb Q[/tex] without the empty set and [tex]\mathbb Q[/tex] itself. These downsets correspond to real numbers, see Dedekind Cuts.

Aperitif for order

Assign 1 to True and 0 to False. Now the minimum corresponds to “and” and maximum to “or”. If you give it a bit more though, less or equal to corresponds to implication. This is a lot more general than this specific case. Add .5 for a third value (eg. NULL) and it still yields natural results.

We can recognize the behaviour of minima and maxima in a lot of other things. Take for instance set inclusion as order with intersection as minimum and union as maximum. Actually, the link between general order and set inclusion is frequently made to then propose that “intersection of two set of cases” and “logical and” do look a lot alike.

This is just the tip of the huge iceberg. Order appears everywhere! Everywhere in Math. Everywhere in CS. And its just recognizing simple order I’ve demonstrated. Other useful concepts in order theory that I didn’t even touch are Galois Connections and formal concept analysis.

Oh, another example of an order are integers with bitwise or and bitwise and. It is left as an exercise to the reader when one integer is greater than another.

Interested? Buy an Introduction to Lattices and Order.