ńņš. 82 |

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 |