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 empty 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 outcomes, we can think of the possible outcomes as being the elements of a set of outcomes associated with that experiment. (There is further discussion of sets of outcomes in the topic summary on probability.)

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

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

4. 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 representing B A to also represent B 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

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

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

In other words, if S is the set of outcomes of tossing a coin once, then S×S is the set of outcomes of tossing a coin twice (or flipping a pair of distinguishable coins once).

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 S×S is the set of outcomes of rolling a die twice (or rolling a pair of distinguishable dice once).

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

which we might also write as

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

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(A×B) = n(A)^.n(B)

Top of Page

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 Algorithm 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 Algorithm 2 (Valid)
Pretend you were constructing such a string by assigning groups of slots to the four different letters, 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 algorithm 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 Algorithm 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

If a decision algorithm 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 Algorithm

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! = 1×2×3×...×(n-1)× n

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) ×...×2×1	.

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)

=

7×6×5

=

210.

C(7, 3)

=

7×6 ×5 3×2×1

=

35.

Since 5 and 2 add up to 7, we have

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

7×6 2×1

=

21.

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

Try the Pop-up Factorials, Permutations and Combinations Window for more examples.