. 1
( : 20)



. . >>

Finite Mathematics

Kemeny, Snell, and Thompson

Version 4.0A0, 5 October 1998
Copyright (C) 1998 Peter G. Doyle
Derived from works
Copyright (C) 1957, 1966, 1974 John G. Kemeny, J.
Laurie Snell, Gerald L. Thompson
This work is freely redistributable under the terms of
the GNU General Public License
as published by the Free Software Foundation.
This work comes with ABSOLUTELY NO WARRANTY.
2
Chapter 2

Sets and subsets

2.1 Introduction
A well-de¬ned collection of objects is known as a set. This concept, in
its complete generality, is of great importance in mathematics since all
of mathematics can be developed by starting from it.
The various pieces of furniture in a given room form a set. So do
the books in a given library, or the integers between 1 and 1,000,000, or
all the ideas that mankind has had, or the human beings alive between
one billion B.C. and ten billion A.D. These examples are all examples
of ¬nite sets, that is, sets having a ¬nite number of elements. All the
sets discussed in this book will be ¬nite sets.
There are two essentially di¬erent ways of specifying a set. One
can give a rule by which it can be determined whether or not a given
object is a member of the set, or one can give a complete list of the
elements in the set. We shall say that the former is a description of
the set and the latter is a listing of the set. For example, we can de¬ne
a set of four people as (a) the members of the string quartet which
played in town last night, or (b) four particular persons whose names
are Jones, Smith, Brown, and Green. It is customary to use braces
to, surround the listing of a set; thus the set above should be listed
{Jones, Smith, Brown, Green}.
We shall frequently be interested in sets of logical possibilities, since
the analysis of such sets is very often a major task in the solving of a
problem. Suppose, for example, that we were interested in the successes
of three candidates who enter the presidential primaries (we assume
there are no other entries). Suppose that the key primaries will be held
in New Hampshire, Minnesota, Wisconsin, and California. Assume

3
4 CHAPTER 2. SETS AND SUBSETS

that candidate A enters all the primaries, that B does not contest in
New Hampshire™s primary, and C does not contest in Wisconsin™s. A
list of the logical possibilities is given in Figure 2.1. Since the New
Hampshire and Wisconsin primaries can each end in two ways, and the
Minnesota and California primaries can each end in three ways, there
are in all 2 · 2 · 3 · 3 = 36 di¬erent logical possibilities as listed in Figure
2.1.
A set that consists of some members of another set is called a subset
of that set. For example, the set of those logical possibilities in Figure
2.1 for which the statement “Candidate A wins at least three primaries”
is true, is a subset of the set of all logical possibilities. This subset can
also be de¬ned by listing its members: {P1, P2, P3, P4, P7, P13, P19}.
In order to discuss all the subsets of a given set, let us introduce the
following terminology. We shall call the original set the universal set,
one-element subsets will be called unit sets, and the set which contains
no members the empty set. We do not introduce special names for other
kinds of subsets of the universal set. As an example, let the universal
set U consist of the three elements {a, b, c}. The proper subsets of U are
those sets containing some but not all of the elements of U . The proper
subsets consist of three two-element sets namely, {a, b}, {a, c}, and
{b, c} and three unit sets, namely, {a}, {b}, and {c}. To complete the
picture, we also consider the universal set a subset (but not a proper
subset) of itself, and we consider the empty set …, that contains no
elements of U , as a subset of U . At ¬rst it may seem strange that we
should include the sets U and … as subsets of U , but the reasons for
their inclusion will become clear later.
We saw that the three-element set above had 8 = 23 subsets. In
general, a set with n elements has 2n subsets, as can be seen in the
following manner. We form subsets P of U by considering each of the
elements of U in turn and deciding whether or not to include it in the
subset P . If we decide to put every element of U into P , we get the
universal set, and if we decide to put no element of U into P , we get
the empty set. In most cases we will put some but not all the elements
into P and thus obtain a proper subset of U . We have to make n
decisions, one for each element of the set, and for each decision we have
to choose between two alternatives. We can make these decisions in
2 · 2 · . . . · 2 = 2n ways, and hence this is the number of di¬erent subsets
of U that can be formed. Observe that our formula would not have
been so simple if we had not included the universal set and the empty
set as subsets of U .
5
2.1. INTRODUCTION




