# 11.3: Strong Induction

Learning Objectives

In reviewing this chapter, be sure you understand clearly the following ideas:

1. Weak Induction
2. Inductive Property
3. Basis Step
4. Inductive Hypothesis
5. Inductive Step
6. Induction on the Number of Connectives
7. Strong Formulation of Weak Induction
8. Strong Induction
9. Least Number Principle

Let's drop the restriction in exercise 11-1 and try to use induction to show that any sentence in which '&' is the only connective is true iff all its atomic sentence letters are true. We restrict attention to any sentence logic sentence, X, in which '&' is the only connective, and we do an induction on the number, n, of occurrences of '&'. If n = 0, X is atomic, and is true iff all its atomic sentence letters (namely, itself) are true. Next, let's assume, as inductive hypothesis, that any sentence, X, in which there are exactly n occurrences of '&' is true iff all its atomic sentence letters are true. You should try to use the inductive hypothesis to prove that the same is true of an arbitrary sentence, Y, with n + 1 occurrences of '&'. If you think you succeeded, you must have made a mistake! There is a problem here. Consider, for example, the sentence '(A&B)&(C&D)'. It has three occurrences of '82. We would like to prove that it has the inductive property, relying on the inductive hypothesis that all sentences with two occurrences of '&' have the inductive property. But we can't do that by appealing to the fact that the components, '(A&B)' and '(C&D)', have the inductive property. The inductive hypothesis allows us to appeal only to components which have two occurrences of '&' in them, but the components '(A&B)' and '(C&D)' have only one occurrence of '&' in them. The problem is frustrating, because in doing an induction, by the time we get to case n, we have proved that the inductive property also holds for all previous cases. So we should be able to appeal to the fact that the inductive property holds, not just for n, but for all previous cases as well. In fact, with a little cleverness one can apply weak induction to get around this problem. But, more simply, we can appeal to another formulation of mathematical induction: Wed Induction, Strong Formulation: Exactly like weak induction, except in the inductive step assume as inductive hypothesis that P(i) holds for all i 5 n, and prove that P(n + 1). 11-3. Using the strong formulation of weak induction, prove that any sentence logic sentence in which '&' is the only connective is true iff all its atomic sentence letters are true. You could have done the last problem with yet another form of induction:

Strong Induction

Suppose that an inductive property, P(n), is defined for n = 1, 2, 3, . . . . Suppose that for arbitrary n we use, as our inductive hypothesis, that P(n) holds for all i < n; and from that hypothesis we prove that P(n). Then we may conclude that P(n) holds for all n from n = 1 on. If P(n) is defined from n = 0 on, or if we start from some other value of n, the conclusion holds for that value of n onward.

Strong induction looks like the strong formulation of weak induction, except that we do the inductive step for all i < n instead of all i 5 n. You are probably surprised to see no explicit statement of a basis step in the statement of strong induction. This is because the basis step is actually covered by the inductive step. If we are doing the induction from n = 1 onward, how do we establish P(i) for all i < l? There aren't any cases of i < l! When n = 1, the inductive hypothesis holds vacuously. In other words, when n = 1, the inductive hypothesis gives us no facts to which to appeal. So the only way in which to establish the inductive step when n = 1 is just to prove that P(1). Consequently, the inductive step really covers the case of the basis step. Similar comments apply if we do the induction from n = 0 onward, or if we start from some other integer. You may be wondering about the connections among the three forms of induction. Weak induction and weak induction in its strong formulation are equivalent. The latter is simply much easier to use in problems such as the last one. Many textbooks use the name 'strong induction' for what I have called 'weak induction, strong formulation'. This is a mistake. Strong induction is the principle I have called by that name. It is truly a stronger principle than weak induction, though we will not use its greater strength in any of our work. As long as we restrict attention to induction on the finite integers, strong and weak induction are equivalent. Strong induction shows its greater strength only in applications to something called "transfinite set theory," which studies the properties of mathematical objects which are (in some sense) greater than all the finite integers. Since, for our work, all three principles are equivalent, the only difference comes in ease of use. For most applications, the second or third formulation will apply most easily, with no real difference between them. So I will refer to both of them, loosely, as "strong induction." You simply need to specify, when doing the inductive step, whether your inductive hypothesis assumes P(i) for all i < n, on the basis of which you prove P(n), or whether you assume P(i) for all i 5 n, on the basis of which you prove P(n + 1). In either case, you will, in practice, have to give a separate proof for the basis step. I should mention one more pattern of argument, one that is equivalent to strong induction:

LEAST Number Principle

To prove that $$P(n)$$, for all integers $$n$$, assume that there is some least value of n, say m, for which P(m) fails and derive a contradiction. The least number principle applies the reductio argument strategy. We want to show that, for all n, P(n). Suppose that this is not so. Then there is some collection of values of n for which P(n) fails. Let m be the least such value. Then we know that for all i < m, P(i) holds. We then proceed to use this fact to show that, after all, P(m) must hold, providing the contradiction. You can see that this form of argument really does the same work as strong induction: We produce a general argument, which works for any value of m, which shows that if for all i < m P(i) holds, then P(m) must hold also.

You will notice in exercises 11-7 to 11-9 that you are proving things which in the beginning of Volume I we simply took for granted. Again, this illustrates how some things we take for granted really turn on mathematical induction.

EXERCISES 114. Prove that any sentence logic sentence in which 'v' is the only connective is true iff at least one of its atomic sentence letters is true.

11-5. Consider any sentence logic sentence, X, in which '&' and 'v' are the only connectives. Prove that for any such sentence, there is an interpretation which makes it true and an interpretation which makes it false. Explain how this shows that '&' and 'v', singly and together, are not expressively complete for truth functions, as this idea is explained in section 34, (volume I).

11-6. Consider any sentence logic sentence, X, in which '-' does not appear (so that '&', 'v', 'S, and '=' are the only connectives). Prove that for any such sentence there is an interpretation which makes X true. Explain how this shows that '&', 'v', 'S, and '=' are, singly and together, not expressively complete for truth functions. 11-7. Prove for all sentence logic sentences, X, and all interpretations, I, that either I makes X true or I makes X false, but not both. 11-8. Prove for all sentence logic sentences, X, that if two truth value assignments, I and If, agree on all the atomic sentence letters in X, then I and I' assign X the same truth value. 11-9. Prove the law of substitution of logical equivalents for sentence logic.