. 1
( 6)



>>

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.
If we have a number of statements relative to a set of logical pos-
sibilities, there is a natural way of assigning a set to each statement.
First of all, we take the set of logical possibilities as our universal set.
Then to each statement we assign the subset of logical possibilities
of the universal set for which that statement is true. This idea is so
important that we embody it in a formal de¬nition.
De¬nition. Let U be a set of logical possibilities, let p be a state-
ment relative to it, and let P be that subset of the possibilities for
which p is true; then we call P the truth set of p.
If p and q are statements, then p∨q and p§q are also statements and
hence must have truth sets. To ¬nd the truth set of p ∨ q, we observe
that it is true whenever p is true or q is true (or both). Therefore we
must assign to p ∨ q the logical possibilities which are in P or in Q (or
both); that is, we must assign to p ∨ q the set P ∪ Q. On the other
hand, the statement p § q is true only when both p and q are true, so
that we must assign to p § q the set P © Q.
Thus we see that there is a close connection between the logical op-
eration of disjunction and the set operation of union, and also between
conjunction and intersection. A careful examination of the de¬nitions
of union and intersection shows that the word “or” occurs in the de¬ni-
tion of union and the word “and” occurs in the de¬nition of intersection.
Thus the connection between the two theories is not surprising.
Since the connective “not” occurs in the de¬nition of the comple-
˜
ment of a set, it is not surprising that the truth set of ¬p is P . This
2.3. THE RELATIONSHIP BETWEEN SETS AND COMPOUND STATEMENTS15




Figure 2.6: ™¦

follows since ¬p is true when p is false, so that the truth set of ¬p
contains all logical possibilities for which p is false, that is, the truth
˜
set of ¬p is P .
The truth sets of two propositions p and q are shown in Figure
2.6. Also marked on the diagram are the various logical possibilities
for these two statements. The reader should pick out in this diagram
the truth sets of the statements p ∨ q, p § q, ¬p, and ¬q.
The connection between a statement and its truth set makes it pos-
sible to “translate” a problem about compound statements into a prob-
lem about sets. It is also possible to go in the reverse direction. Given
a problem about sets, think of the universal set as being a set of logical
possibilities and think of a subset as being the truth set of a statement.
Hence we can “translate” a problem about sets into a problem about
compound statements.
So far we have discussed only the truth sets assigned to compound
statements involving ∨, §, and ¬. All the other connectives can be
de¬ned in terms of these three basic ones, so that we can deduce what
truth sets should be assigned to them. For example, we know that
p ’ q is equivalent to ¬p ∨ q (see Figure ??). Hence the truth set of
˜
p ’ q is the same as the truth set of ¬p∨q, that is, it is P ∪Q. The Venn
diagram for p ’ q is shown in Figure 2.7, where the shaded area is the
truth set for the statement. Observe that the unshaded area in Figure
˜
2.7 is the set P ’ Q = P © Q, which is the truth set of the statement
˜
p § ¬q. Thus the shaded area is the set P ’ Q = P © Q, which is the
truth set of the statement ¬(p § ¬q). We have thus discovered the fact
that p ’ q, ¬p ∨ q, and ¬(p § ¬q) are equivalent. It is always the
case that two compound statements are equivalent if and only if they
16 CHAPTER 2. SETS AND SUBSETS




Figure 2.7: ™¦

have the same truth sets. Thus we can test for equivalence by checking
whether they have the same Venn diagram.
Suppose that p is a statement that is logically true. What is its
truth set? Now p is logically true if and only if it is true in every
logically possible case, so that the truth set of p must be U . Similarly,
if p is logically false, then it is false for every logically possible case, so
that its truth set is the empty set ….
Finally, let us consider the implication relation. Recall that p im-
plies p if and only if the conditional p ’ q is logically true. But p ’ q
is logically true if and only if its truth set is U , that is, (P ’ Q) = U , or
(P ’ Q) = …. From Figure 2.4 we see that if P ’ Q is empty, then P is
contained in Q. We shall symbolize the containing relation as follows:
P ‚ Q means “P is a subset of Q”. We conclude that p ’ q is logically
true if and only if P ‚ Q.
Figure 2.8 supplies a “dictionary” for translating from statement
language to set language, and back. To each statement relative to a
set of possibilities U there corresponds a subset of U , namely the truth
set of the statement. This is shown in lines 1 and 2 of the ¬gure. To
each connective there corresponds an operation on sets, as illustrated
in the next four lines. And to each relation between statements there
corresponds a relation between sets, examples of which are shown in
the last two lines of the ¬gure.

Example 2.3 Prove by means of a Venn diagram that the statement
[p ∨ (¬p ∨ q)] is logically true. The assigned set of this statement is
˜
[P ∪ (P ∪ Q)], and its Venn diagram is shown in Figure 2.9. In
˜
that ¬gure the set P is shaded vertically, and the set P ∪ Q is shaded
2.3. THE RELATIONSHIP BETWEEN SETS AND COMPOUND STATEMENTS17




Figure 2.8: ™¦




Figure 2.9: ™¦
18 CHAPTER 2. SETS AND SUBSETS




Figure 2.10: ™¦

horizontally. Their union is the entire shaded area, which is U , so that
™¦
the compound statement is logically true.