Figure 2.1: ™¦
6 CHAPTER 2. SETS AND SUBSETS

In the example of the voting primaries above there are 236 or about
70 billion subsets. Of course, we cannot deal with this many subsets in
a practical problem, but fortunately we are usually interested in only
a few of the subsets. The most interesting subsets are those which
can be de¬ned by means of a simple rule such as “the set of all logical
possibilities in which C loses at least two primaries”. It would be di¬-
cult to give a simple description for the subset containing the elements
{P1, P4, P14, P30, P34}. On the other hand, we shall see in the next
section how to de¬ne new subsets in terms of subsets already de¬ned.

Example 2.1 We illustrate the two di¬erent ways of specifying sets in
terms of the primary voting example. Let the universal set U be the
logical possibilities given in Figure 2.1.

1. What is the subset of U in which candidate B wins more primaries
than either of the other candidates?

[Ans. {P11, P12, P17, P23, P26, P28, P29}.]

2. What is the subset in which the primaries are split two and two?

[Ans. {P5, P8, P10, P15, P21, P30, P31, P35}.]

3. Describe the set {P1, P4, P19, P22}.

[Ans. The set of possibilities for which A wins in Minnesota and
California.]

4. How can we describe the set {P18, P24, P27}

[Ans. The set of possibilities for which C wins in California, and
the other primaries are split three ways.]

™¦

Exercises
1. In the primary example, give a listing for each of the following
sets.

(a) The set in which C wins at least two primaries.
7
2.1. INTRODUCTION

(b) The set in which the ¬rst three primaries are won by the
same candidate.
(c) The set in which B wins all four primaries.

2. The primaries are considered decisive if a candidate can win three
primaries, or if he or she wins two primaries including California.
List the set in which the primaries are decisive.

3. Give simple descriptions for the following sets (referring to the
primary example).

(a) {P33, P36}.
(b) {P10, P11, P12, P28, P29, P30}.
(c) {P6, P20, P22}.

4. Joe, Jim, Pete, Mary, and Peg are to be photographed. They
want to line up so that boys and girls alternate. List the set of
all possibilities.

5. In Exercise 4, list the following subsets.

(a) The set in which Pete and Mary are next to each other.
(b) The set in which Peg is between Joe and Jim.
(c) The set in which Jim is in the middle.
(d) The set in which Mary is in the middle.
(e) The set in which a boy is at each end.

6. Pick out all pairs in Exercise 5 in which one set is a subset of the
other.

7. A TV producer is planning a half-hour show. He or she wants to
have a combination of comedy, music, and commercials. If each
is allotted a multiple of ¬ve minutes, construct the set of possible
distributions of time. (Consider only the total time allotted to
each.)

8. In Exercise 7, list the following subsets.

(a) The set in which more time is devoted to comedy than to
music.
8 CHAPTER 2. SETS AND SUBSETS

(b) The set in which no more time is devoted to commercials
than to either music or comedy.
(c) The set in which exactly ¬ve minutes is devoted to music.
(d) The set in which all three of the above conditions are satis-
¬ed.

9. In Exercise 8, ¬nd two sets, each of which is a proper subset of
the set in 8a and also of the set in 8c.

10. Let U be the set of paths in Figure ??. Find the subset in which

(a) Two balls of the same color are drawn.
(b) Two di¬erent color balls are drawn.

11. A set has 101 elements. How many subsets does it have? How
many of the subsets have an odd number of elements?

[Ans. 2101 ; 2100 .]

