1B  Set Operations


robot  

Walking
Robot?

 

In our thinking we are always combining sets in one way or another. When we say today is nice and warm, we mean that today is a member of the set of nice days as well as the set of warm days. If the weatherman says today it will rain or snow, he means today will belong to either the rainy day set or the snowy day set. Of course nobody is conscious of these set interpretations - it is all automatic, just as when we walk we don’t have to think about all the muscle movements necessary to accomplish the task. Indeed, we walk adequately without analyzing in detail the method, and in like manner we reason pretty well without the foggiest notion of how we do it. But both these procedures are remarkably complicated; engineers find it extremely difficult to teach a robot to walk, and it is debatable whether anyone will ever understand exactly how we think.

A good way to analyze a complex procedure is to break it down into a succession of simpler ones. Much of what we do in our thinking with sets can be broken down into combinations of three basic set operations. A set operation is something we do to one or more sets to produce another set. One of these basic operations is that of taking the complement. Given a set A, we get a second set ~A by collecting all elements of the universal set not in A. This operation acts on only a single set. The other two basic set operations act on two or more sets to produce a third set.

First we look at the intersection operation. The intersection of sets A and B is that set whose elements are the ones that A and B have in common. We refer to this set with the notation A ∩ B. The precise set-builder formulation is

A ∩ B = {x : x Î A and x Î B} .

One reads A ∩ B as “A intersect B”, or “the intersection of A and B”. Thus if A is the set of nice days and B the set of warm days, then A ∩ B is the set of days that are both nice and warm. Notice that the definition is symmetric in A and B - that is, the elements that A and B have in common are the same elements that B and A have in common. The formula expressing this symmetry is

A ∩ B = B ∩ A .

The third basic set operation is the union operation. The union of A and B is that set we get by combining the elements of A and the elements of B into a single set; it is referred to as A È B, and read as “A union B”, or “the union of A and B”. The precise formulation is

A È B = {x : x Î A or x Î B} .

Thus an element qualifies for A È B if it is a member of A or a member of B (or perhaps of both A and B). For example, if A is the set of days it rains, and B the set of days it snows, then A È B is the set of days it rains, snows, or, heaven forbid, both rains and snows. The union operation likewise is symmetric, as expressed in the formula

A È B = B È A .

Obviously, combining the elements of A and B into one set is the same as combining the elements of B and A into one set.


example 1

  dice

One Die + One Die
= Two Dice

We look at an example involving sets of numbers. Let the universal set U contain all the numbers on a die - or more precisely,

U = {1 , 2 , 3 , 4 , 5 , 6} .

We further define sets

A = {1 , 2 , 4 , 6}     ,      B = {2 , 3 , 6}     ,      C = {1 , 4 , 5} .

You should be able to check that

~A = {3 , 5}

,

~B = {1 , 4 , 5} = C

,

~C = {2 , 3 , 6} = B ,

A ∩ B = {2 , 6}

,

A ∩ C = {1 , 4}

,

B ∩ C = Æ ,

A È B = {1 , 2 , 3 , 4 , 6}

,

A È C = {1 , 2 , 4 , 5 , 6}

,

B È C = U .

We can also combine two or more operations into one expression, such as

B È (A ∩ C) = {2 , 3 , 6} È {1 , 4} = {1 , 2 , 3 , 4 , 6} ,

~(A È B) = ~{1 , 2 , 3 , 4 , 6} = {5} ,

~A È C = {3 , 5} È {1 , 4 , 5} = {1 , 3 , 4 , 5} ,

(~A È C) ∩ B = {1 , 3 , 4 , 5} ∩ {2 , 3 , 6} = {3} .




As in Example 1, we sometimes use parentheses to ensure that operations are performed in the desired order. Parentheses are unnecessary when the order makes no difference. For instance, we don't need parentheses in the two expressions

A ∩ B ∩ C           ,            A È B È C .

In the first, whether we compute (A ∩ B) ∩ C or A ∩ (B ∩ C) we get the same result - those elements common to all three sets. In the second, A È B È C is the result of combining all elements of A, B, and C into a single set; the order in which we do the unions is irrelevant.

