Good resource to learn transfinite induction and/or recursion?

Question

I'm currently reading John H. Conway's On Numbers and Games, but without a good understanding of transfinite induction and/or recursion, progress is very slow.

What's a good resource for learning this topics? I'm looking for something that emphasizes transfinite induction and/or recursion with respect to arbitrary well-founded relations, as opposed to focusing exclusively on well-orderings.

Answer 1

Would it be enough a couple of examples? It seems to me there is no much difference in how to use it from the usual induction on the naturals.

Induction on a transfinite but still well-ordered set $X$

You are proving the proposition $P$ for every $\alpha\in X$. You need to check $P(\alpha_0)$ for the first elements $\alpha_0$ of $X$. And then the induction is completed by showing that if you assume $P(\alpha)$ for every $\alpha<\beta$ then $P(\beta)$.

Exercise (if I am not forgetting something): Show that if the (totally) ordered set $X$ (any cardinality) satisfies induction then every non-empty subset has a first elements. Show the converse too.

Induction on a well-founded set $X$

Let us take an example in which $X$ is still countable, but it doesn't matter too much. Suppose $X$ is indexed by $\mathbb{N}^2$. $X:=\{a_{n,m}\}$, where you order $\mathbb{N}^2$ by the Cartesian order, i.e. $(a,b)\leq(c,b)$ iff $a\leq c$ and $b\leq d$.

You could prove $P$ for all elements of $X$ if you check: 1. $P(a_{0,0})$ 2. $P(a_{n,m})$ implies $P(a_{n+1,m})$ and $P(a_{n,m})$ implies $P(a_{n,m+1})$.

Does this clarifies it? Do you need more concrete examples?

Answer to the question in the comments:

Question 1:

The point $2$ would be better written (and should/could had been written that way too above) "If $P(\alpha,\beta)$ for every $(\alpha,\beta)<(\alpha_0,\beta_0)$ then $P(\alpha_0,\beta_0)$." Remember the how we ordered the pairs. the assumption is, in this case, that is true for $\alpha_<\alpha_0$ and $\beta<\beta_0$.

Question 2:

Example: Suppose we want to define the sequences $a_{n,m}$by:

1. $a_{0,0}=1$
2. $a_{n+1,m}=F(a_{n,m})$
3. $a_{n,m+1}=G(a_{n,m})$. for some functions $F$ and $G$.

It is induction what tells you this sequences are defined for all $\mathbb{N}^2$.

Exercise: Take the proposition $P(n,m)$ to be "a_{n,m} is defined" and prove it by induction as above. (notice that "well defined" here is a different problem since $a_{1,1}$ can be defined using $F(a_{1,0})$ and $G(a_{0,1})$. We are only proving that it can be defined. To get well defined we need to impose more condition on the $F$ and $G$).

Bonus info: Induction over the reals

If $X=[0,\infty)$ and

1. $P(0)$ is true and
2. whenever $P(\alpha)$ is true for every $\alpha<r$ then $P(r)$,

then $P$ is true on all of $X$.

This is equivalent to the nested closed intervals property, Lagrange theorem, Rolle theorem, ...

So, in the same way that almost all probable statements about the naturals can be proven by induction, also almost all (those involving continuity of the reals) probable statements on the reals can be proved by this induction as well.

Answer 2

I haven't seen Conway's book so I don't know if this will be useful. But Ciesielski's "Set theory for the working mathematician" has numerous interesting applications of transfinite induction to set theoretic real analysis. When combined with Hajnal and Hamburger's book, I like to think that this could make a really interesting first course in set theory for undergraduates.