12. Do Exercise 11 for the case of a set with 102 elements.


2.2 Operations on subsets
In Chapter ?? we considered the ways in which one could form new
statements from given statements. Now we shall consider an analogous
procedure, the formation of new sets from given sets. We shall assume
that each of the sets that we use in the combination is a subset of some
universal set, and we shall also want the newly formed set to be a subset
of the same universal set. As usual, we can specify a newly formed set
either by a description or by a listing.
If P and Q are two sets, we shall de¬ne a new set P © Q, called the
intersection of P and Q, as follows: P © Q is the set which contains
those and only those elements which belong to both P and Q. As an
example, consider the logical possibilities listed in Figure 2.1. Let P be
the subset in which candidate A wins at least three primaries, i.e., the
set {P1, P2, P3, P4, P7, P13, P19}; let Q be the subset in which A wins
the ¬rst two primaries, i.e., the set {P1, P2, P3, P4, P5, P6}. Then the
intersection P © Q is the set in which both events take place, i.e., where
A wins the ¬rst two primaries and wins at least three primaries. Thus
P © Q is the set {P1, P2, P3, P4}.
9
2.2. OPERATIONS ON SUBSETS




Figure 2.2: ™¦


If P and Q are two sets, we shall de¬ne a new set P ∪ Q called
the union of P and Q as follows: P ∪ Q is the set that contains those
and only those elements that belong either to P or to Q (or to both).
In the example in the paragraph above, the union P ∪ Q is the set of
possibilities for which either A wins the ¬rst two primaries or wins at
least three primaries, i.e., the set {P1, P2, P3, P4, P5, P6, P7, P13, P19}.
To help in visualizing these operations we shall draw diagrams,
called Venn diagrams, which illustrate them. We let the universal set
be a rectangle and let subsets be circles drawn inside the rectangle.
In Figure 2.2 we show two sets P and Q as shaded circles. Then the
doubly crosshatched area is the intersection P © Q and the total shaded
area is the union P ∪ Q.
If P is a given subset of the universal set U , we can de¬ne a new set
˜
P called the complement of P as follows: P is the set of all elements
of U that are not contained in P . For example, if, as above, Q is the
˜
set in which candidate A wins the ¬rst two primaries, then Q is the set
{P7, P8, . . . , P36}. The shaded area in Figure 2.3 is the complement
of the set P . Observe that the complement of the empty set … is the
universal set U , and also that the complement of the universal set is
the empty set.
Sometimes we shall be interested in only part of the complement of a
set. For example, we might wish to consider the part of the complement
˜
of the set Q that is contained in P , i.e., the set P © Q. The shaded
˜
area in Figure 2.4 is P © Q.
A somewhat more suggestive de¬nition of this set can be given as
10 CHAPTER 2. SETS AND SUBSETS




Figure 2.3: ™¦




Figure 2.4: ™¦
11
2.2. OPERATIONS ON SUBSETS

follows: Let P ’ Q be the di¬erence of P and Q, that is, the set that
contains those elements of P that do not belong to Q. Figure 2.4 shows
˜
that P © Q and P ’ Q are the same set. In the primary voting example
above, the set P ’ Q can be listed as {P7, P13, P19}.
The complement of a subset is a special case of a di¬erence set,
˜
since we can write Q = U ’ Q. If P and Q are nonempty subsets whose
intersection is the empty set, i.e., P © Q = …, then we say that they are
disjoint subsets.

Example 2.2 In the primary voting example let R be the set in which
A wins the ¬rst three primaries, i e., the set {P1, P2, P3}; let S be the
set in which A wins the last two primaries, i.e., the set {P1, P7, P13, P19, P25, P31}.
Then R © S = {P1} is the set in which A wins the ¬rst three primaries
and also the last two, that is, he or she wins all the primaries. We also
have
R ∪ S = {P1, P2, P3, P7, P13, P19, P25, P31},
which can be described as the set in which A wins the ¬rst three pri-
maries or the last two. The set in which A does not win the ¬rst three
˜
primaries is R = {P4, P5, . . . , P36}. Finally, we see that the di¬erence
set R ’ S is the set in which A wins the ¬rst three primaries but not
both of the last two. This set can be found by taking from R the el-
ement P1 which it has in common with S, so that R ’ S = {P2, P3}.
™¦

Exercises
˜˜ ˜˜
1. Draw Venn diagrams for P © Q, P © Q, P © Q, P © Q.
˜
2. Give a step-by-step construction of the diagram for (P ’ Q) ∪
˜
(P © Q).

3. Venn diagrams are also useful when three subsets are given. Con-
struct such a diagram, given the subsets P . Q. and R. Identify
each of the eight resulting areas in terms of P , Q, and R.

4. In testing blood, three types of antigens are looked for: A, B, and
Rh. Every person is classi¬ed doubly. He or she is Rh positive if
he or she has the Rh antigen, and Rh negative otherwise. He or
she is type AB, A, or B depending on which of the other antigens
he or she has, with type O having neither A nor B. Draw a Venn
diagram, and identify each of the eight areas.
12 CHAPTER 2. SETS AND SUBSETS




Figure 2.5: ™¦

5. Considering only two subsets, the set X of people having antigen
A, and the set Y of people having antigen B. de¬ne (symbolically)
the types AB, A, B and O.

6. A person can receive blood from another person if he or she has
all the antigens of the donor. Describe in terms of X and Y the
sets of people who can give to each of the four types. Identify
these sets in terms of blood types.

7. The tabulation in Figure 2.5 records the reaction of a number
of spectators to a television show. A11 the categories can be
de¬ned in terms of the following four: M (male), G (grown-up),
L (liked), V (very much). How many people fall into each of the
following categories?

(a) M .
[Ans. 34.]
(b) L.
(c) V .
˜˜
(d) M © G © L © V .
[Ans. 2.]
˜
(e) M © G © L.
(f) (M © G) ∪ (L © V ).
13
2.2. OPERATIONS ON SUBSETS

(g) M © G.
[Ans. 48.]
˜ ˜
(h) M ∪ G.
(i) M ’ G.
˜ ˜
(j) [M ’ (G © L © V )].

8. In a survey of 100 students, the numbers studying various lan-
guages were found to be: Spanish, 28; German, 30; French, 42;
Spanish and German, 8; Spanish and French, 10; German and
French, 5; all three languages, 3.

(a) How many students were studying no language?
[Ans. 20.]
(b) How many students had French as their only language?
[Ans. 30.]
(c) How many students studied German if and only if they stud-
ied French?
[Ans. 38.]

[Hint: Draw a Venn diagram with three circles, for French, Ger-
man, and Spanish students. Fill in the numbers in each of the
eight areas, using the data given above. Start from the end of the
list and work back.]

9. In a later survey of the 100 students (see Exercise 8) the numbers
studying the various languages were found to be: German only,
18; German but not Spanish, 23; German and French, 8; German,
26; French, 48; French and Spanish, 8; no language, 24.

(a) How many students took Spanish?
[Ans. 18.]
(b) How many took German and Spanish but not French?
[Ans. None.]
(c) How many took French if and only if they did not take Span-
ish?
14 CHAPTER 2. SETS AND SUBSETS

[Ans. 50.]

10. The report of one survey of the 100 students (see Exercise 8)
stated that the numbers studying the various languages were: all
three languages, 5; German and Spanish, 10; French and Spanish,
8; German and French, 20; Spanish, 30; German, 23; French, 50.
The surveyor who turned in this report was ¬red. Why?


2.3 The relationship between sets and com-
pound statements
The reader may have observed several times in the preceding sections
that there was a close connection between sets and statements, and
between set operations and compounding operations. In this section
we shall formalize these relationships.

. 1
( : 20)



. . >>