Question: Hello. I am currently searching for some nice examples of proofs by induction in the finite case, that can be generalized to the infinite case using transfinite induction (and dont become trivial there).

Apparently, the only proof that comes in my mind is that every Vector-Space has a base (mostly this is proven by the Zorn-Lemma, but in the finite case this can be proven by induction, and the same proof can be used in the infinite case with transfinite induction).

Do you have any other examples?

Answer: 
A nice example arises in structural proof theory. You can prove cut-elimination of the sequent calculus for first-order logic by an induction on the size of the cut formula, and the sizes of the proofs you are cutting into and cutting from. By adding rules for induction over the natural numbers, you need transfinite induction up to $\epsilon\_0$ -- but because each rule of the sequent calculus only mentions a principal formula, all the other cases are left untouched in the new proof.
0. In Kaplansky's *Set Theory and Metric Spaces*, he says something like "90% of the time Zorn's Lemma is more natural than transfinite induction. Here is an example of the other 10%." [I don't remember what he proves using transfinite induction -- something about infinite abelian groups, perhaps?]

In my adult mathematical life I have used transfinite induction twice.

1. In

[http://alpha.math.uga.edu/~pete/ellipticded.pdf](http://alpha.math.uga.edu/%7Epete/ellipticded.pdf)

I prove that every abelian group is, up to isomorphism, the Picard group of a ring of functions on some elliptic curve over some field (in particular, of some Dedekind domain). The proof uses transfinite induction. Bjorn Poonen explained to me how to remove transfinite induction from the argument. It seems that Bjorn's modified proof is the first proof of Claborn's theorem (every abelian group is, up to isomorphism, the Picard group of some Dedekind domain) that does not use the Axiom of Choice!

2. To show that if $L/K$ is a purely transcendental extension and $| \ |$ is a non-Archimedean norm on $K$, then it extends to (at least) one non-Archimedean norm $| \ |$
on $L$. This was an exercise in a course I am teaching this semester:

[http://alpha.math.uga.edu/~pete/MATH8410Ex2.3Pete.pdf](http://alpha.math.uga.edu/%7Epete/MATH8410Ex2.3Pete.pdf)

I wrote it up mostly because I wanted to give a worked example of a proof by transfinite induction. Later, one of the students gave a proof using Zorn's Lemma that I thought was faster and simpler.

Thus in my experience, transfinite induction proofs are few, far between, and can probably be recast in other terms. Nevertheless sometimes transfinite induction is what one thinks to do first, and anyway it's fun to prove something in this way every once in a while.