Example 2.4 Prove by means of Venn diagrams that p ∨ (q § r) is
equivalent to (p ∨ q) § (p ∨ r). The truth set of p ∨ (q § r) is the
entire shaded area in diagram (a) of Figure 2.10, and the truth set of
(p ∨ q) § (p ∨ r) is the doubly shaded area in diagram (b). Since these
two sets are equal, we see that the two statements are equivalent. ™¦

Example 2.5 Show by means of a Venn diagram that q implies p ’ q.
The truth set of p ’ q is the shaded area in Figure 2.7. Since this
shaded area includes the set Q. we see that q implies p ’ q. ™¦

Exercises
Note. In Exercises 1, 2, and 3, ¬nd ¬rst the truth set of each
statement.

1. Use Venn diagrams to test which of the following statements are
logically true or logically false.

(a) p ∨ ¬p.
[Ans. logically true.]
2.3. THE RELATIONSHIP BETWEEN SETS AND COMPOUND STATEMENTS19

(b) p § ¬p.
[Ans. logically false.]
(c) p ∨ (¬p § q).
(d) p ’ (q ’ p).
[Ans. logically true.]
(e) p § ¬(q ’ p).
[Ans. logically false.]

2. Use Venn diagrams to test the following statements for equiva-
lences.

(a) p ∨ ¬q.
(b) ¬(p § q).
(c) ¬(q § ¬q).
(d) p ’ ¬q.
(e) ¬p ∨ ¬q.

[Ans. 2a and 2c equivalent; 2b and 2d and 2e equivalent.]

3. Use Venn diagrams for the following pairs of statements to test
whether one implies the other.

(a) p; p § q.
(b) p § ¬q; ¬p ’ ¬q.
(c) p ’ q; q ’ p.
(d) p § q; p § ¬q.

4. Devise a test for inconsistency of p and q, using Venn diagrams.

5. Three or more statements are said to be inconsistent if they can-
not all be true. What does this state about their truth sets?

6. Consider these three statements.

If this is a good course, then I will work hard in it.

If this is not a good course, then I shall get a bad grade in it.
20 CHAPTER 2. SETS AND SUBSETS

I will not work hard, but I will get a good grade in this course.

(a) Assign variables to the components of each of these state-
ments.
(b) Bring the statements into symbolic form.
(c) Find the truth sets of the statements.
(d) Rest for consistency.

[Ans. Inconsistent.]

Note. In Exercises 7, 8, and 9, assign to each set a statement
having it as a truth set.

7. Use truth tables to ¬nd which of the following sets are empty.
˜˜
(a) (P ∪ Q) © (P ∪ Q).
˜
(b) (P © Q) © (Q © R).
(c) (P © Q) ’ P .
˜˜
(d) (P ∪ R) © (P ∪ Q)

[Ans. 7b and 7c.]

8. Use truth tables to ¬nd out whether the following sets are all
di¬erent.

(a) P © (Q ∪ R).
(b) (R ’ Q) ∪ (Q ’ R).
(c) (R ∪ Q) © (R © Q).
(d) (P © Q) ∪ (P © R).
˜ ˜ ˜ ˜ ˜˜
(e) (P © Q © R) ∪ (P © Q © R) ∪ (P © Q © R) ∪ (P © Q © R).

9. Use truth tables for the following pairs of sets to test whether one
is a subset of the other.

(a) P ; P © Q.
˜ ˜
(b) P © Q; Q © P .
(c) P ’ Q; Q ’ P .
21
2.4. THE ABSTRACT LAWS OF SET OPERATIONS

˜
(d) P © Q; P ∪ Q.



10. Show, both by the use of truth tables and by the use of Venn
diagrams, that p § (q ∨ r) is equivalent to (p § q) ∨ (p § r).



11. The symmetric di¬erence of P and Q is de¬ned to be (P ’ Q) ∪
(Q ’ P ). What connective corresponds to this set operation?



12. Let p, q, r be a complete set of alternatives (see Section ??). What
can we say about the truth sets P, Q, R?




2.4 The abstract laws of set operations

The set operations which we have introduced obey some very simple ab-
stract laws, which we shall list in this section. These laws can be proved
by means of Venn diagrams or they can be translated into statements
and checked by means of truth tables.
The abstract laws given below bear a close resemblance to the ele-
mentary algebraic laws with which the student is already familiar. The
resemblance can be made even more striking by replacing ∪ by + and
© by —. For this reason, a set, its subsets, and the laws of combi-
nation of subsets are considered an algebraic system, called a Boolean
algebra”after the British mathematician George Boole who was the
¬rst person to study them from the algebraic point of view. Any other
system obeying these laws, for example, the system of compound state-
ments studied in Chapter ??, is also known as a Boolean algebra. We
can study any of these systems from either the algebraic or the logical
point of view.
Below are the basic laws of Boolean algebras. The proofs of these
laws will be left as exercises.
The laws governing union and intersection:
22 CHAPTER 2. SETS AND SUBSETS

