<<

. 82
( 107 .)



>>


Section 16.2
452 / Mathematical Induction




Figure 16.1: The set of ambig-w¬s is the intersection of all sets satisfying
(1)“(3).

De¬nition The set S of ambig-w¬s is the smallest set satisfying the following
clauses:

1. Each propositional letter is in S.

2. If p is in S, then so is ¬p.

3. If p and q are in S, then so are p § q, p ∨ q, p ’ q, and p ” q.

What we have done here is replace the puzzling clause (4) by one that
refers to the smallest set satisfying (1)“(3). How does that help? First of all,
what do we mean by smallest? We mean smallest in the sense of subset: we
“smallest” set
want a set that satis¬es (1)“(3), but one that is a subset of any other set
satisfying (1)“(3). How do we know that there is such a smallest set? We need
to prove a lemma, to show that our de¬nition makes sense.1

Lemma 3. If S is the intersection of a collection X of sets, each of which
satis¬es (1)“(3), S will also satisfy (1)“(3).

We leave the proof of the lemma as Exercise 16.11.
As a result of this lemma, we know that if we de¬ne the set of ambig-w¬s
to be the intersection of all sets that satisfy (1)“(3), then we will have a set
that satis¬es (1)“(3). Further, it must be the smallest such set, since when
1A “lemma” is an auxiliary result, one that is of little intrinsic interest, but which is
needed for some larger end. Lemmas have the same formal status as theorems or proposi-
tions, but are usually less important.




Chapter 16
Induction on the natural numbers / 453



you take the intersection of a bunch of sets, the result is always a subset of
all of the original sets.
The situation is illustrated in Figure 16.1. There are lots of sets that satisfy
clauses (1)“(3) of our de¬nition, most of which contain many elements that are
not ambig-w¬s. For example, the set of all ¬nite strings of propositional letters
and connectives satis¬es (1)“(3), but it contains strings like A1 ¬ ’ A2 that
aren™t ambig-w¬s. Our set theoretic de¬nition takes the set S of ambig-w¬s
to be the smallest, that is, the intersection of all these sets.
Notice that we can now explain exactly why proof by induction is a valid justifying induction
form of reasoning. When we give an inductive proof, say that all ambig-w¬s
have property Q, what we are really doing is showing that the set {x | Q(x)}
satis¬es clauses (1)“(3). We show that the basic elements all have property
Q and that if you apply the generation rules to things that have Q, you will
get other things that have Q. But if Q satis¬es clauses (1)“(3), and S is the
intersection of all the sets that satisfy these clauses, then S ⊆ Q. Which is to
say: all ambig-w¬s have property Q.

Exercises


16.11 Prove Lemma 3.


16.12 Give an inductive de¬nition of the set of w¬s of propositional logic, similar to the above
 de¬nition, but putting in the parentheses in clause (3). That is, the set of w¬s should be
de¬ned as the smallest set satisfying various clauses. Be sure to verify that there is such a
smallest set.

16.13 Based on your answer to Exercise 16.12, prove that every w¬ has the same number of left
 parentheses as binary connectives.



Section 16.3
Induction on the natural numbers

Many students come away from the study of induction in math classes with
the feeling that it has something special to do with the natural numbers. By
now, it should be obvious that this method of proof is far more general than
that. We can prove things about many di¬erent kinds of sets using induction.
In fact, whenever a set is de¬ned inductively, we can prove general claims




Section 16.3
454 / Mathematical Induction


about its members using an inductive proof. Still, the natural numbers are
one of the simplest and most useful examples to which induction applies.
Just how are the natural numbers de¬ned? Intuitively, the de¬nition runs
de¬ning natural
numbers as follows:

1. 0 is a natural number.

2. If n is a natural number, then n + 1 is a natural number.

3. Nothing is a natural number except in virtue of repeated applications
of (1) and (2).

In set theory, this de¬nition gets codi¬ed as follows. The set N of natural
numbers is the smallest set satisfying:

1. 0 ∈ N

2. If n ∈ N , then n + 1 ∈ N

Based on this de¬nition, we can prove statements about natural numbers
by induction. Suppose we have some set Q of natural numbers and want to
prove that the set contains all natural numbers:

∀x [x ∈ N ’ x ∈ Q]

If we prove the following two things:
induction on N

1. 0 ∈ Q

2. If n ∈ Q, then n + 1 ∈ Q

then we know that N ⊆ Q, since N is de¬ned to be the smallest set satisfying
these clauses. And this is just another way of stating the universal claim we
want to prove.
Let™s work through an example that illustrates induction on the natural
numbers.

Proposition 4. For every natural number n, the sum of the ¬rst n natural
numbers is n(n + 1)/2.

