Operations on Sets

Try this

Shade only the common part of $A$ and $B$ (ignore $C$ ). What does the machine write? Now unshade the small piece of it that lies in $C$ . What does the formula become?
Shade the two regions “in $A$ but not in $B$ ”. Why does the machine use $∖$ instead of $\cap$ and a complement?
Shade every region outside $A \cup B$ , then tap “Complement” a few times. How are the two formulas related?
Into how many regions do the three circles cut $U$ ? Each region is either shaded or not.

Intersection, union, complement and difference are all defined element by element:

A \cap B A \cup B A ∖ B = {x ∣ x \in A and x \in B}, = {x ∣ x \in A or x \in B}, = {x ∣ x \in A and x \in / B}, ∁_{U} A = {x \in U ∣ x \in / A} .

The three logical words “and”, “or” and “not” are the whole secret. A Venn diagram draws exactly this: which region an element lands in depends only on whether it is in $A$ , whether it is in $B$ and whether it is in $C$ . Three yes/no answers give $2^{3} = 8$ possibilities.

Predict first

Three sets $A, B, C$ cut the universal set $U$ into $8$ regions. Using $A, B, C$ with intersection, union, difference and complement, how many different sets can you write?

8

16

256

Infinitely many

Choose an answer first; then you can see the result.

Why: De Morgan's laws

The standard way to prove that two sets are equal is to show that each contains the other, that is, to chase elements: take any element of the left side and show it is in the right side, and vice versa. On a Venn diagram this amounts to shading every region the same way.

Proof: ∁(A∪B) = ∁A ∩ ∁B

Step 1 / 6

The left side
First shade $A \cup B$ : the three regions inside the circles.

$A \cup B$
Take the complement
The first set on the right
The second set on the right
Intersect them
The other half

The commutative, associative, distributive and absorption laws can all be checked region by region in the same way. The “picture matcher” below draws the two sides next to each other. There are two distributive laws: which option is another way of writing $A \cup (B \cap C)$ ?

The red regions are where the two sides disagree. Put an element there and you have a counterexample.

Unlike the arithmetic of numbers, both distributive laws hold for sets: $\cap$ distributes over $\cup$ , and $\cup$ distributes over $\cap$ .

Remove one condition

Break it

Counterexample lab: remove one condition

Conclusion: The brackets can be moved freely

When every operation is $\cup$ (or every one is $\cap$ ), the associative law holds and it does not matter where the brackets go:

Practice

Exercise 1Basic

Let $U = {1, 2, \dots, 10}$ , let $A$ be the set of even numbers in $U$ , and let $B$ be the set of multiples of $3$ in $U$ . How many elements does $∁_{U} (A \cup B)$ have?

Exercise 2Basic

Given $A \cup B = {1, 2, \dots, 8}$ , $A \cap B = {3, 4}$ and $A ∖ B = {1, 2, 5}$ , find $B$ (list its elements separated by commas).

Exercise 3Advanced

How many ordered pairs of sets $(A, B)$ satisfy $A \cup B = {1, 2, 3, 4, 5}$ ? (When $A \neq = B$ , $(A, B)$ and $(B, A)$ count as two.)

Exercise 4Challenge

Let $X = {1, 2, 3, 4, 5, 6}$ . How many ordered triples $(A, B, C)$ satisfy $A \cup B \cup C = X$ and $A \cap B \cap C = \emptyset$ ?

Try this

Why: De Morgan's laws

Proof: ∁(A∪B) = ∁A ∩ ∁B

Remove one condition

Counterexample lab: remove one condition

Practice

Mistake Museum · Exhibits from this stop

Moving brackets around in a set difference

Taking the complement inside the brackets but not flipping the operation