A1. A ∪ A = A.
A2. A © A = A.
A3. A ∪ B = B ∪ A.
A4. A © B = B © A.
A5. A ∪ (B ∪ C) = (A ∪ B) ∪ C.
A6. A © (B © C) = (A © B) © C.
A7. A © (B ∪ C) = (A © B) ∪ (A © C).
A8. A ∪ (B © C) = (A ∪ B) © (A ∪ C).
A9. A ∪ U = U .
A10. A © … = ….
A11. A ∪ … = A.
A12. A © U = A.
The laws governing complements:
˜˜
B1. A = A.
˜
B2. A ∪ A = U .
˜
B3. A © A = ….
˜˜
B4. A ∪ B = A © B.
˜˜
B5. A © B = A ∪ B.
˜
B6. U = ….
The laws governing set-di¬erences:
˜
C1. A ’ B = A © B.
˜
C2. U ’ A = A.
C3. A ’ U = ….
C4. A ’ … = A.
C5. … ’ A = ….
C6. A ’ A = ….
C7. (A ’ B) ’ C = A ’ (B ∪ C).
C8. A ’ (B ’ C) = (A ’ B) ∪ (A © C).
C9. A ∪ (B ’ C) = (A ∪ B) ’ (C ’ A).
C10. A © (B ’ C) = (A © B) ’ (A © C).


Exercises
1. Test laws in the group A1“A12 by means of Venn diagrams.

2. “Translate” the A-laws into laws about compound statements.
Test these by truth tables.

3. Test the laws in groups B and C by Venn diagrams.
23
2.4. THE ABSTRACT LAWS OF SET OPERATIONS

4. “Translate” the B- and C-laws into laws about compound state-
ments. Test these by means of truth tables.

5. Derive the following results from the 28 basic laws.

˜
(a) A = (A © B) ∪ (A © B).
˜ ˜
(b) A ∪ B = (A © B) ∪ (A © B) ∪ (A © B).
(c) A © (A ∪ B) = A.
˜
(d) A ∪ (A © B) = A ∪ B.

6. From the A- and B-laws and from C1, derive C2“C6.

7. Use A1“A12 and C2“C10 to derive B1, B2, B3, and B6.

Supplementary exercises.

Note. Use the following de¬nitions in these exercises: Let + be
symmetric di¬erence (see Exercise 11), — be intersection, let 0 be
… and 1 be U .

8. From A2, A4, and A6 derive the properties of multiplication.

9. Find corresponding properties for addition.

10. Set up addition and multiplication tables for 0 and 1.

11. What do A — 0, A — 1, A + 0, and A + 1 equal?

˜
[Ans. 0; A; A; A.]

12. Show that

A — (B + C) = (A — B) + (A — C).


13. Show that the following equation is not always true.

A + (B — C) = (A + B) — (A + C).
24 CHAPTER 2. SETS AND SUBSETS




Figure 2.11: ™¦


2.5 Two-digit number systems
In the decimal number system one can write any number by using only
the ten digits, 0, 1, 2, . . . , 9. Other number systems can be constructed
which use either fewer or more digits. Probably the simplest number
system is the binary number system which uses only the digits 0 and
1. We shall consider all the possible ways of forming number systems
using only these two digits.
The two basic arithmetical operations are addition and multiplica-
tion. To understand any arithmetic system, it is necessary to know
how to add or multiply any two digits together. Thus to understand
the decimal system, we had to learn a multiplication table and an ad-
dition table, each of which had 100 entries. To understand the binary
system, we have to learn a multiplication and an addition table, each
of which has only four entries. These are shown in Figure 2.11. The
multiplication table given there is completely determined by the two
familiar rules that multiplying a number by zero gives zero, and mul-
tiplying a number by one leaves it unchanged. For addition, we have
only the rule that the addition of zero to a number does not change
that number. The latter rule is su¬cient to determine all but one of
the entries in the addition table in Figure 2.11. We must still decide
what shall be the sum 1 + 1.
What are the possible ways in which we can complete the addition
table? The only one-digit numbers that we can use are 0 and l, and
these lead to interesting systems. Of the possible two-digit numbers, we
see that 00 and 01 are the same as 0 and l and so do not give anything
new. The number 11 or any greater number would introduce a “jump”
in the table, hence the only other possibility is 10. The addition tables
of these three di¬erent number systems are shown in Figure 2.12, and
they all have the multiplication table shown in Figure 2.11. Each of
these systems is interesting in itself as the interpretations below show.
Let us say that the parity of a positive integer is the fact of its being
25
2.5. TWO-DIGIT NUMBER SYSTEMS




Figure 2.12: ™¦

odd or even. Consider now the number system having the addition
table (a) in Figure 2.12 and let 0 represent “even” and 1 represent
“odd”. The tables above now tell how the parity of a combination of
two positive integers is related to the parity of each. Thus 0 · 1 = 0 tells
us that the product of an even number and an odd number is even,
while 1 + 1 = 0 tells us that the sum of two odd numbers is even, etc.
Thus the ¬rst number system is that which we get from the arithmetic
of the positive integers if we consider only the parity of numbers.
The second number system, which has the addition table (b) in Fig-
ure 2.12, has an interpretation in terms of sets. Let 0 correspond to the
empty set … and 1 correspond to the universal set U . Let the addition
of numbers correspond to the union of sets and let the multiplication
of sets correspond to the intersection of sets. Then 0 · 1 = 0 tells us
that … © U = … and 1 + 1 = 1 tells us that U ∪ U = U . The student
should give the interpretations for the other arithmetic computations
possible for this number system.
Finally, the third number system, which has the addition table in (c)
of Figure 2.12, is the so-called binary number system. Every ordinary
integer can be written as a binary integer. Thus the binary 0 corre-
sponds to the ordinary 0, and the binary unit 1 to the ordinary single
unit. The binary number 10 means a “unit of higher order” and corre-
sponds to the ordinary number two (not to ten). The binary number
100 then means two times two or four. In general, if bn bn’1 . . . b2 b1 b0 is a
binary number, where each digit is either 0 or 1, then the corresponding
ordinary integer I is given by the formula

I = bn · 2n + bn’1 · 2n’1 + . . . + b2 · 22 + b1 · 2 + b0 .

Thus the binary number 11001 corresponds to 24 + 23 + 1 = 16 + 8 + 1 =
25. The table in Figure 2.13 shows some binary numbers and their
decimal equivalents.
26 CHAPTER 2. SETS AND SUBSETS




Figure 2.13: ™¦

Because electronic circuits are particularly well adapted to perform-
ing computations in the binary system, modern high-speed electronic
computers are frequently constructed to work in the binary system.

Example 2.6 As an example of a computation, let us multiply 5 by
5 in the binary system. Since the binary equivalent of 5 is the number
101, the multiplication is done as follows.
1 01
1 01
1 01
0 0 0
10 1
11 0 01
The answer is the binary number 11001, which we saw above was equiv-
™¦
alent to the decimal integer 25, the answer we expected to get.

Exercises
1. Complete the interpretations of the addition and multiplication
tables for the number systems representing
(a) parity,
(b) the sets U and ….
2. (a) What are the binary numbers corresponding to the integers
11, 52, 64, 98, 128, 144?
[Partial Ans. 1100010 corresponds to 98.]
(b) What decimal integers correspond to the binary numbers
1111, 1010101, 1000000, 11011011?
27
2.5. TWO-DIGIT NUMBER SYSTEMS

[Partial Ans. 1010101 corresponds to 85.]

3. Carry out the following operations in the binary system. Check
your answer.

(a) 29 + 20.
(b) 9 · 7.

4. Of the laws listed below, which apply to each of the three systems?

(a) x + y = y + x.
(b) x + x = x.
(c) x + x + x = x.

5. Interpret a + b to be the larger of the two numbers a and b, and
a · b to be the smaller of the two. Write tables of “addition” and
“multiplication” for the digits 0 and 1. Compare the result with
the three systems given above.

[Ans. Same as the U , … system.]

6. What do the laws A1“A10 of Section 2.4 tell us about the second
number system established above?

7. The ¬rst number system above (about parity) can be interpreted
to deal with the remainders of integers when divided by 2. An
even number leaves 0, an odd number leaves 1. Construct tables
of addition and multiplication for remainders of integers when
divided by 3. [Hint: These will be 3 by 3 tables.]

8. Given a set of four elements, suppose that we want to number
its subsets. For a given subset, write down a binary number as
follows: The ¬rst digit is 1 if and only if the ¬rst element is in the
subset, the second digit is 1 if and only if the second element is
in the subset, etc. Prove that this assigns a unique number, from
0 to 15, to each subset.

9. In a multiple choice test the answers were numbered 1, 2, 4, and
8. The students were told that there might be no correct answer,
or that one or more answers might be correct. They were told to
add together the numbers of the correct answers (or to write 0 if
no answer was correct).
28 CHAPTER 2. SETS AND SUBSETS

(a) By using the result of Exercise 8, show that the resulting
number gives the instructor all the information he or she
wants.
(b) On a given question the correct sum was 7. Three students
put down 4, 8, and 15, respectively. Which answer was most
nearly correct? Which answer was worst?
[Ans. 15 best, 8 worst.]

10. In the ternary number system, numbers are expressed to the base
3, so that 201 in this system stands for 2 · 32 + 0 · 3 + 1 · 1 = 19.

(a) Write the numbers from 1 through 30 in this notation.
(b) Construct a table of addition and multiplication for the dig-
its 0, 1, 2.
(c) Carry out the multiplication of 5 · 5 in this system. Check
your answer.

11. Explain the meaning of the numeral “2907” in our ordinary (base
10) notation, in analogy to the formula given for the binary sys-
tem.

12. Show that the addition and multiplication tables set up in Exer-
cise 10 correspond to one of our three systems.


2.6 Voting coalitions
As an application of our set concepts, we shall consider the signi¬cance
of voting coalitions in voting bodies. Here the universal set is a set
of human beings which form a decision-making body. For example,
the universal set might be the members of a committee, or of a city
council, or of a convention, or of the House of Representatives, etc.
Each member can cast a certain number of votes. The decision as to
whether or not a measure is passed can be decided by a simple majority
rule, or two-thirds majority, etc.
Suppose now that a subset of the members of the body forms a
coalition in order to pass a measure. The question is whether or not
they have enough votes to guarantee passage of the measure. If they
have enough votes to carry the measure, then we say they form a win-
ning coalition. If the members not in the coalition can pass a measure
29
2.6. VOTING COALITIONS

of their own, then we say that the original coalition is a losing coalition.
Finally, if the members of the coalition cannot carry their measure, and
if the members not in the coalition cannot carry their measure, then
the coalition is called a blocking coalition.
Let us restate these de¬nitions in set-theoretic terms. A coalition
C is winning if they have enough votes to carry an issue; coalition C
˜
is losing if the coalition C is winning; and coalition C is blocking if
˜
neither C nor C is a winning coalition.
The following facts are immediate consequences of these de¬nitions.
The complement of a winning coalition is a losing coalition. The com-
plement of a losing coalition is a winning coalition. The complement of
a blocking coalition is a blocking coalition.

Example 2.7 A committee consists of six members each having one
vote. A simple majority vote will carry an issue. Then any coalition
of four or more members is winning, any coalition with one or two
™¦
members is losing, and any three-person coalition is blocking.


Example 2.8 Suppose in Example 2.7 one of the six members (say
the chair) is given the additional power to break ties. Then any three-
person coalition of which the chair is a member is winning, while the
other three-person coalitions are losing; hence there are no blocking
™¦
coalitions. The other coalitions are as in Example 2.7.


Example 2.9 Let the universal set U be the set {x, y, w, z}, where x
and y each has one vote, w has two votes, and z has three votes. Suppose
it takes ¬ve votes to carry a measure. Then the winning coalitions are:
{z, w}, {z, x, y}, {z, w, x}, {z, w, y}, and U . The losing coalitions are
the complements of these sets. Blocking coalitions are: {z}, {z, x},
{z, y}, {w, x}, {w, y}, and {w, x, y}. ™¦

The last example shows that it is not always necessary to list all
members of a winning coalition. For example, if the coalition {z, w} is
winning, then it is obvious that the coalition {z, w, y} is also winning.
In general, if a coalition C is winning, then any other set that has C as a
subset will also be winning. Thus we are led to the notion of a minimal
winning coalition. A minimal winning coalition is a winning coalition
which contains no smaller winning coalition as a subset. Another way
of stating this is that a minimal winning coalition is a winning coalition
30 CHAPTER 2. SETS AND SUBSETS

such that, if any member is lost from the coalition, then it ceases to be
a winning coalition.
If we know the minimal winning coalitions, then we know everything
that we need to know about the voting problem. The winning coalitions
are all those sets that contain a minimal winning coalition, and the
losing coalitions are the complements of the winning coalitions. All
other sets are blocking coalitions.
In Example 2.7 the minimal winning coalitions are the sets contain-
ing four members. In Example 2.8 the minimal winning coalitions are
the three-member coalitions that contain the tie-breaking member and
the four-member coalitions that do not contain the tie-breaking mem-
ber. The minimal winning coalitions in the third example are the sets
{z, w} and {z, x, y}.
Sometimes there are committee members who have special powers
or lack of power. If a member can pass any measure he or she wishes
without needing anyone else to vote with him or her, then we call him
or her a dictator. Thus member x is a dictator if and only if {x} is a
winning coalition. A somewhat weaker but still very powerful member
is one who can by himself or herself block any measure. If x is such a
member, then we say that x has veto power. Thus x has veto power
if and only if {x} is a blocking coalition. Finally if x is not a member
of any minimal winning coalition, we shall call him or her a powerless
member. Thus x is powerless if and only if any winning coalition of
which x is a member is a winning coalition without him or her.

Example 2.10 An interesting example of a decision-making body is
the Security Council of the United Nations. (We discuss the rules
prior to 1966.) The Security Council has eleven members consisting
of the ¬ve permanent large-nation members called the Big Five, and
six small-nation members. In order that a measure be passed by the
Council, seven members including all of the Big Five must vote for the
measure. Thus the seven-member sets made up of the Big Five plus
two small nations are the minimal winning coalitions. Then the losing
coalitions are the sets that contain at most four small nations. The
blocking coalitions are the sets that are neither winning nor losing. In
particular, a unit set that contains one of the Big Five as a member
is a blocking coalition. This is the sense in which a Big Five member
has a veto. [The possibility of “abstaining” is immaterial in the above
discussion.]
In 1966 the number of small-nation members was increased to 10.
31
2.6. VOTING COALITIONS

A measure now requires the vote of nine members, including all of the
™¦
Big Five. (See Exercise 11.)

Exercises
1. A committee has w, x, y, and z as members. Member w has two
votes, the others have one vote each. List the winning, losing,
and blocking coalitions.

2. A committee has n members, each with one vote. It takes a
majority vote to carry an issue. What are the winning, losing,
and blocking coalitions?

3. Rhe Board of Estimate of New York City consists (that is, con-
sisted at one time) of eight members with voting strength as fol-
lows:

s. Mayor 4 votes
t. Controller 4
u. Council President 4
v. Brooklyn Borough President 2
w. Manhattan Borough President 2
x. Bronx Borough President 2
y. Richmond Borough President 2
z. Queens Borough President 2

A simple majority is needed to carry an issue. List the minimal
winning coalitions. List the blocking coalitions. Do the same if
we give the mayor the additional power to break ties.

4. A company has issued 100,000 shares of common stock and each
share has one vote. How many shares must a stockholder have to
be a dictator? How many to have a veto?

[Ans. 50,001; 50,000.]

5. In Exercise 4, if the company requires a two-thirds majority vote
to carry an issue, how many shares must a stockholder have to
be a dictator or to have a veto?

[Ans. At least 66,667; at least 33,334.]
32 CHAPTER 2. SETS AND SUBSETS

6. Prove that if a committee has a dictator as a member, then the
remaining members are powerless.

7. We can de¬ne a maximal losing coalition in analogy to the mini-
mal winning coalitions. What is the relation between the maximal
losing and minimal winning coalitions? Do the maximal losing
coalitions provide all relevant information?

