Let's look at a more specific example. You may have wondered how many lines there are in a truth table with n atomic sentence letters. The answer is 2". But how do we prove that this answer is correct, that for all n, an n-letter truth table has 2" lines? If n = 1, that is, if there is just one sentence letter in a truth table, then the number of lines is 2 = 2'. So the generalization holds for the first case. This is called the Basis Step of the induction. We then need to do what is called the Inductive Step. We assume that the generalization holds for n. This assumption is called the Inductive Hy$othesis. Then, using the inductive hypothesis, we show that the generalization holds for n + 1. So let's assume (inductive hypothesis) that in an n-letter truth table there are 2" lines. How many lines are there in a truth table obtained by adding one more letter? Suppose our new letter is 'A'. 'A' can be either true or false. The first two lines of the n + 1 letter truth table will be the first line of the n-letter table plus the specification that 'A' is true, followed by the first line of the n-letter table plus the specification that 'A' is false. The next two lines of the new table will be the second line of the old table, similarly extended with the two possible truth values of 'A'. In general, each line of the old table will give rise to two lines of the new table. So the new table has twice the lines of the old table, or 2" x 2 = 2"+ l. This is what we needed to show in the inductive step of the argument. We have shown that there are 2" lines of an n-letter truth table when n = 1 (basis step). We have shown that if an n-letter table has 2" lines, then an n + 1 letter table has 2"+' lines. Our generalization is true for n = 1, and if it is true for any arbitrarily chosen n, then it is true for n + 1. The princple of mathematical induction then tells us we may conclude that it is true for all n. We will express this principle generally with the idea of an Inductive Property. An inductive property is, strictly speaking, a property of integers. In an inductive argument we show that the integer 1 has the inductive property, and that for each integer n, if n has the inductive property, then the integer n + 1 has the inductive property. Induction then licenses us to conclude that all integers, n, have the inductive property. In the last example, All n Ltter truth tubb have exact4 2" lines, a proposition about the integer n, was our inductive property. To speak generally, I will use 'P(n)' to talk about whatever inductive property might be in question:
Principle of Weak Induction
- Let \(P(n)\) be some property which can be claimed to hold for (is defined for) the integers, n = 1, 2, 3, . . . (the Inductive Property).
- Suppose we have proved \(P(l)\) (Basis Step).
- Suppose we have proved, for any n, that if P(n), then P(n + 1) (IndzLchue Skp, with the assumption of P(n), the Inductive Hypothesis).
- Then you may conclude that \(P(n)\) holds for all \(n\) from 1 on.
- If in the basis step we have proved \(P(i)\), we may conclude that \(P(n)\) holds for \(n = i, i + 1, i + 2, \ldots\).
(e) simply says that our induction can really start from any integer, as long as the inductive property is defined from that integer onward. Often it is convenient to start from 0 instead of from 1, showing that P(n) holds for n = 0,1,2,. . . .
Most of the inductions we will do involve facts about sentences. To get you started, here is a simple example. The conclusion is so obvious that, ordinarily, we would not stop explicitly to prove it. But it provides a nice illustration and, incidentally, illustrates the fact that many of the generalizations which seem obvious to us really depend on mathematical induction. Let's prove that if the only kind of connective which occurs in a sentence logic sentence is '-', then there is a truth value assignment under which the sentence is true and another in which it is false. (For short, we'll say that the sentence "can be either true or false.") Our inductive property will be: All sentences with n occurrences of '-' and no other connectives can be either true or false. A standard way of expressing an important element here is to say that we will be doing the induction on th number of connectives, a strategy for which you will have frequent use. We restrict attention to sentences, X, in which no connectives other than '-' occur. Suppose (basis case, with n = 0) that X has no occurrences of '-'. Then X is an atomic sentence letter which can be assigned either t or f. Suppose (inductive hypothesis for the inductive step) that all sentences with exactly n occurrences of '-' can be either true or false. Let Y be an arbitrary sentences with n + 1 occurrences of '-'. Then Y has the form -X, where X has exactly n occurrences of '-'. By the inductive hypothesis, X can be either true or false. In these two cases, -X, that is, Y, is, respectively, false and true. Since Y can be any sentence with n + 1 occurrences of '-', we have shown that the inductive property holds for n + 1, completing the inductive argument. 172 Mathematied Induction 11 -3. Strong Induction 173 EXERCISES 11-1. By a Restricted Conjunctive Sentence, I mean one which is either an atomic sentence or is a conjunction of an atomic sentence with another restricted conjunctive sentence. Thus the sentences 'A' and '[C&(A&B)]&D' are restricted conjunctive sentences. The sentence 'A &[(C&D)&(H&G)]' is not, because the component, '(C&D)&(H&G)', fails to be a conjunction one of the components of which is an atomic sentence letter.
Here is a rigorous definition of this kind of sentence:
- Any atomic sentence letter is a restricted conjunctive sentence.
- Any atomic sentence letter conjoined with another restricted conjunctive sentence is again a restricted conjunctive sentence.
- Only such sentences are restricted conjunctive sentences. Such a definition is called an Inductive Definition. Use weak induction to prove that a restricted conjunctive sentence is true iff all the atomic sentence letters appearing in it are true. 11-2. Prove that the formula is correct for all n.