Bridge to Abstract Mathematics: Mathematical Proof and Structures

164 METHODS OF MATHEMATICAL PROOF, PART I Chapter 5

As we did after Example 7, let us rewrite the preceding proof with ex-
planatory comments removed. That is, let us write a version of the proof
more closely resembling the finished product form of most proofs that
appear in print. "Assume A, B, and C are sets with A x B c A x C and
A # 0. To prove B c C, let x E B. We must show x E C. Since A # 0,
there exists a E A, so that (a, x) E A x B. Since A x B E A x C, then
(a, x) E A x C. Hence x E C, as desired."
We noted in the preceding paragraph that the version of the proof given
there corresponds to a "finished product." In practice, most mathemati-
cians write their original proofs in two forms. The first may cover reams of
paper and involve a number of false starts and failed attempts. More im-
portant, this form of a successful proof will usually reveal the "discovery
process" of the proof. The second form is the one that a mathematician
shows to other people, a compact, cleaned-up, final, elegant kind of proof
in which the discovery process may not be shown. In order to understand
and communicate mathematics, you must learn to read and write proofs
in the latter form. Most proofs contained in our "Solutions," thus far in
the text, have more closely resembled the first form. We have tried thereby
to expose the thought process and to emphasize common pitfalls involved
in the formative stages of a proof. In Book I1 (Chapter 7 through 10) we
will place much more emphasis on writing proofs in compact form only,
with more responsibility left to you for understanding the idea behind the
proof.

DISPROVING CONCLUSIONS OF THE FORM (Vx)(p(x) + q(x))

Suppose now that we wish to disprove a statement whose logical form is

(Vx)(p(x) -, q(x)). Recall first the discussion following Example 8 in Article

5.1. From that discussion, it would be expected that we generally disprove

such a statement by giving a specific counterexample rather than a general

deductive proof. We must use logic carefully, however, to determine pre-.

cisely what constitutes a counterexample. In Article 3.3 we saw that the

negation of (Vx)(p(x) -, q(x)) is (3x)[- (p(x) -, q(x))]. In Article 2.3 we saw

that - (p -, q) is logically equivalent to p A - q. Thus - [(Vx)(p(x) -+ q(x)]

is logically equivalent to (3x)(p(x) A -- q(x)). To disprove a statement of the

form (Vx)(p(x) + q(x)), we must show that some value of x exists for which

p(x) is true and q(x) is false. In most elementary situations this is done by

producing specifically such an x. Let us apply this principle to some of

the definitions stated at the outset of this article.

EXAMPLE 10 Write definitions of "a curve C is not symmetric with respect

to the x axis" and "a set of vectors (v,, v,,... , v,) in a real vector space

V is not linearly independent."

Solution Recall from Example^1 that C is symmetric with respect to the

x axis if and only if, for all real numbers x and y, (x, y) E C implies

(x, - y) E C. Hence C is not symmetric with respect to the x axis if and