<< Предыдущая стр. 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 стр.)ОГЛАВЛЕНИЕ Следующая >>