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: