asserts that a list of statements is “equivalent.” You saw this (or will see
it) in your linear algebra textbook, which featured the following theorem:
Theorem Suppose A is an n × n matrix. The following statements are
equivalent:
(a)
The matrix A is invertible.
(b)
The equation Ax = b has a unique solution for every b ∈ Rn.
(c)
The equation Ax = 0 has only the trivial solution.
(d) The reduced row echelon form of A is In.
(e)
det(A) 6= 0.
(f)
The matrix A does not have 0 as an eigenvalue.
When a theorem asserts that a list of statements is “equivalent,” it is
asserting that either the statements are all true, or they are all false.
Thus the above theorem tells us that whenever we are dealing with a
particular n × n matrix A, then either the statements (a) through (f) are all
true for A, or statements (a) through (f) are all false for A. For example, if
we happen to know that det(A) 6= 0, the theorem assures us that in addition
to statement (e) being true, all the statements (a) through (f) are true. On
the other hand, if it happens that det(A) = 0, the theorem tells us that all
statements (a) through (f) are false. In this way, the theorem multiplies
our knowledge of A by a factor of six. Obviously that can be very useful.
What method would we use to prove such a theorem? In a certain
sense, the above theorem is like an if-and-only-if theorem. An if-and-only-if
theorem of form P ⇔ Q asserts that P and Q are either both true or both
false, that is, that P and Q are equivalent. To prove P ⇔ Q we prove P ⇒ Q
followed by Q ⇒ P, essentially making a “cycle” of implications from P to Q
124
Proving Non-Conditional Statements
and back to P. Similarly, one approach to proving the theorem about the
n × n matrix would be to prove the conditional statement (a) ⇒ (b), then
(b) ⇒ (c), then (c) ⇒ (d), then (d) ⇒ (e), then (e) ⇒ (f ) and finally (f ) ⇒ (a).
This pattern is illustrated below.
(a)
=⇒ (b) =⇒
(c)
⇑
⇓
( f )
⇐= (e) ⇐= (d)
Notice that if these six implications have been proved, then it really does
follow that the statements (a) through (f) are either all true or all false. If
one of them is true, then the circular chain of implications forces them
all to be true. On the other hand, if one of them (say (c)) is false, the fact
that (b) ⇒ (c) is true forces (b) to be false. This combined with the truth of
(a) ⇒ (b) makes (a) false, and so on counterclockwise around the circle.
Thus to prove that n statements are equivalent, it suffices to prove n
conditional statements showing each statement implies another, in circular
pattern. But it is not necessary that the pattern be circular. The following
schemes would also do the job:
(a)
=⇒ (b) ⇐⇒
(c)
⇑
⇓
( f )
⇐= (e) ⇐⇒ (d)
(a)
⇐⇒ (b) ⇐⇒
(c)
m
( f )
⇐⇒ (e) ⇐⇒ (d)
But a circular pattern yields the fewest conditional statements that
must be proved. Whatever the pattern, each conditional statement can be
proved with either direct, contrapositive or contradiction proof.
Though we shall not do any of these proofs in this text, you are sure to
encounter them in subsequent courses.
7.3 Existence Proofs; Existence and Uniqueness Proofs
Up until this point, we have dealt with proving conditional statements
or with statements that can be expressed with two or more conditional
statements. Generally, these conditional statements have form P(x) ⇒ Q(x).
(Possibly with more than one variable.) We saw in Section 2.8 that this
can be interpreted as a universally quantified statement ∀ x, P(x) ⇒ Q(x).
Existence Proofs; Existence and Uniqueness Proofs
125
Thus, conditional statements are universally quantified statements, so
in proving a conditional statement—whether we use direct, contrapositive
or contradiction proof—we are really proving a universally quantified
statement.
But how would we prove an existentially quantified statement? What
technique would we employ to prove a theorem of the following form?
∃ x, R(x)
This statement asserts that there exists some specific object x for which
R(x) is true. To prove ∃ x, R(x) is true, all we would have to do is find and
display an example of a specific x that makes R(x) true.
Though most theorems and propositions are conditional (or if-and-
only-if) statements, a few have the form ∃ x, R(x). Such statements are
called existence statements, and theorems that have this form are called
existence theorems. To prove an existence theorem, all you have to do
is provide a particular example that shows it is true. This is often quite
simple. (But not always!) Here are some examples:
Proposition
There exists an even prime number.
Proof. Observe that 2 is an even prime number.
■
Admittedly, this last proposition was a bit of an oversimplification. The
next one is slightly more challenging.
Proposition
There exists an integer that can be expressed as the sum
of two perfect cubes in two different ways.
Proof. Consider the number 1729. Note that 13 + 123 = 1729 and 93 + 103 =
1729. Thus the number 1729 can be expressed as the sum of two perfect
cubes in two different ways.
■
Sometimes in the proof of an existence statement, a little verification is
needed to show that the example really does work. For example, the above
proof would be incomplete if we just asserted that 1729 can be written as
a sum of two cubes in two ways without showing how this is possible.
WARNING: Although an example suffices to prove an existence statement,
a single example does not prove a conditional statement.
126
Proving Non-Conditional Statements
Often an existence statement will be embedded inside of a conditional
statement. Consider the following. (Recall the definition of gcd on page 90.)
If a, b ∈ N, then there exist integers k and ` for which gcd(a, b) = ak + b `.
This is a conditional statement that has the form
a, b ∈ N =⇒ ∃ k, ` ∈ Z, gcd(a, b) = ak + b `.
To prove it with direct proof, we would first assume that a, b ∈ N, then
prove the existence statement ∃ k, ` ∈ Z, gcd(a, b) = ak + b `. That is, we
would produce two integers k and ` (which depend on a and b) for which
gcd(a, b) = ak + b `. Let’s carry out this plan. (We will use this fundamental
proposition several times later, so it is given a number.)
Proposition 7.1
If a, b ∈ N, then there exist integers k and ` for which
gcd(a, b) = ak + b `.
Proof. (Direct) Suppose a, b ∈ N. Consider the set A = ©ax + b y : x, y ∈ Zª.
This set contains both positive and negative int
egers, as well as 0. (Reason:
Let y = 0 and let x range over all integers. Then ax + b y = ax ranges over
all multiples of a, both positive, negative and zero.) Let d be the smallest
positive element of A. Then, because d is in A, it must have the form
d = ak + b ` for some specific k, ` ∈ Z.
To finish, we will show d = gcd(a, b). We will first argue that d is a
common divisor of a and b, and then that it is the greatest common divisor.
To see that d | a, use the division algorithm (page 29) to write a = qd + r
for integers q and r with 0 ≤ r < d. The equation a = qd + r yields
r
= a − qd
= a − q(ak + b `)
= a(1 − qk) + b(−q `).
Therefore r has form r = ax + b y, so it belongs to A. But 0 ≤ r < d and d
is the smallest positive number in A, so r can’t be positive; hence r = 0.
Updating our equation a = qd + r, we get a = qd, so d | a. Repeating this
argument with b = qd + r shows d | b. Thus d is indeed a common divisor
of a and b. It remains to show that it is the greatest common divisor.
As gcd(a, b) divides a and b, we have a = gcd(a, b)·m and b = gcd(a, b)·n for
some m, n ∈ Z. So d = ak+ b ` = gcd(a, b)· mk+gcd(a, b)· n ` = gcd(a, b)¡mk+ n `¢,
and thus d is a multiple of gcd(a, b). Therefore d ≥ gcd(a, b). But d can’t
be a larger common divisor of a and b than gcd(a, b), so d = gcd(a, b).
■
Existence Proofs; Existence and Uniqueness Proofs
127
We conclude this section with a discussion of so-called uniqueness
proofs. Some existence statements have form “There is a unique x for
which P(x).” Such a statement asserts that there is exactly one example x
for which P(x) is true. To prove it, you must produce an example x = d for
which P(d) is true, and you must show that d is the only such example.
The next proposition illustrates this. In essence, it asserts that the set
©ax + by : x, y ∈ Zª consists precisely of all the multiples of gcd(a, b).
Proposition
Suppose a, b ∈ N. Then there exists a unique d ∈ N for which:
An integer m is a multiple of d if and only if m = ax + b y for some x, y ∈ Z.
Proof. Suppose a, b ∈ N. Let d = gcd(a, b). We now show that an integer m
is a multiple of d if and only if m = ax+ b y for some x, y ∈ Z. Let m = dn be a
multiple of d. By Proposition 7.1 (on the previous page), there are integers
k and ` for which d = ak + b `. Then m = dn = (ak + b `)n = a(kn) + b( ` n), so
m = ax + b y for integers x = kn and y = ` n.
Conversely, suppose m = ax + b y for some x, y ∈ Z. Since d = gcd(a, b) is
a divisor of both a and b, we have a = d c and b = d e for some c, e ∈ Z. Then
m = ax + b y = dcx + de y = d(cx + e y), and this is a multiple of d.
We have now shown that there is a natural number d with the property
that m is a multiple of d if and only if m = ax + b y for some x, y ∈ Z. It
remains to show that d is the unique such natural number. To do this,
suppose d0 is any natural number with the property that d has:
m is a multiple of d0 ⇐⇒ m = ax + b y for some x, y ∈ Z.
(7.1)
We next argue that d0 = d; that is, d is the unique natural number with
the stated property. Because of (7.1), m = a · 1 + b · 0 = a is a multiple of d0.
Likewise m = a · 0 + b · 1 = b is a multiple of d0. Hence a and b are both
multiples of d0, so d0 is a common divisor of a and b, and therefore
d0 ≤ gcd(a, b) = d.
But also, by (7.1), the multiple m = d0 · 1 = d0 of d0 can be expressed as
d0 = ax+ b y for some x, y ∈ Z. As noted in the second paragraph of the proof,
a = dc and b = de for some c, e ∈ Z. Thus d0 = ax + b y = dcx + de y = d(cx + e y),
so d0 is a multiple d. As d0 and d are both positive, it follows that
d ≤ d0.
We’ve now shown that d0 ≤ d and d ≤ d0, so d = d0. The proof is complete.
■
128
Proving Non-Conditional Statements
7.4 Constructive Versus Non-Constructive Proofs
Existence proofs fall into two categories: constructive and non-constructive.
Constructive proofs display an explicit example that proves the theorem;
non-constructive proofs prove an example exists without actually giving it.
We illustrate the difference with two proofs of the same fact: There exist
irrational numbers x and y (possibly equal) for which xy is rational.
Proposition
There exist irrational numbers x, y for which xy is rational.
p p2
p
Proof. Let x = 2
and y =
2. We know y is irrational, but it is not clear
whether x is rational or irrational. On one hand, if x is irrational, then
we have an irrational number to an irrational power that is rational:
p
p
p p
µp
2
2¶
p
2 2
p 2
xy =
2
= 2
= 2 = 2.
p p2
On the other hand, if x is rational, then yy =
2
= x is rational. Either
way, we have a irrational number to an irrational power that is rational.
■
The above is a classic example of a non-constructive proof. It shows
that there exist irrational numbers x and y for which xy is rational without
actually producing (or constructing) an example. It convinces us that one
p p p
p p
¡
2¢ 2
2
of
2
or
2
is an irrational number to an irrational power that
is rational, but it does not say which one is the correct example. It thus
proves that an example exists without explicitly stating one.
Next comes a constructive proof of this statement, one that produces
(or constructs) two explicit irrational numbers x, y for which xy is rational.
Proposition
There exist irrational numbers x, y for which xy is rational.
p
Proof. Let x = 2 and y = log2 9. Then
p log
p log
p 2log
³p 2ĺog2 3
xy = 2 2 9 = 2 2 32 = 2
2 3 =
2
= 2log2 3 = 3.
As 3 is rational, we have shown that xy = 3 is rational.
p
We know that x =
2 is irrational. The proof will be complete if we
can show that y = log2 9 is irrational. Suppose for the sake of contradiction
a
that log2 9 is rational, so there are integers a and b for which b = log2 9.
¡
This means 2a/b = 9, so 2a/b¢b = 9b, which reduces to 2a = 9b. But 2a is even,
while 9b is odd (because it is the product of the odd number 9 with itself
b times). This is a contradiction; the proof is complete.
■
Constructive Versus Non-Constructive Proofs
129
This existence proof has inside of it a separate proof (by contradiction)
that log2 9 is irrational. Such combinations of proof techniques are, of
course, typical.
Be alert to constructive and non-constructive proofs as you read proofs
in other books and articles, as well as to the possibility of crafting such
proofs of your own.
Exercises for Chapter 7
Prove the following statements. These exercises are cumulative, covering all
techniques addressed in Chapters 4–7.
1. Suppose x ∈ Z. Then x is even if and only if 3x + 5 is odd.
2. Suppose x ∈ Z. Then x is odd if and only if 3x + 6 is odd.
3. Given an integer a, then a3 + a2 + a is even if and only if a is even.
4. Given an integer a, then a2 + 4a + 5 is odd if and only if a is even.
5. An integer a is odd if and only if a3 is odd.
6. Suppose x, y ∈ R. Then x3 + x2 y = y2 + xy if and only if y = x2 or y = −x.
7. Suppose x, y ∈ R. Then (x + y)2 = x2 + y2 if and only if x = 0 or y = 0.
8. Suppose a, b ∈ Z. Prove that a ≡ b (mod 10) if and only if a ≡ b (mod 2) and a ≡ b
(mod 5).
9. Suppose a ∈ Z. Prove that 14 | a if and only if 7 | a and 2 | a.
10. If a ∈ Z, then a3 ≡ a (mod 3).
11. Suppose a, b ∈ Z. Prove that (a − 3)b2 is even if and only if a is odd or b is even.
p
12. There exist a positive real number x for which x2 < x.
13. Suppose a, b ∈ Z. If a + b is odd, then a2 + b2 is odd.
14. Suppose a ∈ Z. Then a2 | a if and only if a ∈ © − 1,0,1ª.
15. Suppose a, b ∈ Z. Prove that a + b is even if and only if a and b have the same
parity.
16. Suppose a, b ∈ Z. If ab is odd, then a2 + b2 is even.
17. There is a prime number between 90 and 100.
18. There is a set X for which N ∈ X and N ⊆ X .
19. If n ∈ N, then 20 + 21 + 22 + 23 + 24 + ··· + 2n = 2n+1 − 1.
20. There exists an n ∈ N for which 11 | (2n − 1).
21. Every real solution of x3 + x + 3 = 0 is irrational.
22. If n ∈ Z, then 4 | n2 or 4 | (n2 − 1).
23. Suppose a, b and c are integers. If a | b and a | (b2 − c), then a | c.
24. If a ∈ Z, then 4 - (a2 − 3).
130
Proving Non-Conditional Statements
p
25. If p > 1 is an integer and n - p for each integer n for which 2 ≤ n ≤ p, then p is
prime.
26. The product of any n consecutive positive integers is divisible by n!.
27. Suppose a, b ∈ Z. If a2 + b2 is a perfect square, then a and b are not both odd.
28. Prove the division algorithm: If a, b ∈ N, there exist unique integers q, r for
which a = bq + r, and 0 ≤ r < b. (A proof of existence is given in Section 1.9, but
uniqueness needs to be established too.)
29. If a | bc and gcd(a, b) = 1, then a | c.
(Suggestion: Use the proposition on page 126.)
Book of Proof Page 18