Induction is the name given to a certain kind of proof, and also to a (related) way of defining a function. For a proof, the statement to be proved has a suitably ordered set of cases. Some cases (usually one, but possibly zero or more than one), are proved separately, and the other cases are deduced from those. The deduction goes by contradiction, as we shall see. For a function, its domain is suitably ordered. The function is first defined on some (usually nonempty) subset of its domain, and is then defined at other points in terms of its values at points such that .
1 Elementary proof by induction
Proof by induction is a variety of proof by contradiction, relying, in the elementary cases, on the fact that every non-empty set of natural numbers has a least element. Suppose we want to prove a statement which involves a natural number . It is enough to prove:
1) If , and is true for all such that , then is true.
or, what is the same thing,
2) If is false, then is false for some .
To see why, assume that is false for some . Then there is a smallest such that is false. Then, by hypothesis, is true for all . By (1), is true, which is a contradiction.
(If we don’t regard induction as a kind of proof by contradiction, then we have to think of it as supplying some kind of sequence of proofs, of unlimited length. That’s not very satisfactory, particularly for transfinite inductions, which we will get to below.)
Usually the initial case of , and sometimes a few cases, need to be proved separately, as in the following example. Write . We claim
Let us try to apply (1). We have the inductive hypothesis (as it is called)
which tells us something if . In particular, setting ,
Now we just add to each side, and verify that the right side becomes . This proves (1) for nonzero . But if , the inductive hypothesis is vacuously true, but of no use. So we need to prove separately, which in this case is trivial.
Textbooks sometimes distinguish between weak and strong (or complete) inductive proofs. A proof that relies on the inductive hypothesis (1) is said to go by strong induction. But in the sum-of-squares formula above, we needed only the hypothesis , not for all . For another example, a proof about the Fibonacci sequence might use just and . An argument using only is referred to as weak induction.
2 Definition of a function by induction
Let’s begin with an example, the function , , where is some integer . The inductive definition reads
Formally, such a definition requires some justification, which runs roughly as follows. Let be the set of for which the following definition “has no problem”.
We now have a finite sequence on the interval , for each . We verify that any and have the same values throughout the intersection of their two domains. Thus we can define a single function on the union of the various domains. Now suppose , and let be the least element of . That means that the definition has a problem when but not when . We soon get a contradiction, so we deduce . That means that the union of those domains is all of , i.e. the function is defined, unambiguously, throughout .
Another inductively defined function is the Fibonacci sequence, q.v.
We have been speaking of the inductive definition of a function, rather than just a sequence (a function on ), because the notions extend with little change to transfinite inductions. An illustration par excellence of inductive proofs and definitions is Conway’s theory of surreal numbers. The numbers and their algebraic laws of composition are defined entirely by inductions which have no special starting cases.
3 Minor variations of the method
The reader can figure out what is meant by “induction starting at ”, where is not necessarily zero. Likewise, the term “downward induction” is self-explanatory.
A common variation of the method is proof by induction on a function of the index . Rather than spell it out formally, let me just give an example. Let be a positive integer having no prime factors of the form . Then for some integers and . The usual textbook proof uses induction on a function of , namely the number of prime factors of . The induction starts at (i.e. either or prime ), which in this instance is the only part of the proof that is not quite easy.
4 Well-ordered sets
An ordered set is said to be well-ordered if any nonempty subset of has a least element. The criterion (1), and its proof, hold without change for any well-ordered set in place of (which is a well-ordered set). But notice that it won’t be enough to prove that implies (where denotes the least element , if it exists). The reason is, given an element , there may exist elements but no element such that . Then the induction from to will fail to “reach” . For more on this topic, look for “limit ordinals”.
Informally, any variety of induction which works for ordered sets in which a segment may be infinite, is called “transfinite induction”.
5 Noetherian induction
An ordered set , or its order, is called Noetherian if any non-empty subset of has a maximal element. Several equivalent definitions are possible, such as the “ascending chain condition”: any strictly increasing sequence of elements of is finite. The following result is easily proved by contradiction.
Principle of Noetherian induction: Let be a set with a Noetherian order, and let be a subset of having this property: if is such that the condition implies , then . Then .
So, to prove something “” about every element of a Noetherian set, it is enough to prove that “ for all ” implies “”. This time the induction is going downward, but of course that is only a matter of notation. The opposite of a Noetherian order, i.e. an order in which any strictly decreasing sequence is finite, is also in use; it is called a partial well-order, or an ordered set having no infinite antichain.
6 Inductive ordered sets
An ordered set is said to be inductive if any totally ordered subset of has an upper bound in . Since the empty set is totally ordered, any inductive ordered set is non-empty. We have this important result:
Zorn’s lemma: Any inductive ordered set has a maximal element.
Zorn’s lemma is widely used in existence proofs, rather than in proofs of a property of an arbitrary element of an ordered set. Let me sketch one typical application. We claim that every vector space has a basis. First, we prove that if a free subset , of a vector space , is a maximal free subset (with respect to the order relation ), then it is a basis. Next, to see that the set of free subsets is inductive, it is enough to verify that the union of any totally ordered set of free subsets is free, because that union is an upper bound on the totally ordered set. Last, we apply Zorn’s lemma to conclude that has a maximal free subset.
|Date of creation||2013-03-22 12:24:27|
|Last modified on||2013-03-22 12:24:27|
|Last modified by||Daume (40)|