Unions and Intersections

Date: 05/10/99 at 20:32:02
From: justin cole
Subject: Unions and intersections - their relation

In our discussion in class we showed that the number of elements in 
sets A, B, and C, their unions, and their intersections, have the 
following relation (I have to use u = unions and n = intersections 
because those are the only keys that even come close to looking like 
the symbols):

N(A u B u C) = N(A)+N(B)+N(C)-N(A n B)-N(B n C)-N(C n A)+N(A n B n C)

Generalize the formula for the four-set situation. Apply the newly 
derived formula to find the numbers between (2000,3000) that are 
multiples of 3, 5, 7, or 11.

You are my last hope.
Thank you.

Date: 05/11/99 at 09:17:45
From: Doctor Peterson
Subject: Re: Unions and intersections - their relation

Hi, Justin.

Let's see if we can understand the three-set formula well enough to 
allow you to extend the idea. To do that, we'll get a running start by 
looking first at two sets.

How are the union and intersection of two sets related? Suppose we 
have two sets like this:

            *********   +++++++++
         ***         +++         +++
       **          ++   **          ++
      *           +       *           +
     *           +         *           +
    *           +           *           +
    *    A      +    AnB    *      B    +
    *           +           *           +
     *           +         *           +
      *           +       *           +
       **          ++   **          ++
         ***         +++         +++
            *********   +++++++++

The size of the union is like the area covered by the two circles. If 
I paint circle A red and circle B green, I will have covered an area 
equal to the size of A and the size of B; but I will have covered the 
intersection twice, once with each color. So I will have used a total 
amount of paint that is:

    size(A) + size(B)

which is the sum of the amount of paint in each layer:

               BBBBBBBBBBBBBBBBBBBBBBBBBB
    AAAAAAAAAAAAAAAAAAAAAAAA

but can also be thought of as

    size(AuB) + size(AnB)

which is the sum of the amount of the bottom layer of paint 
everywhere, plus the size of the top layer of paint wherever there are 
two layers:

               2222222222222
    1111111111111111111111111111111111111

So I can calculate the size of the union by subtracting size(AnB) from 
the sum of size(A) and size(B):

    size(AuB) = size(A) + size(B) - size(AnB)

      ***+++       ***       +++
     *      +     *   *     +   +     +*
    *        + = *     * + +     + - +  *
     *      +     *   *     +   +     +*
      ***+++       ***       +++

Now what happens if we add a third circle?

            *********   +++++++++
         ***         +++         +++
       **          ++   **          ++
      *           +       *           +
     *    A      +   AnB   *       B   +
    *           +           *           +
    *           + xxxxxxxxxx*           +
    *          xxx          xxx         +
     *       xx  +  AnBnC  *   xx      +
      *     x     +       *      x    +
       **  x  AnC  ++   **  BnC   x ++
         *x*         +++         ++x
          x *********   +++++++++  x
          x                        x
           x                      x
            x         C          x
             xx                xx
               xxx          xxx
                  xxxxxxxxxx

Side view:

    AAAAAAAAAAAAAAAAAAAAAAAA
                 BBBBBBBBBBBBBBBBBBBBBBBBB
           CCCCCCCCCCCCCCCCCCCCCCCC

Now if I paint circle C blue, I have one layer of paint on some parts; 
two layers on others; and three layers on AnBnC. In trying to get the 
size of the union, if I add the sizes of A, B, and C, I will have 
counted some areas twice and others three times. So I have to subtract 
the size of the region where there are two colors of paint, and then 
subtract the size of the triple overlap:

                 33333333333
           22222222222222222222222
    11111111111111111111111111111111111111

The area of the third layer is just AnBnC; but how can I find the area 
of the second layer? If I add AnB + BnC + AnC, I will have counted 
AnBnC three times. When I subtract that, I'll be taking off AnBnC two 
extra times, instead of just one extra time, so I have to add it back 
on. So the size of the union is

    size(AuBuC) = size(A) + size(B) + size(C)
                  - (size(AnB) + size(BnC) + size(AnC))
                  + size(AnBnC)

      ***+++       ***       +++
     *      +     *   *     +   +
    *        +   *     *   +     +     xxxx
     *      +  =  *   *  +  +   +  +  x    x
     x      x      ***       +++     x      x
      x    x                          x    x
       xxxx                            xxxx

                   +*
                - +  *     xx       xx
                   +*    - + x   - x *
                            ++     **

                  +xx
                +  *

For four sets, you'll follow the same pattern: add the single 
"layers," subtract the double "layers," add the triple "layers," and 
subtract the quadruple "layer."

For the final application, you'll have to consider the sets of numbers 
between 2000 and 3000 that are multiples of either 3, 5, 7, or 11 as 
A, B, C, and D respectively. To count the size of A, divide 2000 and 
3000 by 3; this tells you that there are 1000 numbers divisible by 3 
between 1 and 3000 inclusive, and 666 between 1 and 2000, so there are 
334 between 2000 and 3000. Do the same for the other sets. Then, for 
example, the set of numbers divisible by both 3 and 5 (AnB) is the set 
of numbers divisible by 15, so you can use the same method to count 
each of the intersections. Then put these results into your formula to 
find the size of the union.

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