CHAPTER 1

SETS

Sets, useful in analyzing how we think, also help form the foundation of much of mathematics.

1A  Set Terminology

	Thinking Being

Humans, as thinking beings, like to categorize things; it is a way of making sense of the world. For instance, some things are called rocks, others are called trees, and still others are dogs, cats, or chairs. We have also brown dogs, Persian cats, and ripe yellow bananas. Humans, enjoying a language capability, have an advantage over other thinking creatures, in that we can give names to the categories, enabling ourselves to talk to each other about the things of the world.

Usually we do not speak about all things at once. When we mention in the same conversation apples, oranges, and cherries, we are perhaps talking about fruit, and if we mention Fords, Chevys and Toyotas, probably we are discussing cars. So in general there is a large category containing all things under discussion, and this large category is divided into smaller categories, and these smaller categories might be further divided into others, and at the same time some categories may overlap each other, so that it can get pretty complicated. In the case of cars, there are red cars, white cars, small green cars, mid-size blue Toyotas with anti-lock brakes, and so on. It is indeed fortunate that we are blessed with minds agile enough to handle all these mixtures of categories at once.

The mathematical study of sets is more or less a study of how we categorize things. A category of things is called a set, while the things in the set are called elements, or members, of the set. The large category containing all things under discussion is the universal set, or universe; it is usually referred to with the symbol U. For example, in a discussion of cars U probably would represent the set of all cars, with each individual car an element of the universal set U; then we might further designate F as the set of all Ford cars, C the set of all Chevys, and R the set of all red cars. The rule for a set is that each member of the universe must either be in the set or not be in the set - there can be no ambiguity about it. For example, probably you would not consider the set of all friendly cars, as such a description is vague and ordinarily you cannot say whether a car is friendly or not. (Sometimes in our examples and exercises we might interpret this rule a little loosely, so that sets more entertaining to talk about are allowed.)

It is useful to allow for the possibility of a set with no members; this set is called the empty set, and is denoted by the symbol Æ.

The discerning reader might argue at this point that we have not really defined very well the terms set and element - and this objection would be quite justified. We have said that a set is a category of things, which we call elements. If we were pressed further to define category and thing, we would be back at square one - having to come up with alternative names for these two essential concepts. In fact there is no satisfactory way to define set and element. These words, as well as the phrases belongs to and contains, are examples in mathematics of primitive terms; we just assume that everyone has an idea of what they mean, and we attach certain rules to their use. In the study of sets, the rules are that we have sets and we have elements, and that given any particular set and any particular element, either the element belongs to the set or it does not. If an element belongs to the set, then the set contains that element. The universal set contains all the elements, the empty set has none of them, and all other sets contain some elements and not the others.

We say that two sets A and B are the same set, or equal to one another, whenever they have exactly the same elements, and in this event we write A = B. On the other hand, if A contains an element not belonging to B, or if B has an element not belonging to A, we say that A and B are not equal, and write A ≠ B. Given any set A, there is another set naturally associated with A, designated as ~A and called the complement of A; it is that set whose members are precisely those elements in the universal set but not in A. If an element belongs to A, then it does not belong to ~A, and if it does not belong to A, then it does belong to ~A.

example 1

	Hawaii Math Class

Let the universal set U consist of all students in this math class. We consider various other sets of elements from this universal set. We designate sets

Observe that F = ~M, as F consists of exactly those students from the class not in the set M. Likewise, M = ~F. We see that J ≠ M, except in the unlikely event that all male students in the class are juniors, and all juniors are males. Some of these sets overlap; for instance, some students might belong to all three of the sets F, J, and H. Also, A = Æ because no one was ever born in Antarctica, while B = U since doubtless every student in this class is bright.

The sets M and F of Example 1 illustrate the general set formula

That is, the “complement of the complement” of a set is the set itself. The truth of this statement is evident after a little thought. You start with S and take all the elements not in S to get ~S; then if you repeat the process, beginning with ~S, you return back to the original set S. Two other self-evident formulas are

