Bridge to Abstract Mathematics: Mathematical Proof and Structures

166 METHODS OF MATHEMATICAL PROOF, PART I Chapter 5

and B $ A. To prove the latter, we must prove (3x)[(x E B) A (x $ A)]. This

is generally best done by producing a specific object x which is in B, but

not in A [see Exercise 7(b)].

PROVING STATEMENTS (Vx)(p(x) * q(x))

The relationship between statements of the form (Vx)(p(x) * q(x)) and those

of the form (Vx)(p(x) -, q(x)) is the same as the one we noted in Article

4.1 between set equality A = B and set inclusion A c B. Recall that A = B

if and only if A G B and B c A, so that, for instances where a proof by

transitivity (cf., Article 5.1) of equality isn't possible or evident, we prove

equality of sets by proving mutual inclusion. This kind of proof of set

equality, then, involves two proofs, one in each direction, as in Example 9,

Article 4.1.

The logical basis for this approach to sets, as well as for the approach we

wish to take now in more general situations, is the equivalence

The first equivalence follows from the tautology

(p C+ q) C+ [(p -, q) A (q -, p)] [Theorem l(m), Article 2.31

whereas the second follows from the equivalence

(VX)[~(X) A ~(x)] ++ (vx)(r(x)) A (Vx)(s(x)) [Theorem l(c), Article 3.31

Thus we may write a proof of equivalence by writing two proofs of implica-

tion of the type we've been discussing thus far in this article, one in each

direction.

EXAMPLE 12 Let f be a real-valued function with domain R. Prove that f

is even; that is, f (- x) = f (x) for all x E R (recall Exercise 9, Article 5.1)

if and only if the set of points in the xy plane C = ((x, f(x)) lx E R} is

symmetric with respect to the y axis.

Solution Again, we must argue in two directions. Such proofs are often

presented in the following format:

(3) (This arrow means we are proving that iff is even, then C is

symmetric.) Suppose f is even. To prove the set C = {(x, f(x))lx E R} is

symmetric with respect to the y axis, let (x, y) E C. We must prove

( - x, y) E C, that is, prove that y = f (- x). Now since (x, y) E C, then

y = f (x). Since f is even, we have f (x) = f ( - x). Hence y = f (x) =

f(-x), SO that y = f(-x), as desired..

(=) Conversely, suppose that C is symmetric with respect to the y

axis. To prove f is even, let x E R be arbitrarily chosen. We must show

that f ( - x) = f (x). By definition of C, the point (x, f (x)) E C. By the as-

sumed symmetry, since (x, f (x)) E C, then (- x, f (x)) E C. Now, again by