<<

. 81
( 107 .)



>>

the inductive step shows that if a domino falls down, so will the next one; the
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:


<<

. 81
( 107 .)



>>