## Summary of Chapter 6 inFinite Mathematics/Finite Mathematics & Applied CalculusTopic: Sets and Counting

Student Home
True/False Quiz
Review Exercises
Summary Index
Everything for Calculus
Everything for Finite Math
Everything for Finite Math & Calculus
Chapter 5 Summary     Chapter 7 Summary

Sets and Elements | Sets of Outcomes | Venn Diagrams | Set Operations: Union, Intersection, and Complement | Cardinality | Decision Algorithm | Multiplication Principle | Addition Principle | Permutations and Combinations

Sets and Elements

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.

Examples
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

Top of Page

Sets of Outcomes

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.

Examples

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

or simply
S = {H, T}.

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

 S = { , , , , , },
or simply
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)

Top of Page

Venn Diagrams

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.

Example

The following Venn diagram illustrates the relationship among the three sets

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

Top of Page
Set Operations: Union, Intersection, and Complement

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}
We can picture the union in the Venn diagram shown below.

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}
We can picture the intersection in the Venn diagram shown below.

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.

Examples

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:

 De Morgan's Laws (A B)' = A' B' (A B)' = A' B'

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!).

Top of Page
Cartesian Product

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.
Examples

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}.

Top of Page
Cardinality

If A is a finite set, then n(A), the number of elements A contains, is called the cardinality of A.

If A and B are finite sets, then

n(A B) = n(A) + n(B) - n(A B).
In particular, if A and B are disjoint then
n(A B) = n(A) + n(B).

If S is a finite universal set and A is a subset of S, then

n(A') = n(S) - n(A) and n(A) = n(S) - n(A').

If A and B are finite sets, then

n(AB) = n(A).n(B)
Examples

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

 D = set of diamonds;   n(D) = 13 T = set of tens;   n(T) = 4 H = set of hearts   n(H) = 13.

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

 T = set of suites = {Spades, Hearts, Diamonds, Clubs} D = set of denominations = {2, 3, 4, 5, 6, 7, 8, 9, J, Q, K, A}
Then n(TD) = 413 = 52, accounting for all the cards in a standard deck.

Top of Page
Decision Algorithm

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.

Example

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.

Top of Page
Multiplication Principle

If a decision algoriothm requires several steps, with Step 1 having n1 outcomes, Step 2 having n2 outcomes, . . . , Step r having nr outcomes, then the number of outcomes of the algorithm is n1 n2 . . . nr.

Example

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
Therefore, the total number of outcomes is
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.

Example

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

 Menu Soups Du Joir Creme de la Creme Creme of Tomato Entree Roast Beef with Potatoes or Brussel Sprouts Loin of Pork with Apple, Mango, or Papaya Have a Nice Day

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
The Addition Principle gives a total of 2+3 = 5 choices for Step 2 The Multiplication Principle now gives 25 = 10 choices for the meal.

Top of Page
Permutations and Combinations

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)!
.
Here,
n! = 123...(n-1) n
is read "n factorial." A combination of n items taken r at a time is an unordered set of r items chosen from n. The number of combinations of n items taken r at a time is
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.
Examples
 P(7, 3) = 765 = 210
C(7, 3)= 76 5321
=35.

Since 5 and 2 add up to 7, we have

C(7, 5) = C(7, 2) == 7621
=21.

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

Top of Page

Last Updated: March, 2006