First a lemma. Let S be a finite ordinal with T ∈ S. We know T is an ordinal, since it belongs to an ordinal. Since S is finite it contains no limit ordinals, hence T is not a limit ordinal. It is 0 or a successor ordinal. If T contains a limit ordinal then so does S by transitivity, so T contains no limit ordinals. Therefore T, an arbitrary member of S, is a finite ordinal.
Let f be a formula with one free parameter. Assume f(successor(S)) is true whenever f(S) is true and S is a finite ordinal. Also let f(0) be true.
Suppose S is a finite ordinal such that f(S) is false. We know S is nonzero, since f(0) is true. Let S be the successor of T. If f(T) is true then f(S) is true, hence there are members of S where f() fails. Restrict S to the elements T such that f(T) fails, and call this new set W. This is a nonempty set of ordinals; let z be the least of these. We know z is nonzero, since f(0) is true. Thus z = successor(y) for some y, and f(y) is true. By the above lemma y is a finite ordinal, and f(y) implies f(successor(y)), hence f(z) is true. This is the inductive step.
we assumed f(S) was false and derived a contradiction. Therefore f(S) is true for all finite ordinals. Induction is valid, and can be used to prove various properties of finite sets, such as the pigeonhole principle.