basis step tips over the initial domino. Here is the actual inductive proof:

Proof: We will prove this proposition by induction on the ambig-

an inductive proof

w¬s.

Basis: For our basis case, we need to show that all the propositional

letters are strings that contain at least one propositional letter. But

they do, since they in fact consist of exactly one such letter.

Induction: Suppose p and q are ambig-w¬s that each contain at least

one propositional letter. We want to show that the new ambig-w¬s

generated from these by clauses (2) and (3) will also contain at least

one propositional letter. This is clearly true, since ¬p contains all

the propositional letters contained in p, and so contains at least one

propositional letter; and p § q, p ∨ q, p ’ q, and p ” q contain all

the propositional letters contained in p and q, and so contain at least

one (indeed at least two) propositional letters.

By induction, we can thus conclude that all ambig-w¬s contain at

least one propositional letter.

As far as substance goes, this is a pretty trivial proof. But it is important

to have a good grasp of the form of the proof, and particularly the form of the

inductive step. The inductive step is always a subproof whose assumption is

that the property in question, Q, holds of some arbitrarily selected members of

the inductively de¬ned set. In the above example, we assumed that the ambig-

w¬s p and q each had Q, that is, each contained at least one propositional

letter. This assumption is called the inductive hypothesis. The goal of the

inductive hypothesis

step is to show that it follows from the inductive hypothesis that any new

members generated from these”new ambig-w¬s in our example”must have

the property Q as well.

What ultimately justi¬es the conclusion of an inductive proof is the last

clause of the inductive de¬nition. In our example, since nothing is an ambig-

Chapter 16

Inductive definitions and inductive proofs / 447

w¬ except the basic elements and things that can be generated from them by

repeated applications of our two rules, we can be sure that all the ambig-w¬s

have the property in question.

Let™s try another example. Suppose we want to prove that the string

A1 ¬ ’ A2 is not an ambig-w¬. Again, this is pretty obvious, but to prove

it we need to prove a general fact about the ambig-w¬s, one that will allow

us to conclude that this particular string does not qualify. The following fact

would su¬ce:

Proposition 2. No ambig-w¬ has the symbol ¬ occurring immediately before

one of the binary connectives: §, ∨, ’, ”.

Once again, note that the desired result has the form of a general condi-

tional claim, where the antecedent is our inductively de¬ned predicate:

∀p [(p is an ambig-w¬) ’ Q(p)]

This time, Q is the property of not having ¬ occurring immediately in front

of a binary connective. To prove this, we need a basis step and an inductive

step. The basis step must show that Q(p) holds for those expressions p that

are ambig-w¬s in virtue of clause (1), that is, the propositional letters. The

inductive step involves two cases, one corresponding to premise (2), the other

to premise (3). For (2), we must show that if an ambig-w¬ p has property

Q, so does ¬p. For (3), we need to prove that if p and q are ambig-w¬s with

property Q then so are p § q, p ∨ q, p ’ q, and p ” q. If we can do this,

the proof will be completed by induction, thanks to clause (4). After all, since

every ambig-w¬ has to be obtained by repeated applications of (1), (2), and

(3), every ambig-w¬ will have been shown to have the property in question.

But there is a problem when we try to carry out the details of this proof.

Do you see what it is? Think about trying to do either part of the inductive

step, either (2) or (3). For example, in case (2), how do we know that just

because p has property Q so does ¬p? Well, we don™t. For example, ’A1 has

property Q but ¬ ’A1 does not. (Find a similar problem with case (3).)

This is an example of the so-called Inventor™s Paradox. It is not a real inventor™s paradox

paradox, as in the case of Russell™s Paradox, but it is a bit counterintuitive.

It turns out that proofs by induction often get stuck, not because you are

trying to prove something false, but because you are not aiming high enough.

You need to prove more. In this case, what we have to prove to keep the

induction from getting stuck is this stronger claim: no ambig-w¬ either begins

with a binary connective, or ends with a negation sign, or has a negation

