Examples of inductive proofs that can be generalized by transfinite induction

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 1

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.

Answer 2

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

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

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.

Answer 3

Let me give a few examples and a few remarks.

• Every countable ordinal is realized as a Cantor-Bendixon rank of a closed set . The Cantor-Bendixon derivative X' of set X of reals (or in any topological space) is obtained by casting out isolated points. The rank of X is the number of steps required until a set is reached having no isolated points. The integers in R have rank 1; a convergent sequence has rank 2; a convergent sequence of convergent sequences has rank 3, and so on. The finite ranks are easy to construct by induction. One can continue transfinitely to produce a set with any ordinal rank.

• Cantor's back-and-forth proof that any two countable endless dense linear orders are isomorphic generalizes to the transfinite, for any two structures of size κ having a collection of partial isomorphisms with the <κ back-and-forth property. This idea is related to the model-theoretic notion of saturation, and is a fundamental method in model theory.

Your question asks for examples of finite induction that extend to the transfinite but do not trivialize when doing so. But perhaps a more common situation with transfinite induction is the dual situation, where an argument that is trivial for finite instances, but becomes nontrivial in the transfinite. For example:

• Every countable well ordering embeds into the rational order. This is trivial for finite orders, but can be proved for countable ordinals by transfinite induction. (But actually, one can prove generally that any countable linear order embeds into Q, building the embedding by finite recursion on the enumeration of the order.)

• Every well ordering is rigid, in the sense that it has no nontrivial order automorphisms. This is trivial for finite orders, but can be proved by transfinite induction by looking at the least element to be moved.

• More generally, every transitive set is rigid. This and many other arguments in set theory proceed by proving that there can be no ∈ minimal counterexample, and such arguments can be viewed as proofs by transfinite induction on the Levy rank of the set.

Finally, let me make a distinction between using mathematical induction to prove a statement, and using mathematical recursion to carry out a mathematical construction. The difference is that the result of recursion is a mathematical object, rather than a proof of a statement. Many finite recursions extend naturally into the transfinite.

• The construction of the collection HF of all hereditary finite sets proceeds by starting with the empty set, and iterating the power set operation. The transfinite continuation of this simply collects everything together with a union at limit stages, and continues taking the power set at limit stages. The result is the Levy hierarchy V_α of all sets (or of all well-founded sets).

• One can iteratively add one to finite numbers, to get the next larger cardinal number. Continuing transfinitely, one produces the transfinite cardinals Aleph_α. Similarly, the cardinals Beth_α result from iterating the exponential operation Beth_α+1 = 2^Beth_α.

• There are many others.

Answer 4

One way to prove the general Van Kampen Theorem is to prove it first for coverings by finitely many open sets, and then generalize to the arbitrarily large coverings using transfinite induction. Whether this is simpler than Hatcher's direct argument for arbitrary coverings (Theorem 1.20 in his Algebraic Topology book) is probably a matter of taste.

Answer 5

Determinacy for $\Delta^0_1$-games in Baire space is naturally proven by transfinite induction (over the (rank of the) well-founded tree describing the $\Delta^0_1$-winning set and its complement). This generalizes the backwards-induction argument for finite sequential games having subgame-perfect equilibria.