Bridge to Abstract Mathematics: Mathematical Proof and Structures

(Dana P.) #1
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.

Free download pdf