Sets

Collections, membership, subsets, unions, intersections, and products.

A set is a collection of distinct objects. Sets are used in probability, databases, logic, graph theory, and almost every area of mathematics.

Learning objectives

After this lesson you should be able to:

use membership notation;
distinguish elements from subsets;
compute unions, intersections, differences, and complements;
list a small power set;
compute a Cartesian product;
connect set operations to Venn diagrams and probability events.

What is a set?

A set is a collection where order and repetition do not matter.

{1, 2, 3} = {3, 2, 1} = {1, 1, 2, 3}

The objects in a set are called elements.

2 in {1,2,3} is true.
5 in {1,2,3} is false.

Elements and subsets

The statement x in A means x is an element of A. The statement A subset B means every element of A is also in B.

Element versus subset

If A = {1,2,3}, then 2 in A is true and {2} subset A is also true. But 2 and {2} are different objects.

Set operations

Let A={1,2,3} and B={3,4}.

Operation	Meaning	Result
`A union B`	in A or B or both	`{1,2,3,4}`
`A intersection B`	in both A and B	`{3}`
`A - B`	in A but not B	`{1,2}`
`B - A`	in B but not A	`{4}`
`A symmetric_difference B`	in exactly one set	`{1,2,4}`

Complements

A complement depends on a universe. If the universe is U={1,2,3,4,5} and A={1,2,3}, then

A complement = {4,5}

Without a universe, the complement is not well defined.

Power sets

The power set of A is the set of all subsets of A.

For A={a,b}, the power set is

{ {}, {a}, {b}, {a,b} }

A set with n elements has 2^n subsets.

Cartesian products

The Cartesian product A x B is the set of ordered pairs whose first coordinate comes from A and second coordinate comes from B.

If A={1,2} and B={x,y}, then

A x B = {(1,x), (1,y), (2,x), (2,y)}

Order matters: usually A x B is not the same as B x A.

Worked example 1: Venn regions

Let A={1,2,3}, B={3,4,5}, and universe U={1,2,3,4,5,6}.

only in A: {1,2};
only in B: {4,5};
in both: {3};
in neither: {6}.

Worked example 2: event language

In probability, events are sets. If A is “roll an even number” and B is “roll a number greater than 4” on a six-sided die, then

A = {2,4,6}
B = {5,6}
A intersection B = {6}

The intersection means both events happen.

Common pitfalls

Forgetting that sets ignore repeated elements.
Confusing in with subset.
Thinking A - B equals B - A.
Computing a complement without knowing the universe.
Treating ordered pairs as unordered sets.

Practice

Compute {1,2,3} union {3,4}.
Compute {1,2,3} intersection {3,4}.
Is {2,3} a subset of {1,2,3,4}?
List the power set of {x,y}.
Compute {1,2} x {a}.

Solutions

{1,2,3,4}.
{3}.
Yes, because both 2 and 3 are in the larger set.
{ {}, {x}, {y}, {x,y} }.
{(1,a), (2,a)}.

Subtopic guided practice and checkpoints

Set problems become easier when you decide membership one element at a time.

Lab 1: element or subset?

Guess first. If A = {1, 2, 3}, which statement is correct: 2 in A or {2} in A?

Guided exercise.

2 in A is true because 2 is an element of A. The set {2} is not listed as an element of A, so {2} in A is false. However, {2} subset A is true because every element of {2} is in A.

Checkpoint. For B = {a, {b}, c}, decide whether b in B, {b} in B, and {b} subset B are true. Say which question is about membership and which is about subsets.

Lab 2: compute operations by asking membership questions

Guess first. For A = {1, 2, 3} and B = {3, 4, 5}, which elements are in both sets?

Guided exercise.

Check each possible element:

1 is in A only
2 is in A only
3 is in both A and B
4 is in B only
5 is in B only

Therefore:

A union B        = {1, 2, 3, 4, 5}
A intersection B = {3}
A - B            = {1, 2}
B - A            = {4, 5}

Checkpoint. Let A = {red, blue, green} and B = {green, yellow}. Compute A union B, A intersection B, and A - B.

Lab 3: use complements only after naming the universe

Guess first. Can you find A complement if no universe is given?

Guided exercise.

Let U = {1, 2, 3, 4, 5, 6} and A = {2, 4, 6}. The complement of A is everything in U that is not in A:

A complement = {1, 3, 5}

If the universe changed to all positive integers, the complement would be much larger. That is why the universe must be declared.

Checkpoint. If U = {a, b, c, d, e} and C = {b, d}, find C complement. Then explain why the answer would change if the universe changed.

Lab 4: list power sets and Cartesian products systematically

Guess first. How many subsets should a two-element set have?

Guided exercise.

For A = {x, y}, each element has two choices: include it or leave it out. That gives four subsets:

{}        choose neither
{x}       choose x only
{y}       choose y only
{x, y}    choose both

For A = {1, 2} and B = {a, b}:

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

Checkpoint. List the power set of {p, q} and the Cartesian product {0, 1} x {L, R}.

Lab checkpoint answers

For B = {a, {b}, c}, b in B is false, {b} in B is true, and {b} subset B is false because the element b itself is not in B.
A union B = {red, blue, green, yellow}, A intersection B = {green}, and A - B = {red, blue}.
C complement = {a, c, e} relative to U = {a, b, c, d, e}.
The power set of {p, q} is { {}, {p}, {q}, {p, q} }. The Cartesian product is {(0, L), (0, R), (1, L), (1, R)}.

Sets checkpoint

Using this lesson with edumath and SymPy

Python has built-in set operators.

A = {1, 2, 3}
B = {3, 4}
A | B, A & B, A - B, A ^ B

({1, 2, 3, 4}, {3}, {1, 2}, {1, 2, 4})

Use edumath for a named table of operations.

from edumath.discrete_math import cartesian_product, power_set, set_operation_table

set_operation_table(A, B)

{'union': {1, 2, 3, 4},
 'intersection': {3},
 'a_minus_b': {1, 2},
 'b_minus_a': {4},
 'symmetric_difference': {1, 2, 4}}

power_set({"a", "b"}), cartesian_product({1, 2}, {"x", "y"})

((frozenset(), frozenset({'a'}), frozenset({'b'}), frozenset({'a', 'b'})),
 ((1, 'y'), (1, 'x'), (2, 'y'), (2, 'x')))

SymPy also has finite-set objects.

import sympy as sp

sp.FiniteSet(1, 2, 3).union(sp.FiniteSet(3, 4))

\(\displaystyle \left\{1, 2, 3, 4\right\}\)