mathematical induction a method of definition and a method of proof. A collection of objects can be defined inductively. All members of such a collection can be shown to have a property by an inductive proof. The natural numbers and the set of well-formed formulas of a formal language are familiar examples of sets given by inductive definition. Thus, the set of natural numbers is inductively defined as the smallest set, N, such that: (B) 0 is in N and (I) for any x in N the successor of x is in N. (B) is the basic clause and (I) the inductive clause of this definition. Or consider a propositional language built on negation and conjunction. We start with a denumerable class of atomic sentence symbols ATOM = {A1, A2, . . .}. Then we can define the set of well-formed formulas, WFF, as the smallest set of expressions such that: (B) every member of ATOM is in WFF and (I) if x is in WFF then (- x) is in WFF and if x and y are in WFF then (x & y) is in WFF. We show that all members of an inductively defined set have a property by showing that the members specified by the basis have that property and that the property is preserved by the induction. For example, we show that all WFFs have an even number of parentheses by showing (i) that all ATOMs have an even number of parentheses and (ii) that if x and y have an even number of parentheses then so do (- x) and (x & y). This shows that the set of WFFs with an even number of parentheses satisfies (B) and (I). The set of WFF s with an even number of parentheses must then be identical to WFF, since – by definition – WFF is the smallest set that satisfies (B) and (I). Ordinary proof by mathematical induction shows that all the natural numbers, or all members of some set with the order type of the natural numbers, share a property. Proof by transfinite induction, a more general form of proof by mathematical induction, shows that all members of some well-ordered set have a certain property. A set is well-ordered if and only if every non-empty subset of it has a least element. The natural numbers are well-ordered. It is a consequence of the axiom of choice that every set can be well-ordered. Suppose that a set, X, is well-ordered and that P is the subset of X whose members have the property of interest. Suppose that it can be shown for any element x of X, if all members of X less that x are in P, then so is x. Then it follows by transfinite induction that all members of X have the property, that X % P. For if X did not coincide with P, then the set of elements of x not in P would be non-empty. Since X is well-ordered, this set would have a least element, x*. But then by definition, all members of X less than x* are in P, and by hypothesis x* must be in P after all.
See also INDUCTION , PHILOSOPHY OF MATHEMATICS , PROOF THEORY. B.Sk.