4.1 APPLICATIONS OF LOGIC TO SET THEORY-SOME PROOFS 117The proofs we have given in Examples 1 through 3 make explicit reference
to logical principles from Chapters 2 and 3. In actual practice, the style of
proof writing that mathematicians use in proving less basic results about
set inclusion and equality is not quite so formal. As one becomes more
experienced in writing proofs, the underlying logical principles are used
in a (hopefully correct, but) less explicit manner. The point of departure
toward writing such proofs is a method of proof so widely applicable that
its importance cannot be stressed strongly enough. It might be called the
"elementhood" method, the "choose" method, or the "pick-a-point" method,
Whatever it's called, the principle sets forth:
The direct way to prove that a set A is a subset of a set B is to start by
letting a symbol x represent an arbitrary element of A. This element,
though generic (i.e., not a specifically identified or named element of A),
is to remain fixed throughout the proof. The proof is carried out by
deducing, through methods depending on the specifics of the problem
at hand, that this x must be an element of B.The proofs in Examples 4 and 5, below, constitute our introduction to this
method.
Using the notation of Chapters 2 and 3, we can reformulate the definitions
of the operations intersection, union, complement, and difference in terms
of the logical connectives and quantifiers. This is the object of Exercise 1.
Some proofs of elementary theorems of set theory are now direct conse-
quences of corresponding theorems of the propositional calculus.
EXAMPLE 4 Prove that, for any sets A and B, A n B E A and A S A u B
[Fact 2, (20), (19), Article 1.4).
Solution To prove that A n B E A by the elementhood method, we begin
by letting x be an arbitrary element of A n B. We must prove that &&
x - is an element of A. Now since x E A n B, then x E A and x E B.
Hence x E A, as desired, where we note that the last step makes implicit
use of the tautology (p A q) -t p [Theorem 2(c), Article 2.31.
To prove that A G A u B, let x E A be given. We must prove that
x E A u B; that is, either x E A or x E B. Since x E A, the latter statement
follows directly. (What tautology is being used in passing from the
assumption "XE A" to the conclusion "either x E A or x E B?)EXAMPLE 5 Prove that, for any sets A and B, A E (A u B) n (A u B').
Solution Let x be an arbitrary element of A. In order to prove that
x E (A u B) n (A u B'), we must prove that x E A u B x E A u B'.
Since x E A, then x E A u B, by Example 4. The same result implies that
x E A u B' as well. Thus x E (A u B) n (A u B'), as desired.
In Article 5.1, Exercise 4, you are to prove that, in fact, A =
(A u B) n (A u B') for any two sets A and B.