Visual Tools
Calculators
Tables
Mathematical Keyboard
Converters
Other Tools

How to Prove a Set Identity

Two sets are equal when each is a subset of the other. To prove an identity, take an arbitrary element of the left side and show it lies in the right side, then do the same in reverse.

Recognize the task

The task says prove, show or verify that two set expressions are equal: A∖(B∪C)=(A∖B)∩(A∖C)A \setminus (B \cup C) = (A \setminus B) \cap (A \setminus C), (A∪B)c=Ac∩Bc(A \cup B)^c = A^c \cap B^c, A∖(A∖B)=A∩BA \setminus (A \setminus B) = A \cap B. Test: the claim is meant to hold for all sets AA, BB, CC, so one example is not enough; you need an argument for an arbitrary element.
Equal sets and the two-inclusion test are covered in the equal sets lesson.

Ways to do it

Two inclusionsusual
A=B  ⟺  A⊆B and B⊆AA = B \iff A \subseteq B \text{ and } B \subseteq A
The set equality criterion: follow an arbitrary element through both sides.
Laws of set algebraalgebra
(A∪B)c=Ac∩Bc(A \cup B)^c = A^c \cap B^c
Rewrite one side into the other with named laws such as De Morgan's law and the distributive laws.
Membership tabletable
2n rows for n sets2^n \text{ rows for } n \text{ sets}
List every in or out pattern of the sets, one row per Venn region, and check that both sides agree in every row.

Steps

StepOn A∖(B∪C)=(A∖B)∩(A∖C)A \setminus (B \cup C) = (A \setminus B) \cap (A \setminus C)
1Translate each side into membership conditions. Use the definition of each operation, one at a time.left: x∈Ax \in A, x∉B∪Cx \notin B \cup C; right: x∈A∖Bx \in A \setminus B, x∈A∖Cx \in A \setminus C
2Show that the left side is a subset of the right side. Take any xx on the left. x∉B∪Cx \notin B \cup C means x∉Bx \notin B and x∉Cx \notin C, so x∈A∖Bx \in A \setminus B and x∈A∖Cx \in A \setminus C.A∖(B∪C)⊆(A∖B)∩(A∖C)A \setminus (B \cup C) \subseteq (A \setminus B) \cap (A \setminus C)
3Show that the right side is a subset of the left side. Take any xx on the right. Then x∈Ax \in A, x∉Bx \notin B and x∉Cx \notin C, so xx is in neither BB nor CC: x∉B∪Cx \notin B \cup C.(A∖B)∩(A∖C)⊆A∖(B∪C)(A \setminus B) \cap (A \setminus C) \subseteq A \setminus (B \cup C)
4Conclude that the sets are equal. Two inclusions give equality. Before writing a proof, test the claim on small sets: a single failure disproves it.the identity holds

Worked examples

Example 1 · with set laws

algebra
(A∩B)∪(A∩Bc)(A \cap B) \cup (A \cap B^c)
start from the longer side
=A∩(B∪Bc)= A \cap (B \cup B^c)
distributive law, read backward
=A∩U= A \cap U
complement law
=A= A
identity law

Example 2 · with a membership table

table
claim: A∖(A∖B)=A∩BA \setminus (A \setminus B) = A \cap B; rows (x∈Ax \in A, x∈Bx \in B): 1111, 1010, 0101, 0000
one row per region
left side: 11, 00, 00, 00
in AA but not in A∖BA \setminus B
right side: 11, 00, 00, 00
in both AA and BB
the columns agree in all 44 rows
so the sets are equal

Example 3 · with two inclusions

elements
claim: A∖(B∩C)=(A∖B)∪(A∖C)A \setminus (B \cap C) = (A \setminus B) \cup (A \setminus C)
take xx on the left
x∈Ax \in A and x∉B∩Cx \notin B \cap C
definition of difference
x∈Ax \in A and (x∉Bx \notin B or x∉Cx \notin C)
not in both means missing one
x∈A∖Bx \in A \setminus B or x∈A∖Cx \in A \setminus C; every step reverses
both inclusions hold, so equal
Compare both sides region by region in the two-set laws Venn tool or the three-set laws Venn tool, or build the rows in the Venn truth table tool.

See it happen

With nn sets, every element has one of 2n2^n in or out patterns, and each pattern is one region of the Venn diagram. A set expression is a choice of regions. Two expressions are equal exactly when they choose the same regions: a membership table checks this row by row, and an element argument proves it without drawing. A Venn sketch shows why an identity is true, but it is a check, not a proof.

Common mistakes

Taking one example as a proof

✗ it works for A={1,2}A = \{1, 2\}, B={2}B = \{2\}, so it is true
✓ an example can only disprove; prove it for an arbitrary element xx

Proving only one inclusion

✗ left ⊆\subseteq right, so left == right
✓ also show right ⊆\subseteq left

Moving a complement without switching the operation

✗ (A∩B)c=Ac∩Bc(A \cap B)^c = A^c \cap B^c
✓ (A∩B)c=Ac∪Bc(A \cap B)^c = A^c \cup B^c
With U={1,2,3,4}U = \{1, 2, 3, 4\}, A={1,2}A = \{1, 2\}, B={2,3}B = \{2, 3\} the left side is {1,3,4}\{1, 3, 4\} but Ac∩Bc={4}A^c \cap B^c = \{4\}.

Reordering a difference

✗ A∖B=B∖AA \setminus B = B \setminus A
✓ with A={1,2,3}A = \{1, 2, 3\}, B={3,4}B = \{3, 4\}: {1,2}≠{4}\{1, 2\} \neq \{4\}