Thus far we have defined sets by describing their members. If the members of a set have names, or perhaps symbols representing them, then we can define the set by the roster method, whereby we just list all the elements of the set inside a pair of brackets. For example, we could write

to denote the set of vowels in the English alphabet. To represent the set of all letters in the alphabet we might write

The three dots, or ellipsis, signify that the pattern is so obvious that anyone should be able to fill in the missing elements. We might also consider sets of people, such as

or sets of numbers like

If a set has an infinite number of elements then obviously we cannot list individually all its elements, but with the use of ellipsis we might still be able to use the roster method to describe the set. The set of all positive integers is such a set; it can be indicated as

The order in which the elements of a set are listed is not important - that is, listing the elements in a different order does not change the set. Thus the three listings

refer to the same set. Also, it does not matter if an element is listed more than once. Another acceptable - but doubtless more confusing - way of writing the above set is

One can describe sets also with so-called set-builder notation. We use this notation to describe the set S of students in Math 100 class by writing

The colon inside the brackets is read “such that”, and the entire line is read “S equals the set of all x such that x is a student in Math 100”. The letter x is just a placeholder, and could be replaced by any other symbol. The set-builder method is merely a formal way of verbally describing the members of the set; it has obvious advantages over the roster method when the set has many members, or when the members of the set do not have names. For instance, you would not want to try to describe the set

with the roster method!

The symbol “Δ means belongs to, or is a member of, while “Ï” has the opposite meaning does not belong to or is not a member of. For example, if

then we can write 3 Î A and 7 Ï A.

The concept of a subset is fundamental in the study of sets, and indeed to much of mathematics. Given two sets A and B, we say that A is a subset of B whenever every element of A is also an element of B. We write A Ì B to signify that A is a subset of B, and A Ë B to signify otherwise. The empty set is considered a subset of every set, while every set is a subset of itself as well as of the universal set.

example 2

The set B = {a , b , c} has eight subsets; they are

Be careful not to confuse the symbols “Ì” and “Δ. In this situation we can write {a} Ì B and a Î B, but we cannot write {a} Î B or a Ì B. The notation {a} refers to the set containing a, but not to the element a itself - it is like the difference between a sack containing an apple and only the apple.

Two sets A and B intersect, or meet, if they have at least one element in common, in which case we say that A meets B, and likewise that B meets A. If A and B do not meet - that is, if they have no common elements - we say that they are disjoint from one another, or that they form a disjoint pair. Certainly the empty set is disjoint from every other set, while the universal set meets every set except the empty set.

example 3

Let the universal set be

and consider also the sets

Note that sets A and B, having no elements in common, are disjoint from one another. Other disjoint pairs of sets are A and E, B and D, D and E. All other pairs of sets intersect; for example, A and C intersect because they have in common the element 3, while B and F intersect because they have in common the two elements 4 and 6. Observe also that D Ì A, E Ì B, E Ì C, E Ì F, while every set is a subset of itself and of the universal set U.

If sets A and B are disjoint, then each element of A is not a member of B - that is, each element of A is a member of the complement of B, or A Ì ~B. Equivalently, we can say that each element of B is not an element of A, or B Ì ~A. In the above Example 3, the sets A and B are disjoint, while

Observe that A Ì ~B and B Ì ~A.

example 4

Let the universal set consist of all the world's animals, and consider the sets

The sets M and F are disjoint from one another, as are the pairs F and L, W and H, and F and H (unless you believe in mermaids). Also, F Ì W, F Ì S, H Ì M, and H Ì L. The sets M and W intersect (consider the whales), although neither is a subset of the other. The same can be said for the pairs M and S, M and L, S and W, S and H, and S and L. If we agree that amphibians such as frogs belong to both sets W and L, then likewise these two sets meet.

Many everyday statements can be formulated as statements about sets. Consider again the sets described in Example 4. The table below shows a few statements on the left expressed in ordinary language, and on the right appear equivalent formulations of these statements in terms of sets.