8. Prove that any two minimal winning coalitions have at least one
member in common.

9. Find all the blocking coalitions in the Security Council example
(Example 2.10).

10. Prove that if a member has veto power and if he or she together
with any one other member can carry a measure, then the distri-
bution of the remaining votes is irrelevant.

11. Find the winning, losing, and blocking coalitions in the Security
Council, using the revised (1966) structure.

Suggested reading.
Birkho¬, G., and S. MacLane, A Survey of Modern Algebra, 1953,
Chapter XI.
Tarski, A., Introduction to Logic, 2d rev. ed., 1946, Chapter IV.
Allendoerfer, C. B., and C. O. Oakley, Principles of Mathematics, 1955,
Chapter V.
Johnstone, H. W., Jr., Elementary Deductive Logic, 1954, Part Three.
Breuer, Joseph, Introduction to the Theory of Sets, 1958.
Fraenkel, A. A., Abstract Set Theory, 1953.
Kemeny, John G., Hazleton Mirkil, J. Laurie Snell, and Gerald L.
Thompson, Finite Mathematical Structures, 1959, Chapter 2.
Chapter 3

Partitions and counting

3.1 Partitions
The problems to be studied in this chapter can be most conveniently
described in terms of partitions of a set. A partition of a set U is a
subdivision of the set into subsets that are disjoint and exhaustive, i.e.,
every element of U must belong to one and only one of the subsets.
The subsets Ai in the partition are called cells. Thus [A1 , A2 , . . . , Ar ]
is a partition of U if two conditions are satis¬ed: (1) Ai © Aj = … if
i = j (the cells are disjoint) and (2) A1 ∪ A2 ∪ . . . ∪ Ar = U (the cells
are exhaustive).

Example 3.1 If U = {a, b, c, d, e}, then [{a, b}, {c, d, e}] and [{b, c, e}, {a}, {d}]
and [{a}, {b}, {c}, {d}, {e}] are three di¬erent partitions of U . The last
™¦
is a partition into unit sets.
The process of going from a ¬ne to a less ¬ne analysis of a set of
logical possibilities is actually carried out by means of a partition. For
example, let us consider the logical possibilities for the ¬rst three games
of the World Series if the Yankees play the Dodgers. We can list the
possibilities in terms cf the winner of each game as
{YYY, YYD, YDY, DYY, DDY, DYD, YDD, DDD}.
We form a partition by putting all the possibilities with the same num-
ber of wins for the Yankees in a single cell,
[{YYY}, {YYD, YDY, DYY}, {DDY, DYD, YDD}, {DDD}].
Thus, if we wish the possibilities to be Yankees win three games, win
two, win one, win zero, then we are considering a less detailed analysis

33
34 CHAPTER 3. PARTITIONS AND COUNTING

obtained from the former analysis by identifying the possibilities in each
cell of the partition.
If [A1 , A2 , . . . , Ar ] and [B1 , B2 , . . . , Bs ] are two partitions of the same
set U , we can obtain a new partition by considering the collection of all
subsets of U of the form Ai © Bj (see Exercise 7). This new partition
is called the cross-partition of the original two partitions.

Example 3.2 A common use of cross-partitions is in the problem of
classi¬cation. For example, from the set U of all life forms we can form
the partition [P, A] where P is the set of all plants and A is the set
of all animals. We may also form the partition [E, F ] where E is the
set of extinct life forms and F is the set of all existing life forms. The
cross-partition
[P © E, P © F, A © E, A © F ]
gives a complete classi¬cation according to the two separate classi¬ca-
™¦
tions.
Many of the examples with which we shall deal in the future will
relate to processes which take place in stages. It will be convenient
to use partitions and cross-partitions to represent the stages of the
process. The graphical representation of such a process is, of course,
a tree. For example, suppose that the process is such that we learn in
succession the truth values of a series of statements relative to a given
situation. If U is the set of logical possibilities for the situation, and
p is a statement relative to U , then the knowledge of the truth value
˜
of p amounts to knowing which cell of the partition [P, P ] contains the
˜
actual possibility. Recall that P is the truth set of p, and P is the
truth set of ¬p. Suppose now we discover the truth value of a second
statement q. This information can again be described by a partition,
˜
namely, [Q, Q]. The two statements together give us information which
can be represented by the cross-partition of these two partitions,
˜˜ ˜˜
[P © Q, P © Q, P © Q, P © Q].

That is, if we know the truth values of p and q, we also know which
of the cells of this cross-partition contains the particular logical pos-
sibility describing the given situation. Conversely, if we knew which
cell contained the possibility, we would know the truth values for the
statements p and q.
The information obtained by the additional knowledge of the truth
value of a third statement r, having a truth set R, can be represented
35
3.1. PARTITIONS

˜ ˜ ˜
by the cross-partition of the three partitions [P, P ], [Q, Q], [R, R] This
cross-partition is
˜ ˜ ˜ ˜˜ ˜ ˜˜ ˜ ˜˜˜
[P ©Q©R, P ©Q©R, P ©Q©R, P ©Q©R, P ©Q©R, P ©Q©R, P ©Q©R, P ©Q©R].

