Bridge to Abstract Mathematics: Mathematical Proof and Structures

210 METHODS OF MATHEMATICAL PROOF, PART II Chapter 6

Two classic proofs by contradiction are the proofs that fi is irrational

and that there exist infinitely many primes. The latter will be held off until

the next article; proof by contradiction is one of the primary methods of

proving existence, part of the subject of that article. We consider the former

in the next example.

EXAMPLE 9 Prove that fi is irrational; that is, there do not exist integers

p and q such that (p/q)2 = 2.

Solution Proceeding by contradiction, we suppose that such integers exist.

Note that if any such pair of integers exists, as we suppose, then surely

a pair (p, q) exists having no factors in common. Now 2 = (p/q)2 =

(p2/q2) means that 2q2 = p2. Hence p2 is even. By Exercise 6(a), p is

even. Hence we can express p as p = 2n, where n is an integer. Hence

2q2 = p2 = (2n)2 = 4n2, so that q2 = 2n2. This means that q2 is even so

that q is even, again by Exercise 6(a). Hence p and q are both even; but

this contradicts the assumption that p and q have no factors in common.

Thus a pair of integers of the type described at the outset must not exist,

as desired.

Exercises

1. Let A, B, and C be sets. Prove:
   (a) Ax@=@
   (b) If A x B = A x C, then either A = (21 or B = C
   (c) If A x B = B x A, then either A = (21, B = (21, or A = B
   (d) If A x B = (21, then either A = 0 or B = (21
   (e) (A x C) - (B x C) c (A - B) x C [recall Exercise 4(d), Article 6.11.
   (f) If A n B' = 0, then A E B [recall Example 12, Article 4.1. How is the theo-
   rem of that example related to the result of this exercise?].
   (g) If A' u B = U, then A r B [recall Exercise 8(a), Article 4.1 and Exercise lqc),
   Article 3.21
   (h) If (A' v B) n (A u B') = U, then A = B [recall Exercise 3(g), Article 5.1 and
   Exercise 9(c), Article 3.21.


2. Suppose it is known that if m, a, and b are integers such that m divides ab, and
   m and a have no factors in-common, then m divides b. Suppose also that it is
   known that if m is prime, then either mla or m has no factors in common with a.
   Use these facts to prove that if p, a, and b are integers such that p is prime and
   p 1 ab, then either p divides a or p divides b.


3. (a) Verify, by using a truth table, the tautology

(b) (i) Prove that if A, B, C, and D are nonempty sets such that A x B c C x D,
I then A E C B c D.