Proof: We want to prove the statement ∀n(n ∈ N ’ Q(n)), where
Q(n) is the statement: the sum of the ¬rst n natural numbers is
n(n + 1)/2. We do this by induction.
Basis: The basis step requires that we prove that the sum of the ¬rst
0 natural numbers is 0, which it is. (If you don™t like this case, you



Chapter 16
Induction on the natural numbers / 455



might check to see that Q(1) holds. You might even go so far as to
check Q(2), although it™s not necessary.)
Induction: To prove the inductive step, we assume that we have a
natural number k for which Q(k) holds, and show that Q(k + 1)
holds. That is, our inductive hypothesis is that the sum of the ¬rst
k natural numbers is k(k + 1)/2. We must show that the sum of the
¬rst k + 1 natural numbers is (k + 1)(k + 2)/2. How do we conclude
this? We simply note that the sum of the ¬rst k + 1 natural numbers
is k + 1 greater than the sum of the ¬rst k natural numbers. We
already know by the inductive hypothesis that this latter sum is
simply k(k + 1)/2. Thus the sum of the ¬rst k + 1 numbers is
k(k + 1)
+ (k + 1)
2
Getting a common denominator gives us
k(k + 1) 2(k + 1)
+
2 2
which we factor to get
(k + 2)(k + 1)
2
the desired result.


Exercises


16.14 Prove by induction that for all natural numbers n, n ¤ 2n.


16.15 Prove by induction that for all natural numbers n, 0 + 1 + . . . + n ¤ n2 . Your proof should
 not presuppose Proposition 4, which we proved in the text, though it will closely follow the
structure of that proof.

16.16 Prove by induction that for all n,

1 + 3 + 5 + . . . + (2n + 1) = (n + 1)2

16.17 Prove that for all natural numbers n ≥ 2,

1 1 1 1
(1 ’ )(1 ’ ) . . . (1 ’ ) =
2 3 n n




Section 16.3
456 / Mathematical Induction


16.18 Notice that 13 + 23 + 33 = 36 = 62 and that 13 + 23 + 33 + 43 + 53 = 225 = 152 . Prove that the
 sum of the ¬rst n perfect cubes is a square. [Hint: This is an instance of the inventor™s paradox.
You will have to prove something stronger than this.]



Section 16.4
Axiomatizing the natural numbers

In giving examples of informal proofs in this book, we have had numerous
occasions to use the natural numbers as examples. In proving things about
the natural numbers, we have made recourse to any fact about the natural
numbers that was obviously true. If we wanted to formalize these proofs, we
would have to be much more precise about what we took to be the “obvious”
facts about the natural numbers.
Over the years, a consensus has arisen that the obviously true claims about
the natural numbers can be formalized in what has come to be known as Peano
Peano Arithmetic (pa)
Arithmetic, or pa for short, named after the Italian mathematician Giuseppe
Peano. This is a certain ¬rst-order theory whose main axiom states a form of
induction for natural numbers.
pa is formulated in a ¬rst-order language that has constants 0 and 1 to-
gether with the binary function symbols + and — and the identity predicate.
It takes as axioms the following basic facts about the domain of natural num-
bers.

1. ∀x ∀y (x + 1 = y + 1 ’ x = y)

2. ∀x (x + 1 = 0)

3. 0 + 1 = 1

4. ∀x (x + 0 = x)

5. ∀x ∀y [x + (y + 1) = (x + y) + 1]

6. ∀x (x — 0 = 0)

7. ∀x ∀y [x — (y + 1) = (x — y) + x]

In addition, pa has an axiom scheme capturing the principle of mathematical
induction on the natural numbers. This can be stated as follows:
induction scheme

[Q(0) § ∀x (Q(x) ’ Q(x + 1))] ’ ∀x Q(x)




Chapter 16
Axiomatizing the natural numbers / 457



What this says if that if Q(x) is satis¬ed by 0, and if its being satis¬ed by
some number n insures that it is satis¬ed by n + 1, then Q(x) is satis¬ed by
all natural numbers. (Actually, as with the axioms of comprehension in the
preceding chapter, the axiom needs to be stated a bit more generally than we
have stated it. The w¬ Q(x) may have free variables other than x, and these
need to be universally quanti¬ed.)
There are many other facts about the natural numbers which are obvious.
Some of these include the familiar commutative, associative, and distributive
laws from addition and multiplication. It turns out, however, that these facts,
and all other “obvious” facts, and many very di¬cult facts, can be proven
from the axioms as set out above. Here is probably the simplest; we give an
informal proof, using just these axioms, of

∀x (x + 1 = 1 + x)

<<

. 82
( 107 .)



>>