Unions and Intersections: Proving Sets

Date: 10/17/1999 at 18:33:04
From: Don Edgar
Subject: Proving sets with unions and intersections

The question given to me is: A student is asked to prove that for any 
sets A, B and C; A - (B union C) = (A - B) intersect (A - C). The 
student writes 'Let x be an element of A - (B union C). Then x is an 
element of A and x is not an element of B, or x is not an element of 
C. Therefore, x is an element of A - B and x is an element of A - C. 
Thus, A - (B union C) = (A - B) intersect (A - C).' What, if anything, 
is wrong with this proof?

I have no idea what to do or how to go about this. I'm not sure if 
he's right or not or how he even came up with that thinking. If you 
could help me I would be most appreciative.

Thank you very much.
DE

Date: 10/17/1999 at 22:06:06
From: Doctor Ian
Subject: Re: Proving sets with unions and intersections

Hi Don,

I'm going to reformat the proof so I can refer to specific parts of 
it:

     [1] Let x be an element of A-(B union C).  

     [2] Then x is an element of A 
         and x is not an element of B 
         or x is not an element of C.  

     [3] Therefore, x is an element of A - B 
         and x is an element of A - C.  

     [4] Thus, A-(B union C) = (A - B)intersect(A - C).

Technically, the third line of [2] should begin with 'and' instead of 
'or'. Other than that, it's correct.  

It's easier to see what's going on with pictures. And the pictures are 
a lot better looking if you use overlapping circles instead of 
rectangles, but I have to do this with a keyboard, so...

Imagine three sets - A, B and C - represented by three overlapping 
rectangles.

            +---------------+
            |            B  |
   +--------|----+          |      (Figure 1)
   | A      |    |          |
   |        |    |          |
   |   +--------------+     |
   |   |    |    |    |     |
   |   |    +----|----------+
   |   |         |    |
   +---|---------+    |
       |              |
       |      C       |
       +--------------+

The union of B and C is everything that is in B, or in C, or both:

            +---------------+
            |XXXXXXXXXXXXXXX|
   +--------|----+XXXXXXXXXX|      (Figure 2)
   | A      |XXXX|XXXXXXXXXX|
   |        |XXXX|XXXXXXXXXX|
   |   +--------------+XXXXX|
   |   |XXXX|XXXX|XXXX|XXXXX|
   |   |XXXX+----|----------+
   |   |XXXXXXXXX|XXXX|
   +---|---------+XXXX|
       |XXXXXXXXXXXXXX|
       |XXXXXXXXXXXXXX|
       +--------------+

The part left unfilled in the diagram above is everything that is in A 
that isn't in the union of B and C -- in other words, A - (B union C).

A - B is everything that is in A that isn't also in B:

            +---------------+
            |            B  |
   +--------|----+          |      (Figure 3)
   |XXXXXXXX|    |          |
   |XXXXXXXX|    |          |
   |XXX+--------------+     |
   |XXX|XXXX|    |    |     |
   |XXX|XXXX+----|----------+
   |XXX|XXXXXXXXX|    |
   +---|---------+    |
       |              |
       |      C       |
       +--------------+

A - C is everything that is in A that isn't also in C:

            +---------------+
            |            B  |
   +--------|----+          |      (Figure 4)
   |XXXXXXXX|XXXX|          |
   |XXXXXXXX|XXXX|          |
   |XXX+--------------+     |
   |XXX|    |    |    |     |
   |XXX|    +----|----------+
   |XXX|         |    |
   +---|---------+    |
       |              |
       |      C       |
       +--------------+

The intersection of these two sets is the part they have in common,

            +---------------+
            |            B  |
   +--------|----+          |      (Figure 5)
   |XXXXXXXX|    |          |
   |XXXXXXXX|    |          |
   |XXX+--------------+     |
   |XXX|    |    |    |     |
   |XXX|    +----|----------+
   |XXX|         |    |
   +---|---------+    |
       |              |
       |      C       |
       +--------------+

The part that is left unfilled in Figure 2 is A - (B union C).

The part that is filled in Figure 5 is (A - B) intersect (A - C).

They're the same. So A - (B union C) = (A - B) intersect (A - C).

Now let's look at the (corrected) proof again:

     [1] LET x BE AN ELEMENT OF A - (B UNION C).  

           This is given. 

     [2] THEN x IS AN ELEMENT OF A 

           Because it's in the part of A that isn't in some other set,
           so it must at least be in A.

         AND X IS NOT AN ELEMENT OF B 

           Because if it were an element of B, it would be in
           B union C.

         AND X IS NOT AN ELEMENT OF C.  

           Because if it were an element of C, it would be in 
           B union C. 

     [3] THEREFORE X IS AN ELEMENT OF A - B 

           Because it's in A, but not in B. 

         AND X IS AN ELEMENT OF A - C.  

           Because it's in A, but not in C. 

     [4] THUS, A - (B UNION C) = (A - B) INTERSECT (A - C).

           Because it's in both (A - B) and in (A - C). 

I hope this helps. Be sure to write back if you're still confused, or 
if you have any other questions. 

- Doctor Ian, The Math Forum
  http://mathforum.org/dr.math/