<logic> A powerful technique for proving that a theorem holds for all cases in a large or infinite well-ordered sets. The proof has two steps, the basis and induction step. Roughly, in the basis the theorem is proved to hold for the "ancestor" case, and in the induction step it is proved to hold for all "descendant" cases.
Example: if S is a well-ordered set with ordering "<", and we want to show that a property P holds for every element of S, it is sufficient to show that, for all s in S,
IF for all t in S, t < s => P(t) THEN P(s)I.e. if P holds for anything less than s then it holds for s. In this case we say P is proved by induction.
The most common instance of proof by induction is induction over the natural numbers where we prove that some property holds for n=0 and that if it holds for n, it holds for n+1.
(In fact it is sufficient for "<" to be a well-founded partial order on S, not necessarily a well-ordering of S.)
For a more precise definition, see sub-items below.
Basis
Proof that the theorem in question holds for the minimal case. Induction hypothesis
Assumption that the theorem in question holds (in weak mathematical
induction) for an arbitrary case k, or that it holds (in strong mathematical induction) for all cases up to and including k. Induction step
Proof that if the induction hypothesis is true, then the theorem in question holds for case k+1.
Strong and weak mathematical induction
Two versions of the induction hypothesis (see above).
[Glossary of First-Order Logic] and [FOLDOC]
Try this search on OneLook / Google