<< Ļšåäūäółą’ ńņš. 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ā
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 ńņš.)ĪĆĖĄĀĖÅĶČÅ Ńėåäóžłą’ >>