sign immediately preceding a binary connective. So let Q be this stronger

property. It is clear that ∀p [Q (p) ’ Q(p)]. Thus, what we need to prove by

induction is that

Section 16.1

448 / Mathematical Induction

∀p [(p is an ambig-w¬) ’ Q (p)]

This turns out to be easy, and is left as an exercise.

Let™s quickly look at another example of an inductively de¬ned set and a

another inductive

de¬nition proof by induction based on this de¬nition. Suppose we de¬ned the set pal as

follows:

1. Each letter in the alphabet (a, b, c,. . . , z) is a pal.

2. If a string ± is a pal, so is the result of putting any letter of the alphabet

both in front of and in back of ± (e.g., a±a, b±b, c±c, etc.).

3. Nothing is a pal unless it is generated by repeated applications of (1)

and (2).

Make sure you understand how this de¬nition works. For example, come up

with a string of seven letters that is a pal.

Now let™s prove that every pal reads the same way back to front and front

to back, in other words, every pal is a palindrome. Here is our inductive proof

palindromes

of this fact:

Proof: We prove by induction that every pal reads the same forwards

and backwards, that is, when the order of letters in the string is

reversed.

Basis: The basic elements of pal are single letters of the alphabet.

Clearly, any single letter reads the same way forwards or backwards.

Induction: Suppose that the pal ± reads the same way forwards or

backwards. (This is our inductive hypothesis.) Then we must show

that if you add a letter, say l, to the beginning and end of ±, then

the result, l±l, reads the same way forwards and backwards. When

you reverse the string l±l, you get l± l, where ± is the result of

reversing the string ±. But by the inductive hypothesis, ± = ± , and

so the result of reversing l±l is l±l, i.e., it reads the same forwards

and backwards.

We conclude by induction that every pal is a palindrome.

Chapter 16

Inductive definitions and inductive proofs / 449

Remember

Given an inductive de¬nition of a set, an inductive proof requires

—¦ a basis step, which shows that the property holds of the basic elements,

and

—¦ an inductive step, which shows that if the property holds of some

elements, then it holds of any elements generated from them by the

inductive clauses.

The assumption that begins the inductive step is called the inductive

hypothesis.

Exercises

16.1 In the state of Euphoria, the following two principles hold:

1. If it is sunny on one day, it is sunny the next day.

2. It is sunny today.

Prove that it is going to be sunny from now on.

16.2 Raymond Smullyan, a famous logician/magician, gives the following good advice: (1) always

speak the truth, and (2) each day, say “I will repeat this sentence tomorrow.” Prove that

anyone who did these two things would live forever. Then explain why it won™t work.

16.3 Give at least two distinct derivations which show that the following is an ambig-w¬: A1 ’

A2 ” ¬A2 .

16.4 Prove by induction that no ambig-w¬ begins with a binary connective, ends with a negation

sign, or has a negation sign immediately preceding a binary connective. Conclude that the

string A1 ¬ ’ A2 is not an ambig-w¬.

16.5 Prove that no ambig-w¬ ever has two binary connectives next to one another. Conclude that

A1 ’ ∨A2 is not an ambig-w¬.

16.6 Modify the inductive de¬nition of ambig-w¬ as follows, to de¬ne the set of semi-w¬s:

1. Each propositional letter is a semi-w¬.

2. If p is any semi-w¬, so is the string ¬p).

3. If p and q are semi-w¬s, so are (p § q), (p ∨ q), (p ’ q), (p ” q).

4. Nothing is a semi-w¬ except in virtue of repeated applications of (1), (2), and (3).

Prove by induction that every semi-w¬ has the following property: the number of right paren-

theses is equal to the number of left parentheses plus the number of negation signs.

Section 16.1

450 / Mathematical Induction

16.7 In the text, we proved that every pal is a palindrome, a string of letters that reads the same

back to front and front to back. Is the converse true, that is, is every palindrome a pal? If so,

