# Examples of transfinite induction

I know what transfinite induction is, but not sure how it is used to prove something. Can anyone show how transfinite induction is used to prove something? A simple case is OK.

-
You can find some examples in Chapter 12: Transfinite enumeration of Komjath, Totik: Problems and Theorems in Classical Set Theory. – Martin Sleziak Jan 14 '15 at 9:47
If you are interested in category theory (and in a relatively long read), I have used it a lot of times in my bachelor's thesis, which you can find at the webpage academia.edu/5902060/… – Daniel Robert-Nicoud Oct 7 '15 at 18:49

Every infinite ordinal can be written uniquely as the sum of a limit ordinal and a finite ordinal.

Proof. If $\alpha$ is limit then $\alpha=\alpha+0$; if $\alpha=\beta+1$ then $\beta=\delta+n$ and so $\alpha=\delta+n+1$ where $\delta$ is a limit and $n+1$ is a finite ordinal as wanted. The case where $\alpha=0$ is not needed because this holds vacuously for finite ordinals.

To see that this sum is unique, suppose this is true for $\beta$, let $\alpha=\beta+1$ then $\beta=\delta+n$ and $\alpha=\delta+(n+1)$. If $\alpha=\delta'+k$, where $\delta'$ is a limit ordinal, then $k>0$ because $\alpha$ is a successor and so $\beta=\delta'+(k-1)$. Since this sum is unique for $\beta$ we have $\delta=\delta'$ and $k-1=n$ as wanted. For a limit ordinal this is obvious because $\delta+n$ is not a limit ordinal if $n\neq 0$ so $\alpha=\alpha+0=\delta+n$ implies $n=0$ and $\delta=\alpha$ as wanted.

Other, slightly more interesting perhaps, uses can be found in proving claims about the Borel sets. This is done by transfinite induction on the rank. Other nice options are Goodstein sequences, and every set has a von Neumann rank in ZF.

-
Nice one: (+1) ...can one make this result appear more beautiful as every ordinal represents as such if one accounts zero as limit ordinal, too? – Alexander Frei Jul 31 '15 at 10:46
Is there a typo in the first line of the proof: "if $\alpha=\beta+1$ then $\beta=\delta+n$ and so $\alpha=\delta+n+1$" Shouldn't it read instead: "if $\alpha=\beta+1$ and $\beta=\delta+n$ then so $\alpha=\delta+n+1$" – Alexander Frei Jul 31 '15 at 10:53

Here is one I like. Construction of a "Bernstein set" ... That is a set $E \subseteq \mathbb R$ such that for every uncountable closed set $K$ we have $E \cap K \ne \varnothing$ and $K \setminus E \ne \varnothing$.

The collection $\mathcal K$ of uncountable closed sets has power $\mathfrak c = 2^{\aleph_0}$. Index it as $\mathcal K = \{ K_\xi: \xi < \omega_{\mathfrak c}\}$, where $\omega_{\mathfrak c}$ is the least ordinal of power $\mathfrak c$. Then by transfinite induction choose points $u_\xi$, $v_\xi$, all different, such that $u_\xi, v_\xi \in K_\xi$. This is possible since $K_\xi$ has power $\mathfrak c$, and at each stage fewer than $\mathfrak c$ points have been chosen previously. Then $E = \{u_\xi: \xi < \omega_{\mathfrak c}\}$ is your Bernstein set. Indeed, given any $K \in \mathcal K$, there is $\xi$ so that $K = K_\xi$, and we have $u_\xi \in E \cap K$ and $v_\xi \in K \setminus E$.

-
Oh yeah, this one is an instant classic! – Asaf Karagila Feb 14 '13 at 4:12
That’s a construction by transfinite recursion, not a proof by transfinite induction; it doesn’t answer the question as stated (though it may still be of interest to the OP). – Brian M. Scott Feb 14 '13 at 4:29

I'll give an example of a nice proof by transfinite induction that also uses the idea of cofinality. I'll show that for every countable ordinal, there is a subset of $\mathbb{R}$ of that order type (where we're using the restriction of the usual order on $\mathbb{R}$.

First I'll fix $f:\mathbb{R} \to (0,1)$ an order preserving bijection. You'll see why I use this later.

For the case $\alpha = 0$ the result is clear. For $\alpha = \beta+1$ take $S_\beta \subseteq \mathbb{R}$ with order type $\beta$. Then $f(S_\beta)$ is a subset of $(0,1)$ of order type $\beta$. We then define $S_\alpha = f(S_\beta) \cup \{1\}$. This then has the desired order type. For $\alpha$ limit, as $\alpha$ is countable, we know that there is $\langle \beta_i: i<\omega\rangle$ cofinal in $\alpha$. Then for each $i$ take $S_i$ to be a set with that order type. Then let $S_\alpha = \bigcup\limits_{i \in \omega}i+f(S_i)$, where $i+f(S_i)$ is the translation of $f(S_i)$ by $i$. Then $S_\alpha$ has order type $\alpha$.

-
You can require more, you can require this to be a subset of $\mathbb Q$. – Asaf Karagila Feb 14 '13 at 4:12
Or, more generally, you can show that any countable totally ordered set can be embedded in $\mathbb Q$. Use plain induction, no need for "transfinite". – GEdgar Feb 15 '13 at 15:37
This result is also mentioned in several other posts on MSE. See the following question and other questions linked from/to it: math.stackexchange.com/questions/123969/… – Martin Sleziak Feb 9 '15 at 8:22

Most (all?) applications of Zorn's lemma are examples of transfinite induction, as you can read for example here and here. Therefore, you can prove that every vector space has a basis, that every commutative ring has a maximal ideal, Tychonoff's theorem, etc... always using transfinite induction. However, this is often not really natural.

-