The sets B and C in Example 1 serve to illustrate the general set identities

S ∩ ~S = Æ           ,            S È ~S = U .

These two formulas state the obvious - the first says that S and ~S have no elements in common, while the second asserts that combining the elements of S with those elements not in S gives everything in the universal set. You should be able to convince yourself also of the validity of the elementary identities

S ∩ S = S

,

S ∩ U = S

,

S ∩ Æ = Æ ,

S È S = S

,

S È U = U

,

S È Æ = S .

Note that the equation A ∩ B = Æ means simply that A and B are disjoint; in fact, the following three statements are equivalent:

A ∩ B = Æ        ,         A Ì ~B        ,         B Ì ~A .

The first statement says that sets A and B have nothing in common, the second says that everything in A is not in B, and the third that everything in B is not in A. But these three statements mean the same thing!

The next (somewhat silly) example illustrates how everyday descriptions of objects can be translated into symbolic expressions involving complements, intersections, and unions of sets.


example 2

Let the universal set consist of all adults, and consider further the sets

M : men

 

T : tall people

 

H : honest people

L : left-handers

 

P : pessimists

 

N : noisy people .

For the sake of this example, we will assume that everyone is either a man or a woman, tall or short, honest or dishonest, left- or right-handed, an optimist or a pessimist, and noisy or quiet. Consequently, ~T is the set of short people, ~H the set of dishonest people, etc. Below are listed a few combinations of sets and their descriptions in words:


male pessimist

 

M ∩ T : tall men

L ∩ ~M : left-handed women

~H ∩ P : dishonest pessimists

~T ∩ ~L : short right-handers

M ∩ H ∩ ~P : honest optimistic men

M È N : people who are male or noisy

An Element
of M ∩ P

~M È ~N : people who are female or quiet

~M ∩ (H È P) : women who are honest or pessimistic

~P È (P ∩ ~N) : people who are optimistic, or pessimistic and quiet

(~L ∩ M) È (L ∩ ~M) : people who are right-handed and male, or left-handed and female.




To form complete symbolic statements about sets of objects, we can incorporate the symbols “Ì” and “Ë”, as well as the equals sign “=”, between set descriptions.


example 3

We consider the same sets of Example 2. On the left are some symbolic sentences, and on the right their translation into plain English.

 

(H ∩ M) Ì P : Honest men are pessimists.

  female optimist

H ∩ M = Æ : There are no honest men.

~P Ì (T È L) : Optimists are tall or left-handed.

T ∩ ~H ∩ ~M = Æ : There are no tall dishonest women.

L Ë N : Not all left-handers are noisy.

(N ∩ M) Ì (P È ~H) : Noisy men are either pessimistic or dishonest.

(P ∩ ~T) Ë ~H : Not all pessimistic short people are dishonest.

(H È ~N) ∩ ~P = Æ : No one who is honest or quiet is an optimist.

U = P È ~H : Everyone is either a pessimist or dishonest.

(~N È ~T) Ë (~M ∩ ~L) : Not everyone who is quiet or short is a right-handed woman.

(~P ∩ ~M) Ì ~N





