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.
 A: 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$. 
A: 
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$ and $\beta=\delta+n$ then $\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.
A: 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$.  
A: 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.