(For simplicity we assume that “some” means “at least one” - thus, “some humans” means “at least one human” or “one or more humans”.)

EXERCISES 1A

1. Which descriptions do you think are precise enough to define a set?
   1. all even integers larger than 3 and less than 17
   2. all lucky numbers between 1 and 100
   3. all sincere students in this math class
   4. all left-handed students in this math class
   5. all pretty good novelists
   6. all living Nobel prize winning novelists
   
   

2. First U.S. President of the Second Half of the Twentieth Century

   Let P denote the set of initials of U.S. Presidents in the second half of the twentieth century. Describe this set
   1. by the roster method,
   2. with set-builder notation.
   
   
3. Let PC denote the set containing the three primary colors. Describe this set
   1. by the roster method,
   2. with set-builder notation.
   
   
4. Describe the set by the roster method:
   1. {x : x is a positive odd single-digit integer}
   2. {y : y is a positive integer evenly divisible by 3}
   3. {h : h is one of the six largest Hawaiian islands}
   4. {$ : $ is a letter of the alphabet representing a note on the musical scale}
   5. {# : # is a letter of the English alphabet whose pronunciation requires exhaling through the nose}
   
   
5. Describe the set using set-builder notation:
   1. {2 , 4 , 6 , 8}
   2. {1 , 3 , 5 , 7 , 9 , 11 , …}
   3. {b , c , d , f , g , h , j , k , l , m , n , p , q , r , s , t , v , w , x , y , z}
   4. {Alaska , Hawaii}
   5. {Bess , Mamie , Jackie , Lady Byrd , Pat , Betty , Rosalynn , Nancy , Barbara , Hilary , Laura}
   
   
6. List all subsets of the set S = {a , b , c , d}. How many subsets do you guess a set with five elements would have?
   
   
7. Given that B = {0 , 1}, answer true or false to the following:

   a.  Æ Î B		b.  Æ Ì B		c.  {0} Î B		d.  0 Î B		e.  B Î B
   f.  B Ì B
   g.  0 Ì B		h.  {0} Ì B		i.  0 Î Æ		j.  Æ Î 0
   k.  Æ Ì 0		l.  Æ Î {0}		m.  Æ Ì Æ		n.  Æ Î Æ		o.  1 Î B

   
   
8. Let the universal set be

   U = {u , v , w , x , y , z} ,

   and consider also the sets

   A = {u , v , y , z}		B = {v , w , y , z}		C = {w , x , y}
   D = {u , z}		E = {v , w , y}		F = {u , v} .

   Neglecting the universal set U,
   1. list all pairs of sets disjoint from each other,
   2. find all pairs of sets with one a subset of the other,
   3. list the sets that intersect D.
   Also,
   4. describe the sets ~A, ~B, and ~C,
   5. list the sets (among A, B, C, D, E, F) that are subsets of ~D.
   
   
9. Let the universal set consist of all cats, and consider the sets

   B : black cats		P : Persian cats		S : Siamese cats
   W : white cats		F : finicky cats		L : long-tailed cats .

   Formulate the following sentences as symbolic statements about sets (using the symbols Ì and Ë):

   All Persian cats are finicky. Finicky cats all have long tails. No finicky cat has a long tail. Not all Siamese cats are white. Some Persian cats are black. A black cat cannot be Siamese. Any cat not finicky is most certainly white. Cats not black are not necessarily Siamese. Some long-tailed cats are not black. You can't assume a cat is not Persian, just because it does not have a long tail.

   
   
10. Let the universal set consist of days in Montana, and consider the sets

    C : cold days		J : June days		N : nice days
    W : warm days		D : December days		R : rainy days .

    Translate the following symbolic statements about sets into ordinary sentences:

    a.  D Ì C		b.  D Ë C		c.  R Ì ~N		d.  J Ë ~R		e.  J Ë W
    f.  N Ì ~D		g.  ~N Ì C		h.  ~N Ë ~W		i.  W Ë ~D		j.  ~R Ë J
    June Day in Montana