5.2 CONCLUSIONS INVOLVING V AND +, BUT NOT 3 163Solution You may recall this result as one that we assumed and used in the
solution to Example 8, Article 5.1. To prove it, we proceed, as in Ex-
amples 6 and 7, by concentrating at the outset on the desired conclusion. A n X c A n Y; we use the hypothesis X E Y in the course of the
argument. Now, how do we go about showing that one set is a subset
of another? We saw in Article 4.1 that this is done by choosing an ar-
bitrary element from the first set and trying to show that this object lies
in the second set as well. In this case we begin by letting x be an element
of A n X. We must show that this x lies in A n Y. Somewhere along the
line, we will have to use the hypothesis X E Y. So to start, let x E A n X
be given. To show that x E A n Y, we must prove that x E A and x E Y.
Now since x E A n X and A n X E A, then x E A. Also, since x E
A n X, then x E X. But X c Y, by hypothesis, so that since x E X and
X _c Y, we must have x E Y. Since x E A and x E Y, then x E A n Y, as
desired.
A common error in a proof such as that in Example 8, committed even
by students who understand the general pick-a-point approach to proving
set inclusion, is to begin the proof in the wrong place, setting it up with
reference to the hypothesis rather than to the conclusion. Specifically, in
trying to prove that X E Y implies A n X c A n Y, many students will er-
roneously write as their first step "let x E X" rather than the correct "let
x E A n X." Also, since we have repeatedly suggested focusing on the de-
sired conclusion rather than on the hypotheses in setting up a proof, it
is perhaps appropriate that we emphasize that this guiding rule is not to be
confused with the common error of beginning a proof by assuming the con-
clusion. The latter approach, of course, is never valid. In the proof from
Example 8 this mistaken approach would have involved starting with the
statement "assume (or suppose) that A n X c A n Y." This is different
from the approach we took ("let x E A n X. We must prove x E A n Y.. .").
Here is a slightly more complicated example from set theory.EXAMPLE 9 Prove that if A, B, and C are sets with A x B E A x C and
A # 0, then BE C.
Solution Again, we focus first on our desired conclusion. We begin the
proof that B G C by letting x be an arbitrary element of B. Our goal is
to prove x E C. We have at our disposal the hypotheses A = 0 and
A x B c A x C. We must determine how to make use of these hypoth-
eses. Think about this for a while before proceeding; for instance, what
is the significance of the hypothesis that A is nonempty? Let us resume.
Since A # 0, then A contains at least one element, call it a. Since a E A
and x E B, then the ordered pair (a, x) is an element of A x B. Do you
see the next step? Since A x B c A x C, by hypothesis, and since
(a, x) E A x B, then (a, x) must be an element of A x C. But this implies
x E C and this is precisely what we wanted to prove. 0