A set is a collection of items, referred to as the elements of the set.

x ∈ A means that x is an element of the set A.

x ∉ A means that x is not an element of the set A.

B = A means that A and B have the same elements.

B ⊆ A means that B is a subset of A; every element of B is also an element of A.

B ⊂ A means that B is a proper subset of A; in other words, B ⊆ A, but B ≠ A.

Ø is the empty set, the set containing no elements. It is a subset of every set.

A finite set is a set that has finitely many elements. An infinite set is a set that does not have finitely many elements.

b ∈ {a, b, c, d}

e ∉ {a, b, c, d}

{1, 2, 4, 5} = {2, 1, 5, 4}

{1, 2, 3} ⊆ {1, 2, 3}

{1, 2, 3} ⊆ {1, 2, 3, 4}

{1, 2, 3} ⊂ {1, 2, 3, 4}

{1, 2, 3, ..., 1000} is a finite set.

{1, 2, 3, ...} is an infinite set.

Any given set	is a proper subset of itself is a subset of itself is not a subset of itself
The null set	is a proper subset of every set is not a subset of itself is a proper subset of every set except itself

If we perform some kind of experiment that has one or more outsomes, we can think of the possible outcomes as being the elements of a set of outcomes associated with that experiment. (We say more about sets of ourtcomes when we disucss probability in the Chapter 7 Summary.)

As the examples show, we can often represent the same set of outcomes in different ways.

1, If we toss a coin and observe which side faces up, the set of outcomes can be written as

S = {Heads, Tails}

S = {H, T}.

2, If we roll a die with faces numbered 1 through 6, the set of outcomes can be represented as

S = {

, , , , ,

},

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

2, If we roll two distinguishable dice (for instance, one red and one green) with faces numbered 1 through 6, the set of outcomes can be represented as

S =

or simply

S =		(1, 1),	(1, 2),	(1, 3),	(1, 4),	(1, 5),	(1, 6),
		(2, 1),	(2, 2),	(2, 3),	(2, 4),	(2, 5),	(2, 6),
		(3, 1),	(3, 2),	(3, 3),	(3, 4),	(3, 5),	(3, 6),
		(4, 1),	(4, 2),	(4, 3),	(4, 4),	(4, 5),	(4, 6),
		(5, 1),	(5, 2),	(5, 3),	(5, 4),	(5, 5),	(5, 6),
		(6, 1),	(6, 2),	(6, 3),	(6, 4),	(6, 5),	(6, 6)

3, If we roll two indistinguishable dice (that is, two identical dice) with faces numbered 1 through 6, the set of outcomes can be represented as

S =		(1, 1),	(1, 2),	(1, 3),	(1, 4),	(1, 5),	(1, 6),
			(2, 2),	(2, 3),	(2, 4),	(2, 5),	(2, 6),
				(3, 3),	(3, 4),	(3, 5),	(3, 6),
					(4, 4),	(4, 5),	(4, 6),
						(5, 5),	(5, 6),
							(6, 6)

Each diagram in the following figure represents the relation listed below it.

Neither A nor B a subset of the other

For a proper inclusion, the disk of B must be smaller than the disk of A. For simplicity we usually take the drawing in the figure representing B a proper subset of A to also represent B a subset of A.

The following Venn diagram illustrates the relationship among the three sets

{March}, {March, April, May}, and {June, July, August}.

The union of A and B is the set of all elements that are either in A or B (or both).

A B = {x | x A or x B}

The intersection of A and B is the set of all elements that are common to A and B.

A B = {x | x A and x B}

If A is a subset of S, then A' is the complement of A in S, the set of all elements of S not in A.

We can picture the complement in the Venn diagram shown below.

Let S be the set of all integers, and let

A = {2, 4, 6, 8}

B = {5, 6, 7, 8}

C = {positive even integers}

D = {1, 2, 3}.

Then

A B = {2, 4, 5, 6, 7, 8}

A B = {6, 8}

A C = A

C' = {0, 1, -1, -2, 3, -3, -4, 5, -5, . . .}

A (B C) = A.

A D = {		}
A D = {		}
D A' = {		}
A (B D) = {		}

We also have De Morgan's Laws, which follow from the definitions:

Press here and scroll down to the discussion after Example 7 to see the counterparts in propositional logic (and visit the entire logic site while you're at it!).

The Cartesian product of two sets, A and B, is the set of all ordered pairs (a, b) with a A and b B.

A B = { (a, b) | a A and b B }.

In Words

AB is the set of all ordered pairs whose first component is in A and whose second component is in B.

1. If A = {a, b} and B = {1, 2, 3}, then

A B = { (a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3) }.

2. Take S = {H, T}.       (H stands for Heads, T stands for Tails)

S S = { (H,H), (H,T), (T,H), T,T) }.

In other words, if S is the set of outcomes of tossing a coin once, then SS is the set of outcomes of tossing a coin twice.

3. S = {1, 2, 3, 4, 5, 6}    The set of outcomes of rolling a die

S S

=

