122 ELEMENTARY APPLICATIONS OF LOGIC Chapter 4On the other hand, suppose x E X u 0; we must prove x E X. Now, by
our supposition, either x E X or x E 0. But x E @ is false, so we may
conclude x E X, as desired. {Note: We have implicitly used the tau-
tology [(p v q) A --p] -, q, Theorem 2(k), Article 2.3, in the preceding
sentence. The tautologies of the propositional calculus are of vital
importance for writing proofs in mathematics!)The technique used in the first part of the proof of Example 13 (letting
Y = @ in the known theorem X c X u Y to conclude X c X u @) is called
specialization, which we will focus on in Article 5.3.
The point was made earlier that we cannot employ the choose approach
("let x E 0'') to prove @ G A. The perceptive reader may have thought
of the following objection to a number of the proofs presented in this article.
In Example 4, for instance, we began the proof that A n B c A with the
step "let x E A n B." But what if A n B = @? The argument given does
not apply in this case; we cannot choose an element from @. More generally,
whenever we prove a set X is a subset of a set Y by using the choose
method, the argument applies only to the case "X nonempty." Again
what if X is empty? The answer to this dilemma is an implicit "division
into cases" [recall Example 8(a)] with the two cases (1) X nonempty and
(2) X empty. In case (1) the proof proceeds by using the choose method,
as in all our earlier examples. In case (2) the desired result follows directly
from the result in Example 1, with no further proof required. As stated
previously, this division into cases is "implicit." That is, since the case "X
empty" is trivially true whenever we prove X c Y, we do not normally
make explicit reference to it when proving set containment.
The proofs in the exercises that follow may not be enjoyable. For very
elementary, and seemingly obvious, theorems in mathematics, it is some-
times difficult, or frustrating, to try to write a proof, since there often
appears to be little or nothing to say. Two remarks may alleviate this
problem somewhat: (1) We will give hints, for many of the exercises, of
how you should proceed or to what example(@ you should refer. In this
connection we note that a key step in proving many "obvious" theorems
of set theory, such as Exercise 5, is identifying explicitly the relevant
tautology, as we did in Examples 4, 6, 10, and 13, among others. (2) We
promise more interesting (and less vacuous) proofs of theorems in set theory,
as well as in other areas of undergraduate mathematics, in Chapter 5.
Exercises
We assume as axioms throughout these exercises that x E U for any object x (U
being a universal set) and that U # fa.- Formulate definitions of A n B, A u B, A', and A - B using set-builder notation
and the logical connectives introduced in Chapters 2 and 3.