Euler, Erdős

It's about time I write on a non-Euler topic -- the birth of ordinals. I've been reading Georg Cantor's Contributions to the Founding of the Theory of Transfinite Numbers. In two papers published in 1895 and 1897, Cantor creates the theory of cardinals and ordinals from the ground up. The memoir is a rather good read since it assume no prior knowledge of set-theory on part of the reader; in fact, set theory had not even been properly formed at this time. Unfortunately, since it is a foundational text (if that makes any sense), you get the feeling he's forming all this great ideas out of thin air. This post documents my journey to convince myself how ideas of ordinal numbers can arise naturally when studying point-sets, specifically, sets of real numbers.

I will assume some familiarity with topology and countability. Here are the important definitions:

Definition 1. Let \(S \subset \mathbb{R}\). A point \(x \in \mathbb R\) is called a limit point of \(S\) if for every interval \((x-\epsilon, x+\epsilon)\), \[ (x-\epsilon, x+\epsilon) \cap S \] has infinitely many elements.

A point \(x \in S\) is called an isolated point of \(S\) if it is not a limit point of \(S\).

Definition 2. Let \(S\) be a set. \(S\) is said to be countable if there exist an injective function \(f\colon S\rightarrow\mathbb N\). Otherwise the set is called uncountable.

It follows from this definition that:

1. if \(T\) is countable and there is an injective map from \(S \rightarrow T\), then \(S\) is countable.
2. if \(S\) is countable, then all its elements can be ordered as: \( s_1\prec s_2 \prec s_3 \prec \cdots \prec s_n \prec \cdots\)
3. \(\mathbb Q\), the set of rationals, is countable.
4. if \(S\) is uncountable and \(T\) are countable, then \(S\setminus T\) is uncountable.

The second fact relies on the well-ordering principle of natural numbers. Now we can start proving the interesting stuff:

Theorem 3. Any set of isolated points is countable.

Proof: Suppose every point of \(S\) is an isolated point of \(S\). Then for every point \(x \in S\), there is an interval \( I_x = \left(x-\frac{\epsilon}{2}, x+\frac{\epsilon}{2}\right)\) such that each of these intervals are pairwise disjoint and \[ (x-\epsilon,x+\epsilon) \cap S = {x} \] Since \(\mathbb Q\) is countable, then we can order the set of rationals like \(q_1 \prec q_2 \prec q_3 \prec \cdots\). With this new order on rationals, we say \(q_i\) is less than \(q_j\) if \(i < j\). Every interval \(I_x\) contains rational numbers; therefore, we can map each \(x \in S\) to the “least” rational number contained in its interval \(I_x\). This mapping is injective because all \(I_x\) are disjoint. By fact \((1)\) above, \(S\) is countable. \(\Box\)

Note: Noticed how I claimed every interval \(I_x\) contains rational numbers? This is known as the density of rational numbers in \(\mathbb R\). To Cantor, this fact was obvious since he defined the real numbers as the set of equivalence classes of Cauchy sequences (he called them fundamental series) on rationals. You can read more by searching the Arithmetization of Real Numbers.

Definition 4. For any set \(S \subset \mathbb R\), the set \[ S' = {x \in \mathbb R : x \text{ is a limit point in S} } \] is known as the derived set of \(S\).

Corollary 5. If \(S \subset \mathbb R\) is uncountable, then \(S'\) is uncountable and \(S\setminus S'\) is countable.

This follows from fact \((4)\) and the theorem. Note that \(S\setminus S'\) is the set of isolated points of \(S\).

Corollary 6. If \(T = S'\) for some set \(S\), then \(T' \subset T\).

To prove this, simply apply the definition of limit points twice. This sets us up for the next definition:

Definition 7. A set \(S \subset \mathbb R\) is called perfect if \(S' = S\).

Historical note: Nearly every definition I've given thus far is due to ideas by Cantor. Cantor defined want it meant to be countable and famously proved that real numbers were uncountable. While Cantor was not the first to define a limit-point (Weierstrass mentioned it in unpublished lectures), he was the first to study and publish them. He also defined derived and perfect sets. That is why he is considered one of the two fathers of point-set topology. The other father is of course Felix Hausdorff.

So if \(S'\) is uncountable, then \(\left(S'\right)' \subset S'\) is uncountable, so on and so forth. Intuitively, we would expect with “enough” application of derived sets, we'd be left with a perfect set since we are removing countable isolated points with each step.

Definition 8. For any set \(S \subset \mathbb R\), let \(S^{(1)} = S'\) and \(S^{(n+1)} = \left(S^{(n)}\right)'\) for \(n\in \mathbb N\). Lastly, \[ S^{(\infty)} = \bigcap_{n \in \mathbb N} S^{(n)} \]

So is it possible that \(S^{(\infty)}\) to have isolated points? My first naive guess was that the set would be perfect (and possibly empty). I tried to prove this for a whole day, but eventually, I started to doubt myself. So I worked to find a good counterexample.

Ideally, I wanted a set, \(S\), whose derived set is the same set we get if we mapped for every \(x\in S\), \(x \mapsto \frac{x}{2}\). So if \(0 \in S\) and \(S\) is bounded, then \(S^{(\infty)} = {0}\) by the Archimedean property. This led to the following neat fractal.

Theorem 9. Let \[ S = \left\{ 2^{1-i} \sum_{m \in M_i} 2^{-m} : M_i \subset \mathbb N ~and~ |M_i| = i \in \mathbb N \right\} \cup \{0\} \] Then \(S^{(\infty)} = \{0\}\).

This is easy to see by looking at the binary representation of the elements in this set. So knowing \(S^{(\infty)}\) is not enough to get rid of all isolated points, where do we go from here? Ordinal numbers.

To be continued...

References

Cantor, Georg. Contributions to the Founding of the Theory of Transfinite Numbers. Trans. Philip Jourdain. New York: Dover Publications, 1954. Web.