<< Предыдущая стр. 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 стр.)ОГЛАВЛЕНИЕ Следующая >>