Notice that now we have the possibility narrowed down to being in one
of 8 = 23 possible cells. Similarly, if we knew the truth values of n
statements, our partition would have 2n cells.
If the set U were to contain 220 (approximately one million) logical
possibilities, and if we were able to ask yes-no questions in such a way
that the knowledge of the truth value of each question would cut the
number of possibilities in half each time, then we could determine in 20
questions any given possibility in the set U . We could accomplish this
kind of questioning, for example, if we had a list of all the possibilities
and were allowed to ask “Is it in the ¬rst half?” and, if the answer is
yes, then “Is it in the ¬rst one-fourth?”, etc. In practice we ordinarily
do not have such a list, and we can only approximate this procedure.

Example 3.3 In the familiar radio game of twenty questions it is not
unusual for a contestant to try to carry out a partitioning of the above
kind. For example, he or she may know that he or she is trying to guess
a city. He or she might ask, “Is the city in North America?” and if the
answer is yes, “Is it in the United States?” and if yes, “Is it west of
the Mississippi?” and if no, “Is it in the New England states?”, etc. Of
course, the above procedure does not actually divide the possibilities
exactly in half each time. The more nearly the answer to each question
comes to dividing the possibilities in half, the more certain one can be
of getting the answer in twenty questions, if there are at most a million
™¦
possibilities.

Exercises
1. If U is the set of integers from 1 to 6, ¬nd the cross-partitions of
the following pairs of partitions

(a) [{1, 2, 3}, {4, 5, 6}] and [{1, 4}, {2, 3, 5, 6}].
[Ans. [{1}, {2, 3}, {4}, {5, 6}].]
(b) [{1, 2, 3, 4, 5}, {6}] and [{1, 3, 5}, {2, 6}, {4}].

2. A coin is thrown three times. List the possibilities according to
which side turns up each time. Give the partition formed by
36 CHAPTER 3. PARTITIONS AND COUNTING

putting in the same cell all those possibilities for which the same
number of heads occur.

3. Let p and q be two statements with truth set P and Q. What
˜ ˜
can be said about the cross-partition of [P, P ] and [Q, Q] in the
case that

(a) p implies q.
˜
[Ans. P © Q = ….]

(b) p is equivalent to q.
(c) p and q are inconsistent.

4. Consider the set of eight states consisting of Illinois, Colorado,
Michigan, New York, Vermont, Texas, Alabama, and California.

(a) Show that in three “yes” or “no” questions one can identify
any one of the eight states.
(b) Design a set of three “yes” or “no” questions which can be
answered independently of each other and which will serve
to identify any one of the states.

5. An unabridged dictionary contains about 600,000 words and 3000
pages. If a person chooses a word from such a dictionary, is it
possible to identify this word by twenty “yes” or “no” questions?
If so, describe the procedure that you would use and discuss the
feasibility of the procedure. (One approach is the following. Use
12 questions to locate the page, but then you may need 9 questions
to locate the word.)

6. Jones has two parents, each of his or her parents had two parents,
each of these had two parents, etc. Tracing a person™s family tree
back 40 generations (about 1000 years) gives Jones 240 ancestors,
which is more people than have been on the earth in the last 1000
years. What is wrong with this argument?

7. Let [A1 , A2 , A3 ] and [B1 , B2 ] be two partitions. Prove that the
cross-partition of the two given partitions really is a partition,
that is, it satis¬es requirements (1) and (2) for partitions.
37
3.1. PARTITIONS

8. The cross-partition formed from the truth sets of n statements
has 2n cells. As seen in Chapter ??, the truth table of a state-
ment compounded from n statements has 2n rows. What is the
relationship between these two facts?

9. Let p and q be statements with truth sets P and Q. Form the
˜˜ ˜˜
partition [P © Q, P © Q, P © Q, P © Q]. State in each case below
which of the cells must be empty in order to make the given
statement a logically true statement.

(a) p ’ q
(b) p ” q
(c) p ∨ ¬p
(d) p

10. A partition [A1 , A2 , . . . , An ] is said to be a re¬nement of the par-
tition [B1 , B2 , . . . , Bm ] if every Aj is a subset of some Bk . Show
that a cross-partition of two partitions is a re¬nement of each of
the partitions from which the cross-partition is formed.

11. Consider the partition of the people in the United States deter-
mined by classi¬cation according to states. The classi¬cation ac-
cording to county determines a second partition. Show that this
is a re¬nement of the ¬rst partition. Give a third partition which
is di¬erent from each of these and is a re¬nement of both.

12. What can be said concerning the cross-partition of two partitions,
one of which is a re¬nement of the other?

13. Given nine objects, of which it is known that eight have the same
weight and one is heavier, show how, in two weighings with a pan
balance, the heavy one can be identi¬ed.

14. Suppose that you are given thirteen objects, twelve of which are
the same, but one is either heavier or lighter than the others.
Show that, with three weighings using a pan balance, it is possible
to identify the odd object. (A complete solution to this problem
is given on page 42 of Mathematical Snapshots, second edition,
by H. Steinhaus.)

15. A subject can be completely classi¬ed by introducing several sim-
ple subdivisions and taking their cross-partition. Thus, courses
38 CHAPTER 3. PARTITIONS AND COUNTING

in college may be partitioned according to subject, level of ad-
vancement, number of students, hours per week, interests, etc.
For each of the following subjects, introduce ¬ve or more par-
titions. How many cells are there in the complete classi¬cation
(cross-partition) in each case?

