q
divisors of q, it follows that q has only two positive divisors, q and 2n−1 .
q
Since one of its divisors must be 1, it must be that 2n−1 = 1, which means
q = 2n − 1. Now a number with just two positive divisors is prime, so
q = 2n − 1 is prime. Plugging this into Equation (8.3) gives p = 2n−1(2n − 1),
where 2n − 1 is prime. This means p ∈ A, by definition of A. We have now
shown that p ∈ E implies p ∈ A, so E ⊆ A.
Since A ⊆ E and E ⊆ A, it follows that A = E.
■
Do not be alarmed if you feel that you wouldn’t have thought of this
proof. It took the genius of Euler to discover this approach.
We’ll conclude this chapter with some facts about perfect numbers.
• The sixth perfect number is p = 217−1(217 − 1) = 8589869056.
• The seventh perfect number is p = 219−1(219 − 1) = 137438691328.
• The eighth perfect number is p = 231−1(231 − 1) = 2305843008139952128.
• The twentieth perfect number is p = 24423−1(24423 − 1). It has 2663 digits.
• The twenty-third perfect number is p = 211213−1(211213 − 1). It has 6957
digits.
As mentioned earlier, no one knows whether or not there are any odd
perfect numbers. It is not even known whether there are finitely many or
infinitely many perfect numbers. It is known that the last digit of every
even perfect number is either a 6 or an 8. Perhaps this is something you’d
enjoy proving.
We’ve seen that perfect numbers are closely related to prime numbers
that have the form 2n − 1. Such prime numbers are called Mersenne
primes, after the French scholar Marin Mersenne (1588–1648), who
popularized them.
The first several Mersenne primes are 22 − 1 = 3,
23 − 1 = 7, 25 − 1 = 31, 27 − 1 = 127 and 213 − 1 = 8191. To date, only
48 Mersenne primes are known, the largest of which is 257,885,161 − 1.
There is a substantial cash prize for anyone who finds a 49th.
(See
http://www.mersenne.org/prime.htm.) You will probably have better luck
with the exercises.
Examples: Perfect Numbers
145
Exercises for Chapter 8
Use the methods introduced in this chapter to prove the following statements.
1.
©
Prove that 12n : n ∈ Zª ⊆ ©2n : n ∈ Zª ∩ ©3n : n ∈ Zª.
2.
©
Prove that 6n : n ∈ Zª = ©2n : n ∈ Zª ∩ ©3n : n ∈ Zª.
3.
©
If k ∈ Z, then n ∈ Z : n | kª ⊆ ©n ∈ Z : n | k2ª.
4.
©
If m, n ∈ Z, then x ∈ Z : mn | xª ⊆ ©x ∈ Z : m | xª ∩ ©x ∈ Z : n | xª.
5.
©
If p and q are positive integers, then pn : n ∈ Nª ∩ ©qn : n ∈ Nª 6= ;.
6. Suppose A, B and C are sets. Prove that if A ⊆ B, then A − C ⊆ B − C.
7. Suppose A, B and C are sets. If B ⊆ C, then A × B ⊆ A × C.
8. If A, B and C are sets, then A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C).
9. If A, B and C are sets, then A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).
10. If A and B are sets in a universal set U, then A ∩ B = A ∪ B.
11. If A and B are sets in a universal set U, then A ∪ B = A ∩ B.
12. If A, B and C are sets, then A − (B ∩ C) = (A − B) ∪ (A − C).
13. If A, B and C are sets, then A − (B ∪ C) = (A − B) ∩ (A − C).
14. If A, B and C are sets, then (A ∪ B) − C = (A − C) ∪ (B − C).
15. If A, B and C are sets, then (A ∩ B) − C = (A − C) ∩ (B − C).
16. If A, B and C are sets, then A × (B ∪ C) = (A × B) ∪ (A × C).
17. If A, B and C are sets, then A × (B ∩ C) = (A × B) ∩ (A × C).
18. If A, B and C are sets, then A × (B − C) = (A × B) − (A × C).
19.
©
©
Prove that 9n : n ∈ Zª ⊆ ©3n : n ∈ Zª, but 9n : n ∈ Zª 6= ©3n : n ∈ Zª
20.
©
Prove that 9n : n ∈ Qª = ©3n : n ∈ Qª.
21. Suppose A and B are sets. Prove A ⊆ B if and only if A − B = ;.
22. Let A and B be sets. Prove that A ⊆ B if and only if A ∩ B = A.
23.
For each a ∈ R, let Aa = ©(x, a(x2 −1)) ∈ R2 : x ∈ Rª. Prove that
Aa = ©(−1,0),(1,0)ª.
a∈R
24.
Prove that
[3 − x2,5 + x2] = [3,5].
x∈R
25. Suppose A, B, C and D are sets. Prove that (A × B) ∪ (C × D) ⊆ (A ∪ C) × (B ∪ D).
26.
©
Prove 4k + 5 : k ∈ Zª = ©4k + 1 : k ∈ Zª.
27.
©
Prove 12a + 4b : a, b ∈ Zª = ©4c : c ∈ Zª.
28.
©
Prove 12a + 25b : a, b ∈ Zª = Z.
29. Suppose A 6= ;. Prove that A × B ⊆ A × C, if and only if B ⊆ C.
30. Prove that (Z × N) ∩ (N × Z) = N × N.
31. Suppose B 6= ; and A × B ⊆ B × C. Prove A ⊆ C.
CHAPTER
9
Disproof
ver since Chapter 4 we have dealt with one major theme: Given a
E statement, prove that is it true. In every example and exercise we
were handed a true statement and charged with the task of proving it.
Have you ever wondered what would happen if you were given a false
statement to prove? The answer is that no (correct) proof would be possible,
for if it were, the statement would be true, not false.
But how would you convince someone that a statement is false? The
mere fact that you could not produce a proof does not automatically mean
the statement is false, for you know (perhaps all too well) that proofs
can be difficult to construct. It turns out that there is a very simple and
utterly convincing procedure that proves a statement is false. The process
of carrying out this procedure is called disproof. Thus, this chapter is
concerned with disproving statements.
Before describing the new method, we will set the stage with some
relevant background information. First, we point out that mathematical
statements can be divided into three categories, described below.
One category consists of all those statements that have been proved to be
true. For the most part we regard these statements as significant enough
to be designated with special names such as “theorem,” “proposition,”
“lemma” and “corollary.” Some examples of statements in this category are
listed in the left-hand box in the diagram on the following page. There are
also some wholly uninteresting statements (such as 2 = 2) in this category,
and although we acknowledge their existence we certainly do not dignify
them with terms such as “theorem” or “proposition.”
At the other extreme is a category consisting of statements that are
known to be false. Examples are listed in the box on the right. Since
mathematicians are not very interested in them, these types of statements
do not get any special names, other than the blanket term “false statement.”
But there is a third (and quite interesting) category between these
two extremes. It consists of statements whose truth or falsity has not
bee
n determined. Examples include things like “Every perfect number
147
is even,” or “Every even integer greater than 2 is the sum of two primes.”
(The latter statement is called the Goldbach conjecture. See Section 2.1.)
Mathematicians have a special name for the statements in this category
that they suspect (but haven’t yet proved) are true. Such statements are
called conjectures.
Three Types of Statements:
Known to be true
Truth unknown
Known to be false
(Theorems & propositions)
(Conjectures)
Examples:
Examples:
Examples:
•
•
All prime numbers are
Pythagorean theorem
• All perfect numbers are
odd.
•
even.
Fermat’s last theorem
• Some quadratic equations
(Section 2.1)
• Any even number greater
have three solutions.
•
than 2 is the sum of two
The square of an odd
primes. (Goldbach’s
• 0 = 1
number is odd.
∞ 1
conjecture, Section 2.1)
• There exist natural
X
• The series
diverges.
k
• There are infinitely many
numbers a, b and c
k=1
prime numbers of form
for which a3 + b3 = c3.
2n − 1, with n ∈ N.
Mathematicians spend much of their time and energy attempting
to prove or disprove conjectures. (They also expend considerable mental
energy in creating new conjectures based on collected evidence or intuition.)
When a conjecture is proved (or disproved) the proof or disproof will
typically appear in a published paper, provided the conjecture is of sufficient
interest. If it is proved, the conjecture attains the status of a theorem or
proposition. If it is disproved, then no one is really very interested in it
anymore—mathematicians do not care much for false statements.
Most conjectures that mathematicians are interested in are quite
difficult to prove or disprove. We are not at that level yet. In this text, the
“conjectures” that you will encounter are the kinds of statements that an
experienced mathematician would immediately spot as true or false, but
you may have to do some work before figuring out a proof or disproof. But
in keeping with the cloud of uncertainty that surrounds conjectures at the
advanced levels of mathematics, most exercises in this chapter (and many
beyond it) will ask you to prove or disprove statements without giving any
hint as to whether they are true or false. Your job will be to decide whether
or not they are true and to either prove or disprove them. The examples
in this chapter will illustrate the processes one typically goes through in
148
Disproof
deciding whether a statement is true or false, and then verifying that it’s
true or false.
You know the three major methods of proving a statement: direct proof,
contrapositive proof and proof by contradiction. Now we are ready to
understand the method of disproving a statement. Suppose you want to
disprove a statement P. In other words you want to prove that P is false.
The way to do this is to prove that ∼ P is true, for if ∼ P is true, it follows
immediately that P has to be false.
How to disprove P:
Prove ∼ P.
Our approach is incredibly simple. To disprove P, prove ∼ P. In theory,
this proof can be carried out by direct, contrapositive or contradiction
approaches. However, in practice things can be even easier than that
if we are disproving a universally quantified statement or a conditional
statement. That is our next topic.
9.1 Disproving Universal Statements: Counterexamples
A conjecture may be described as a statement that we hope is a theorem.
As we know, many theorems (hence many conjectures) are universally
quantified statements. Thus it seems reasonable to begin our discussion
by investigating how to disprove a universally quantified statement such as
∀ x ∈ S, P(x).
To disprove this statement, we must prove its negation. Its negation is
∼ (∀ x ∈ S, P(x)) = ∃ x ∈ S, ∼ P(x).
The negation is an existence statement. To prove the negation is true,
we just need to produce an example of an x ∈ S that makes ∼ P(x) true,
that is, an x that makes P(x) false. This leads to the following outline for
disproving a universally quantified statement.
How to disprove ∀ x ∈ S, P(x).
Produce an example of an x ∈ S
that makes P(x) false.
Counterexamples
149
Things are even simpler if we want to disprove a conditional statement
P(x) ⇒ Q(x). This statement asserts that for every x that makes P(x) true,
Q(x) will also be true. The statement can only be false if there is an x that
makes P(x) true and Q(x) false. This leads to our next outline for disproof.
How to disprove P(x) ⇒ Q(x).
Produce an example of an x that
makes P(x) true and Q(x) false.
In both of the above outlines, the statement is disproved simply by
exhibiting an example that shows the statement is not always true. (Think
of it as an example that proves the statement is a promise that can be
broken.) There is a special name for an example that disproves a statement:
It is called a counterexample.
Example 9.1
As our first example, we will work through the process of
deciding whether or not the following conjecture is true.
Conjecture: For every n ∈ Z, the integer f (n) = n2 − n + 11 is prime.
In resolving the truth or falsity of a conjecture, it’s a good idea to gather
as much information about the conjecture as possible. In this case let’s
start by making a table that tallies the values of f (n) for some integers n.
n
−3
−2
−1
0
1
2
3
4
5
6
7
8
9
10
f (n)
23
17
13
11
11
13
17
23
31
41
53
67
83
101
In every case, f (n) is prime, so you may begin to suspect that the conjecture
is true. Before attempting a proof, let’s try one more n. Unfortunately,
f (11) = 112−11+11 = 112 is not prime. The conjecture is false because n = 11
is a counterexample. We summarize our disproof as follows:
Disproof. The statement “For every n ∈ Z , the integer f (n) = n2 − n + 11 is
prime, ” is false. For a counterexample, note that for n = 11, the integer
f (11) = 121 = 11 · 11 is not prime.
■
In disproving a statement with a counterexample, it is important to explain
would not have been complete if we had just said “for a counterexample,
consider n = 11,” and left it at that. We need to show that the answer f (11)
is not prime. Showing the factorization f (11) = 11 · 11 suffices for this.
150
Disproof
Example 9.2
Either prove or disprove the following conjecture.
Conjecture
If A, B and C are sets, then A − (B ∩ C) = (A − B) ∩ (A − C).
Disproof. This conjecture is false because of the following counterexample.
Let A = ©1, 2, 3ª, B = ©1, 2ª and C = ©2, 3ª. Notice that A − (B ∩ C) = ©1, 3ª and
(A − B) ∩ (A − C) = ;, so A − (B ∩ C) 6= (A − B) ∩ (A − C).
■
(To see where this counterexample came from, draw Venn diagrams for
A −(B∩C) and (A −B)∩(A −C). You will see that the diagrams are different.
The numbers 1, 2 and 3 can then be inserted into the regions of the
diagrams in such a way as to create the above counterexample.)
9.2 Disproving Existence Statements
We have seen that we can disprove a universally quantified statement or a
conditional statement simply by finding a counterexample. Now let’s turn
to the problem of disproving an existence statement such as
∃ x ∈ S, P(x).
Proving this would involve simply finding an example of an x that makes
P(x) true. To disprove it, we have to prove its negation ∼ (∃ x ∈ S, P(x)) =
∀ x ∈ S, ∼ P(x). But this negation is universally quantified. Proving it
involves showing that ∼ P(x) is true for all x ∈ S, and for this an example
does not suffice. Instead we must use direct, contrapositive or contradiction
proof to prove the conditional statement “If x ∈ S , then ∼ P(x) .” As an
example, here is a conjecture to either prove or disprove.
Example 9.3
Either prove or disprove the following conjecture.
Conjecture: There is a real number x for which x4 < x < x2.
This may not seem like an unreasonable statement at first glance. After
all, if the statement were asserting the existence of a real number for
which x3 < x < x2, then it would be true: just take x = −2. But it asserts
there is an x for which x4 < x < x2. When we apply some intelligent guessing
to locate such an x we run into trouble. If x = 12 , then x4 < x, but we don’t
have x < x2; similarly if x = 2, we have x < x2 but not x4 < x. Since finding
an x with x4 < x < x2 seems problematic, we may begin to suspect that the
given statement is false.
Let’s see if we can disprove it. According to our strategy for disproof,
Book of Proof Page 21