(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5), (2, 6), (3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (3, 6), (4, 1), (4, 2), (4, 3), (4, 4), (4, 5), (4, 6), (5, 1), (5, 2), (5, 3), (5, 4), (5, 5), (5, 6), (6, 1), (6, 2), (6, 3), (6, 4), (6, 5), (6, 6)

In other words, if S is the set of outcomes of a rolling a die once, then SS is the set of outcomes of rolling a die twice (or rolling two distinguishable dice).

4. If A = {Red, Yellow} and B = {Mustang, Firebird} then

AB = { (Red, Mustang), (Red, Firebird), (Yellow, Mustang), (Yellow, Firebird)},

which we might also write as

AB = {Red Mustang, Red Firebird, Yellow Mustang, Yellow Firebird}.

1. Let S be the set of all playing cards in a standard deck, and let

Then

n(D H)	=	n(D) + n(H)	Since D H = Ø
	=	13 +13 = 26
n(D T)	=	n(D) + n(T) - n(D T)
	=	13+4-1 = 16
n(D')	=	n(S) -n(D)
	=	52-13 = 39.

2. Let

A decision algorithm is a procedure with definite rules or instructions for what to do at every step.

We can use decision algorithms to help us count the number of possible elements in any set as follows:

A. Formulate a Decision Algorithm
If you are asked how many possible elements there are, pretend that you are constructing such an element, and come up with a step-by-step procedure -- that is, a decision algorithm -- for doing this. List the steps you would take, showing the number of choices for each step.

B. Apply the following "Acid Test"
Ask yourself the following question: "Suppose that I went through the algorithm twice, but the second time made a different choice at one or more of the steps. Would I then get a different outcome?" If the answer is "yes," then your decision algorithm is a valid one. If your algorithm is not valid, you need to come up with another algorithm.

Here are two decision algorithms to calculate the number of different five-letter strings containing two "s"s, one "i," one "e," and one "d." The first one is not valid -- it fails the "acid test", and the second one is valid.

Decision Algoriothm 1 (Not Valid)
Pretend you were constructing such a string by placing the five letters in five slots one-at-a-time:

		Possible Outcome
1.	Place the first "s." (5 open slots to choose from)	s
2.	Place the second "s." (4 remaining open slots to choose from)	s       s
3.	Place the "i." (3 remaining open slots to choose from)	s i     s
4.	Place the "e." (2 remaining open slots to choose from)	s i   e s
5.	Place the "d." (1 remaining open slot to choose from)	s i d e s

Acid Test
You can obtain the same string "sides" by reversing the choices in steps 1 and 2. Therefore, the acid test fails for this procedure.

Decision Algoriothm 2 (Valid)
Pretend you were constructing such a string by assigning groups of slots to the four different lettters, starting with the letters that appear once (to make it easier);

		Possible Outcome
1.	Assign a slot for the "i." (5 open slots to choose from)	i
2.	Assign a slot for the "e." (4 remaining open slots to choose from)	e       i
3.	Assign a slot for the "d." (3 remaining open slots to choose from)	e d     i
4.	Assign a pair of slots for the "s"s. (1 remaining pair of slots to choose from)	e d s s i

Acid Test
Making different choices in any of the steps will result in a different string. Therefore, the acid test passes for this procedure.

If a decision algoriothm requires several steps, with Step 1 having n₁ outcomes, Step 2 having n₂ outcomes, . . . , Step r having n_r outcomes, then the number of outcomes of the algorithm is n₁ n₂ . . . n_r.

Look at Decision algoriothm 2 above. The number of outcomes of each step is as follows:

Step 1:   5 possible outcomes

Step 2:   4 possible outcomes

Step 3:   3 possible outcomes

Step 4:   1 possible outcome

5431 = 60. In other words, there are a total of 60 possible five-letter strings containing two "s"s, one "i," one "e," and one "d."

Top of Page

If a decision algoriothm requires a choice among several different alternatives, then the total number of outcomes is obtained by adding the number of outcomes of each alternative.

In this example, we combine the Multiplication and Addition Principles to calculate the number of possible 2-course meals from the following menu:

Decision Algoriothm

Step 1: Choose a soup: 2 choices
Step 2: Choose an entree:

Alternative 1: Beef: 2 choices of side dish
Alternative 2: Pork: 3 choices of side dish

A permutation of n items taken r at a time is an ordered list of r items chosen from a set of n items. The number of permutations of n items taken r at a time is given by

P(n, r)	=	n (n-1) (n-2) . . . (n-r+1)
	=	n! (n-r)!	.

n! = 123...(n-1) n

C(n, r)	=	P(n, r) r!
	=	n! r! (n-r)!	.
	=	n(n-1)...(n-r+1) r(r-1) ...21	.

Note

0! = 1   Zero factorial equals 1.

It follows that C(n, 0) = n! 0! n! = n! n! = 1

If a and b add up to n, then     C(n ,a) = C(n, b)   See the examples.

P(7, 3)

=

765

=

210.

C(7, 3)

=

76 5 321

=

35.

Since 5 and 2 add up to 7, we have

C(7, 5) = C(7, 2) =

=

76 21

=

21.

P(4, 1) =
P(4, 4) =
C(4, 2) =
C(4, 0) =
C(4, 4) =
C(100, 98) =