(a) Detective stories.
(b) Diseases.

16. Assume that in a given generation x men are Republicans and y
are Democrats and that the total number of men remains at 50
million in each generation. Assume further that it is known that
20 per cent of the sons of Republicans are Democrats and 30 per
cent of the sons of Democrats are Republicans in any generation.
What conditions must x and y satisfy if there are to be the same
number of Republicans in each generation? Is there more than
one choice for x and y? If not, what must x and y be?

[Partial Ans. There are 30 million Republicans.]

17. Assume that there are 30 million Democratic and 20 million Re-
publican men in the country. It is known that p per cent of the
sons of Democrats are Republicans, and q per cent of the sons
of Republicans are Democrats. If the total number of men re-
mains 50 million, what condition must p and q satisfy so that the
number in each party remains the same? Is there more than one
choice of p and q?


3.2 The number of elements in a set
The remainder of this chapter will be devoted to certain counting prob-
lems. For any set X we shall denote by n(X) the number of elements
in the set.
Suppose we know the number of elements in certain given sets and
wish to know the number in other sets related to these by the opera-
tions of unions, intersections, and complementations. As an example,
consider the following problem.
Suppose that we are told that 100 students take mathematics, and
150 students take economics. Can we then tell how many take either
mathematics or economics? The answer is no, since clearly we would
39
3.2. THE NUMBER OF ELEMENTS IN A SET




Figure 3.1: ™¦

also need to know how many students take both courses. If we know
that no student takes both courses, i.e., if we know that the two sets
of students are disjoint, then the answer would be the sum of the two
numbers or 250 students.
In general, if we are given disjoint sets A and B, then it is true that
n(A∪B) = n(A)+n(B). Suppose now that A and B are not disjoint as
˜
shown in Figure 3.1. We can divide the set A into disjoint sets A © B
˜
and A © B. Similarly, we can divide B into the disjoint sets A © B and
A © B. Thus,
˜
n(A) = n(A © B) + n(A © B),
˜
n(B) = n(A © B) + n(A © B).
Adding these two equations, we obtain
˜ ˜
n(A) + (B) = n(A © B) + n(A © B) + n(A © B) + 2n(A © B).
˜ ˜
Since the sets A © B, A © B, and A © B are disjoint sets whose union
is A ∪ B, we obtain the formula

n(A ∪ B) = n(A) + n(B) ’ n(A © B),

which is valid for any two sets A and B.

Example 3.4 Let p and q be statements relative to a set U of logical
possibilities. Denote by P and Q the truth sets of these statements.
The truth set of p ∨ q is P ∪ Q and the truth set of p § q is P © Q. Thus
the above formula enables us to ¬nd the number of cases where p ∨ q is
true if we know the number of cases for which p, q, and p § q are true.
™¦
40 CHAPTER 3. PARTITIONS AND COUNTING




Figure 3.2: ™¦

Example 3.5 More than two sets. It is possible to derive formulas for
the number of elements in a set which is the union of more than two
sets (see Exercise 6), but usually it is easier to work with Venn dia-
grams. For example, suppose that the registrar of a school reports the
following statistics about a group of 30 students: l9 take mathematics.
17 take music. 11 take history. 12 take mathematics and music. 7 take
history and mathematics. 5 take music and history. 2 take mathemat-
ics, history, and music. We draw the Venn diagram in Figure 3.2 and
¬ll in the numbers for the number of elements in each subset working
from the bottom of our list to the top. That is, since 2 students take
all three courses, and 5 take music and history, then 3 take history and
music but not mathematics, etc. Once the diagram is completed we
can read o¬ the number which take any combination of the courses.
For example, the number which take history but not mathematics is
™¦
3 + 1 = 4.

Example 3.6 Cancer studies. The following reasoning is often found
in statistical studies on the e¬ect of smoking on the incidence of lung
cancer. Suppose a study has shown that the fraction of smokers among
those who have lung cancer is greater than the fraction of smokers
among those who do not have lung cancer. It is then asserted that the
fraction of smokers who have lung cancer is greater than the fraction
of nonsmokers who have lung cancer. Let us examine this argument.
Let S be the set of all smokers in the population, and C be the
41
3.2. THE NUMBER OF ELEMENTS IN A SET




Figure 3.3: ™¦

˜
set of all people with lung cancer. Let a = n(S © C), b = n(S © C),
˜ ˜˜
c = n(S © C) and d = n(S © C), as indicated in Figure 3.3. The
fractions in which we are interested are
a c a b
p1 = , p2 = , p3 = , p4 = ,
a+b c+d a+c b+d
where p1 is the fraction of those with lung cancer that smoke, p2 the
fraction of those without lung cancer that smoke, p3 the fraction of
smokers who have lung cancer, and p4 the fraction of nonsmokers who
have cancer.
The argument above states that if p1 > p2 , then p3 > p4 . The
hypothesis,
a c
>
a+b c+d
is true if and only if ac + ad > ac + bc, that is, if and only if ad > bc.
The conclusion
a b
>
a+c b+d
is true if and only if ab + ad > ab + bc, that is, if and only if ad > bc.
Thus the two statements p1 > p2 and p3 > p4 are in fact equivalent
™¦
statements, so that the argument is valid.

Exercises
1. In Example 3.5, ¬nd

(a) The number of students that take mathematics but do not

. 1
( 6)



>>