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?



Examples of inductive proofs that can be generalized by transfinite induction
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. 