EXERCISES 1B


  1. The universe is U = {a , b , c , d , e , f , g}, and sets P, Q, R are

    P = {a , c , f , g}      ,      Q = {b , c, g}      ,      R = {a , b , c , d} .


    List in brackets the elements of the following sets.

    a.  ~P

     

    b.  P ∩ Q

     

    c.  Q È R

     

    d.  ~Q ∩ R

    e.  ~(P È R)

    f.  Q È ~P

    g.  P ∩ Q ∩ R

    h.  P È Q È R

    i.  R ∩ (P È Q)

    j.  (Q ∩ R) È P

    k.  (P ∩ R) È ~Q

    l.  (R È ~P) ∩ (~Q È P)


  2. Suppose that A Ì B. What then are A ∩ B and A È B? What is A ∩ ~B?

  3.  

    cow

     

    Element of B ∩ H ∩ C

    A farmer in Waianae raises cows. Some of his cows are females, and the rest are males. Some are Jerseys, and the rest are Guernseys. Some are brown, and the rest are white. Some are lazy, and the rest are energetic. Some cows are contented, and the rest discontented. Some have horns, and the rest have no horns. Let the universe consist of all the farmer's cows, and consider the sets

    F : females

     

    J : Jerseys

    B : brown cows

    L : lazy cows

    C : contented cows

    H : horned cows .


    Describe in words the following sets:

    a.  B ∩ F

     

    b.  J È C

     

    c.  ~F ∩ C

     

    d.  ~L È ~B È H

    e.  J ∩ B ∩ ~C

    f.  H ∩ (L È ~C)

    g.  ~H ∩ ~J

    h.  F È (C ∩ ~J)


    Also, write the following with symbolic set notation:

    i.  brown Jersey cows

     

    j.  cows that are brown or female

    k.  contented Guernsey cows

    l.  male cows that are Jersey or white

    m.  discontented hornless cows

    n.  cows that are lazy, or brown with horns

    o.  lazy and discontent male cows

    p.  cows that are white, or Jersey, or horned


    Translate the symbolic statements into ordinary sentences:

    q.  (F ∩ J) Ì C

     

    r.  (J ∩ H) Ë C

     

    s.  (B ∩ L) Ì (C ∩ ~J)

    t.  ~J Ì (B ∩ ~L)

    u.  (L ∩ ~C) Ë (~F ∩ H)

    v.  (~L È C) Ì ~H

    w.  F ∩ ~C = Æ

    x.  H ∩ (L È ~C) = Æ

    y.  U = C ∩ ~L


    Write the sentences symbolically using set notation:

    z.  The lazy cows are contented Jerseys.

    @.  The male horned Guernseys are energetic.

    #.  All the female brown cows are contented hornless Jerseys.

    $.  Not every lazy brown cow is a female Jersey.

    %.  The female horned cows are white and lazy.

    &.  There are no contented brown male cows.

    *.  No brown cow with horns is lazy and discontented.

    !.  Every cow is an energetic female or a lazy male.

    +.  You cannot assume a cow is a hornless male Guernsey, just because it is lazy or discontent.



  4.  

    tomatoes

     

    Elements of R ∩ J ∩ T

    Let all the tomatoes in Hawaii comprise the universal set, and assume a tomato is either red or green, hard or soft, juicy or dry, tasty or bland, plump or not plump, and local or imported. Consider the sets

    R : red tomatoes

     

    H : hard tomatoes

    J : juicy tomatoes

    T : tasty tomatoes

    P : plump tomatoes

    L : local tomatoes .


    Describe in words the following sets:

    a.  T ∩ R

     

    b.  R È T È J

     

    c.  ~R ∩ ~L

     

    d.  H È (~R ∩ ~T)

    e.  J È T

    f.  ~(P È J)

    g.  P ∩ L ∩ ~H

    h.  ~L ∩ (~P È H)


    Also, write the following with symbolic set notation:

    i.  local juicy tomatoes

     

    j.  bland or dry tomatoes

    k.  soft juicy plump tomatoes

    l.  hard tomatoes that are green or dry

    m.  tomatoes plump or juicy, and imported

    n.  tomatoes that are bland, or hard and green


    Translate the symbolic statements into ordinary sentences:

    o.  (L ∩ R) Ì J

     

    p.  H Ì (~T ∩ ~J)

     

    q.  H ∩ ~L ∩ J = Æ

    r.  (J ∩ P) Ë T

    s.  (H È ~T) Ì ~J

    t.  (R ∩ P) Ì (J ∩ T)


    Write the sentences symbolically using set notation:

    u.  Some red tomatoes are imported.

    v.  There are no tasty imported tomatoes.

    w.  Tomatoes that are green and juicy are bland.

    x.  Plump, juicy, local tomatoes are red and tasty.

    y.  Imported plump tomatoes are dry and bland.

    z.  Not all plump or juicy tomatoes are soft and tasty.