Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

3 Answers 3

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.

share|improve this answer
add comment

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$.

share|improve this answer
    
Oh yeah, this one is an instant classic! –  Asaf Karagila Feb 14 '13 at 4:12
3  
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
add comment

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$.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.