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