prove it. If not, ¬x up the de¬nition so that it becomes true.

16.8 (Existential w¬s) In this problem we return to a topic raised in Problem 14.59. In that problem

we de¬ned an existential sentence as one whose prenex form contains only existential quanti¬ers.

A more satisfactory de¬nition can be given by means of the following inductive de¬nition. The

existential w¬s are de¬ned inductively by the following clauses:

1. Every atomic or negated atomic w¬ is existential.

2. If P1 , . . . , Pn are existential, so are (P1 ∨ . . . ∨ Pn ) and (P1 § . . . § Pn ).

3. If P is an existential w¬, so is ∃νP , for any variable ν.

4. Nothing is an existential w¬ except in virtue of (1)“(3).

Prove the following facts by induction:

—¦ If P is an existential w¬, then it is logically equivalent to a prenex w¬ with no universal

quanti¬ers.

—¦ If P is an existential sentence that is true in some world, then it will remain true if new

objects are added to the world. [You will need to prove something a bit stronger to keep

the induction going.]

Is our new de¬nition equivalent to our old one? If not, how could it be modi¬ed to make it

equivalent?

16.9 Give a de¬nition of universal w¬, just like that of existential w¬ in the previous problem, but

with universal quanti¬ers instead of existential. State and prove results analogous to the results

you proved there. Then show that every universal w¬ is logically equivalent to the negation of

an existential w¬.

16.10 De¬ne the class of wellfounded sets by means of the following inductive de¬nition:

1. If C is any set of objects, each of which is either not a set or is itself a wellfounded set,

then C is a wellfounded set.

2. Nothing is a wellfounded set except as justi¬ed by (1).

This exercise explores the relationship between the wellfounded sets and the cumulative con-

ception set discussed in the preceding chapter.

1. Which of the following sets are wellfounded?

…, {…}, {Washington Monument}, {{{. . .}}}

Chapter 16

Inductive definitions in set theory / 451

2. Assume that a is wellfounded. Show that „˜a is wellfounded.

3. Assume that a and b are wellfounded. Is the ordered pair a, b (as de¬ned in the

preceding chapter) wellfounded?

4. Assume that a = {1, b} and b = {2, a}. Are a and b wellfounded?

5. Show that the Axiom of Regularity implies that every set is wellfounded.

6. When using set theory, one often wants to be able to prove statements of the form:

∀x [Set(x) ’ Q(x)]

One of the advantages of the cumulative conception of set discussed in the preceding

chapter is that it allows one to prove such statements “by induction on sets.” How?

7. Use mathematical induction to show that there is no in¬nite sequence of wellfounded

sets a1, a2 , a3 , . . . such that an+1 ∈ an for each natural number n.

Section 16.2

Inductive de¬nitions in set theory

The way we have been stating inductive de¬nitions seems reasonably rigorous.

Still, you might wonder about the status of clauses like

4. Nothing is an ambig-w¬ unless it can be generated by repeated applica-

tions of (1), (2), and (3).

This clause is quite di¬erent in character from the others, since it mentions not

just the objects we are de¬ning, but the other clauses of the de¬nition itself.

You might also wonder just what is getting packed into the phrase “repeated

applications.”

One way to see that there is something di¬erent about clause (4) is to note

that the other clauses are obviously expressible using ¬rst-order formulas. For

example, if concat is a symbol for the concatenation function (that is, the

function that takes two expressions and places the ¬rst immediately to the

left of the second), then one could express (2) as

∀p [ambig-w¬(p) ’ ambig-w¬(concat(¬, p))]

In contrast, clause (4) is not the sort of thing that can be expressed in fol.

However, it turns out that if we work within set theory, then we can ex- making the ¬nal

clause more precise

press inductive de¬nitions with ¬rst-order sentences. Here, for example, is a

de¬nition of the set of ambig-w¬s that uses sets. It turns out that this de¬-

nition can be transcribed into the language of set theory in a straightforward

way. The English version of the de¬nition is as follows: