<<

. 80
( 107 .)



>>

 of discourse in which both are clearly true. [Hint: consider the domain whose only element is
the empty set.]

15.69 Show that the theorem about the existence of a©b can be proven using the Axiom of Separation,
 but that the theorem about the existence of a ∪b cannot be so proven. [Come up with a domain
of sets in which the separation axiom is true but the theorem in question is false.]

15.70 (The Union Axiom and ∪) Exercise 15.69 shows us that we cannot prove the existence of a ∪ b
 from the Axiom of Separation. However, the Union Axiom of zfc is stronger than this. It says
not just that a ∪ b exists, but that the union of any set of sets exists.
1. Show how to prove the existence of a ∪ b from the Union Axiom. What other axioms
of zfc do you need to use?
2. Apply the Union Axiom to show that there is no set of all singletons. [Hint: Use proof
by contradiction and the fact that there is no universal set.]

15.71 Prove in zfc that for any two sets a and b, the Cartesian product a — b exists. The proof you
 gave in an earlier exercise will probably not work here, but the result is provable.

15.72 While § and ∨ have set-theoretic counterparts in © and ∪, there is no absolute counterpart
 to ¬.
1. Use the axioms of zfc to prove that no set has an absolute complement.
2. In practice, when using set theory, this negative result is not a serious problem. We
usually work relative to some domain of discourse, and form relative complements.
Justify this by showing, within zfc, that for any sets a and b, there is a set c = {x |
x ∈ a § x ∈ b}. This is called the relative complement of b with respect to a.

15.73 Assume the Axiom of Regularity. Show that no set is a member of itself. Conclude that, if we
 assume Regularity, then for any set b, the Russell set for b is simply b itself.




Chapter 15
Zermelo Frankel set theory zfc / 441



15.74 (Consequences of the Axiom of Regularity)

1. Show that if there is a sequence of sets with the following property, then the Axiom of
Regularity is false:
. . . ∈ an+1 ∈ an ∈ . . . ∈ a2 ∈ a1
2. Show that in zfc we can prove that there are no sets b1 , b2 , . . . , bn , . . . , where bn =
{n, bn+1 }.
3. In computer science, a stream is de¬ned to be an ordered pair x, y whose ¬rst element
is an “atom” and whose second element is a stream. Show that if we work in zfc and
de¬ne ordered pairs as usual, then there are no streams.

There are alternatives to the Axiom of Regularity which have been explored in recent years.
We mention our own favorite, the axiom afa, due to Peter Aczel and others. The name “afa”
stands for “anti-foundation axiom.” Using afa you can prove that a great many sets exist with
properties that contradict the Axiom of Regularity. We wrote a book, The Liar, in which we
used afa to model and analyze the so-called Liar™s Paradox (see Exercise 19.32, page 555).




Section 15.9
Chapter 16

Mathematical Induction
In the ¬rst two parts of this book, we covered most of the important methods
of proof used in rigorous reasoning. But we left out one extremely important
method: proof by mathematical induction.
By and large, the methods of proof discussed earlier line up fairly nicely
with various connectives and quanti¬ers, in the sense that you can often tell
from the syntactic form of your premises or conclusion what methods you
will be using. The most obvious exception is proof by contradiction, or its
formal counterpart ¬ Intro. This method can in principle be used to prove
any form of statement, no matter what its main connective or quanti¬er. This
is because any sentence S is logically equivalent to one that begins with a
negation symbol, namely, ¬¬S.
In terms of syntactic form, mathematical induction is typically used to
form of statements
proved by induction prove statements of the form

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

This is also the form of statements proved using general conditional proof.
In fact, proof by induction is really a pumped-up version of this method:
general conditional proof on steroids, you might say. It works when these
statements involve a predicate P(x) de¬ned in a special way. Speci¬cally, proof
by induction is available when the predicate P(x) is de¬ned by what is called an
inductive de¬nition. For this reason, we need to discuss proof by induction and
inductive de¬nition
inductive de¬nitions side by side. We will see that whenever a predicate P(x)
is de¬ned by means of an inductive de¬nition, proof by induction provides a
much more powerful method of proof than ordinary general conditional proof.
Before we can discuss either of these, though, we should distinguish both
from yet a third process that is also known as induction. In science, we use
induction in science
the term “induction” whenever we draw a general conclusion on the basis of a
¬nite number of observations. For example, every day we observe that the sun
comes up, that dropped things fall down, and that people smile more when
it is sunny. We come to infer that this is always the case: that the sun comes
up every morning, that dropped things always fall, that people are always
happier when the sun is out.
Of course there is no strict logical justi¬cation for such inferences. We may
have correctly inferred some general law of nature, or we may have simply ob-
served a bunch of facts without any law that backs them up. Some time in



442
Inductive definitions and inductive proofs / 443



the future, people may be happier if it rains, for example after a long drought.
Induction, in this sense, does not guarantee that the conclusion follows neces-
sarily from the premises. It is not a deductively valid form of inference, since
it is logically possible for the premises to be true and the conclusion false.
This is all by way of contrast with mathematical induction, where we can vs. mathematical
induction
justify a general conclusion, with in¬nitely many instances, on the basis of a
¬nite proof. How is this possible? The key lies in the inductive de¬nitions that
underwrite this method of proof. Induction, in our sense, is a logically valid
method of proof, as certain as any we have studied so far.
Usually, discussions of mathematical induction start (and end) with in-
duction on the natural numbers, to prove statements of the form

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

We will start with other examples, examples which show that mathematical
induction applies much more widely than just to natural numbers. The reason
it applies to natural numbers is simply that the natural numbers can be
speci¬ed by means of an inductive de¬nition. But so can many other things.


Section 16.1
Inductive de¬nitions and inductive proofs
Inductive de¬nitions involve setting things up in a certain methodical, step-
by-step manner. Proofs by induction take advantage of the structure that
results from such inductive de¬nitions. We begin with a simple analogy.

Dominoes
When they were younger, Claire and Max liked to build long chains of domi-
noes, all around the house. Then they would knock down the ¬rst and, if
things were set up right, the rest would all fall down. Little did they know
that in so doing they were practicing induction. Setting up the dominoes is
like giving an inductive de¬nition. Knocking them all down is like proving a
theorem by induction.
There are two things required to make all the dominoes fall over. They
must be close enough together that when any one domino falls, it knocks down
the next. And then, of course, you need to knock down the ¬rst. In a proof by
induction, these two steps correspond to what are called the inductive step
(getting from one to the next) and the basis step (getting the whole thing
started).



Section 16.1
444 / Mathematical Induction


Notice that there is no need to have just one domino following each domino.
You can have two, as long as the one in front will knock down both of its
successors. In this way you can build quite elaborate designs, branching out
here and there, and, when the time is right, you can knock them all down
with a single ¬‚ick of the ¬nger. The same is true, as we™ll see, with induction.

Inductive de¬nitions
Inductive de¬nitions are used a great deal in logic. In fact, we have been using
them implicitly throughout this book. For example, our de¬nitions of the w¬s
of fol were really inductive de¬nitions. So was our de¬nition of the set of
terms of ¬rst-order arithmetic. Both of these de¬nitions started by specifying
inductive de¬nitions
the simplest members of the de¬ned collection, and then gave rules that told
us how to generate “new” members of the collection from “old” ones. This is
how inductive de¬nitions work.
Let™s look at another example, just to make things more explicit. Suppose
that for some reason we wanted to study an ambiguous variant of proposi-
tional logic, maybe as a mathematical model of English that builds in some
ambiguity. Let™s take some primitive symbols, say A1 , . . . , An , and call these
propositional letters. Next, we will build up “w¬s” from these using our old
friends ¬, §, ∨, ’, and ”. But we are going to let the language be ambiguous,
unlike fol, by leaving out all parentheses. How will we do this? To distinguish
these strings from w¬s, let us call them ambig-w¬s. Intuitively, what we want
ambig-w¬s
to say is the following:

1. Each propositional letter is an ambig-w¬.

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

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

4. Nothing is an ambig-w¬ unless it is generated by repeated applications
of (1), (2), and (3).

In this de¬nition, clause (1) speci¬es the basic ambig-w¬s. It is called the
base clause of the de¬nition. Clauses (2) and (3) tell us how to form new
base clause
ambig-w¬s from old ones. They are called inductive clauses. The ¬nal clause
inductive clause
just informs us that all ambig-w¬s are generated by the earlier clauses, in case
¬nal clause
we thought that the World Trade Center or the actor Brad Pitt or the set {2}
might be an ambig-w¬.




Chapter 16
Inductive definitions and inductive proofs / 445



Remember

An inductive de¬nition consists of

—¦ a base clause, which speci¬es the basic elements of the de¬ned set,

—¦ one or more inductive clauses, which tell us how to generate additional
elements, and

—¦ a ¬nal clause, which tells us that all the elements are either basic or
generated by the inductive clauses.




Inductive proofs
Having set up an inductive de¬nition of the set of ambig-w¬s, we are in a
position to prove things about this set. For example, assuming the clauses of
our inductive de¬nition as premises, we can easily prove that A1 ∨ A2 § ¬A3
is an ambig-w¬.

Proof: First, A1 , A2 , and A3 are ambig-w¬s by clause (1). ¬A3 is
thus an ambig-w¬ by clause (2). Then A2 § ¬A3 is an ambig-w¬ by
clause (3). Another use of clause (3) gives us the desired ambig-w¬
A1 ∨A2 §¬A3. (Can you give a di¬erent derivation of this ambig-w¬,
one that applies § before ∨?)

This proof shows us how the inductive de¬nition of the ambig-w¬s is sup-
posed to work, but it is not an inductive proof. So let™s try to prove something
about ambig-w¬s using the method of inductive proof. Indeed, let™s prove a
few things that will help us identify strings that are not ambig-w¬s.
Consider the string ¬∨ ’. Obviously, this is not an ambig-w¬. But how do
we know? Well, clause (4) says it has to be formed by repeated applications of
clauses (1)“(3). Examining these clauses, it seems obvious that anything you
get from them will have to contain at least one propositional letter. But what
kind of proof is that? What method are we applying when we say “examining
these clauses, it seems obvious that . . . ”? What we need is a way to prove the
following simple fact:

Proposition 1. Every ambig-w¬ contains at least one propositional letter.

Notice that this claim has the form of a general conditional, where the
antecedent involves an inductively de¬ned predicate:



Section 16.1
446 / Mathematical Induction


∀p [(p is an ambig-w¬) ’ Q(p)]
Here, Q is the property of containing at least one propositional letter. What
the method of induction allows us to do is prove just such a claim. The way
proof by induction
we do it is by showing two things. First, we show that all the basic ambig-
w¬s, those speci¬ed by clause (1), have the property Q. We call this the basis
basis step
step of our inductive proof. Second, we show that if some “old” members of
ambig-w¬ have the property Q, then so will the “new” members generated
from them by the inductive clauses (2) and (3). We call this the inductive
inductive step
step of the proof. This is just like knocking down dominoes, albeit in reverse:

<<

. 80
( 107 .)



>>