Set Identities & Element Proofs

⚗ Dr. Möbius, from the lab

A Venn diagram is a hypothesis, not a proof. Coloring two pictures the same shade tells you an identity is plausible — it does not tell you it's true, and the Federation of Boring Textbook Authors lets students confuse the two for their entire mathematical lives without ever feeling shame about it. I feel shame on their behalf. Today you learn the one move that converts a colorful guess into an ironclad theorem: element chasing. Roll up your sleeves. This is the good shit.

THE BIG IDEA

To prove two sets equal, prove each is a subset of the other by chasing an arbitrary element through the definitions.

The element-chasing method

We've defined $\subseteq$ , $\cup$ , $\cap$ , and complement entirely in terms of membership and logical connectives. Now we cash that in to prove things, using the direct-proof discipline from the Logic stratum. No more coloring. We're doing the real thing.

Recall the definition that does all the work: $A \subseteq B$ means $\forall x\,(x \in A \implies x \in B)$ . So to prove $A \subseteq B$ , you run a direct proof of that implication:

Take an arbitrary $x \in A$ . ("Let $x \in A$ ." Don't pick a specific one — pick a generic one, so the conclusion holds for all.)
Push it through the definitions. Unfold what $x \in A$ means, do honest logical steps, until you've shown $x$ satisfies the membership condition for $B$ .
Conclude $x \in B$ . Since $x$ was arbitrary, $\forall x\,(x \in A \implies x \in B)$ , i.e. $A \subseteq B$ .

That's element chasing: you chase one nameless element from the left set, through the logic, into the right set. Every set-inclusion proof in mathematics is this exact move.

Set equality is double inclusion — two proofs, always

How do you prove two sets are equal? Two sets are equal precisely when they have the same members, which means each contains the other:

$A = B \quad \iff \quad A \subseteq B \ \text{ and } \ B \subseteq A.$

So proving an equality is always two subset proofs. You prove $A \subseteq B$ (chase an element from $A$ into $B$ ), then you prove $B \subseteq A$ (chase an element from $B$ into $A$ ). Two directions, two arguments. Skip one and you've proven nothing — half an equality is a vibe, not a theorem, and I will hand it back to you with a red question mark and a sigh that echoes off the reactor walls. This double inclusion structure is the spine of the whole lesson.

Sometimes both directions chain together as a single "iff" computation (when every step is reversible). When you can honestly write $\iff$ at every line, the two inclusions collapse into one proof. But the safe default — and the one that never lies to you — is to do both directions explicitly.

De Morgan, proven in full — and why it's just logic

Here's the headliner, and I want you to treat it with the reverence it's owed. The first De Morgan law for sets says:

$(A \cup B)' = A' \cap B'.$

"The complement of a union is the intersection of the complements." Watch this get nailed down by double inclusion. Fix a universe $U$ .

Direction 1: $(A \cup B)' \subseteq A' \cap B'$ . Let $x \in (A \cup B)'$ . By definition of complement, $x \notin A \cup B$ . By definition of union, $x \in A \cup B$ would mean $x \in A \lor x \in B$ ; since that's false, we have $\neg(x \in A \lor x \in B)$ . By logical De Morgan (from the Logic stratum), this is $x \notin A \land x \notin B$ . So $x \in A'$ and $x \in B'$ , which means $x \in A' \cap B'$ . Done.

Direction 2: $A' \cap B' \subseteq (A \cup B)'$ . Let $x \in A' \cap B'$ . Then $x \in A'$ and $x \in B'$ , i.e. $x \notin A$ and $x \notin B$ . By logical De Morgan again, $\neg(x \in A \lor x \in B)$ , so $x \notin A \cup B$ , so $x \in (A \cup B)'$ . Done.

Both inclusions hold, therefore $(A \cup B)' = A' \cap B'$ . $\blacksquare$

Now stare at the load-bearing step in each direction: it was literally the logical De Morgan law applied to the membership statements. Set De Morgan IS logical De Morgan, channeled through $\in$ . The second law, $(A \cap B)' = A' \cup B'$ , proves identically — swap every $\land$ and $\lor$ . This is the dictionary from the last lesson doing all the heavy lifting: translate to logic, solve there, translate back. If this feels anticlimactic, good — it should. The whole damn point of building the dictionary was so that the hard work was already done.

The distributive laws

The other workhorse identities are the distributive laws, where $\cap$ distributes over $\cup$ and vice versa:

$A \cap (B \cup C) = (A \cap B) \cup (A \cap C),$ $A \cup (B \cap C) = (A \cup B) \cap (A \cup C).$

These are exactly the distributive laws of $\land$ over $\lor$ (and $\lor$ over $\land$ ) from logic, in bag costume. I swear to you, every single set identity you will ever meet is just a logical law wearing braces. Let me prove the first one's forward direction so you see the pattern, then you'll finish the rest in the gauntlet.

Claim: $A \cap (B \cup C) \subseteq (A \cap B) \cup (A \cap C)$ . Let $x \in A \cap (B \cup C)$ . Then $x \in A$ and $x \in B \cup C$ , so $x \in A \land (x \in B \lor x \in C)$ . By the distributive law of $\land$ over $\lor$ , this is $(x \in A \land x \in B) \lor (x \in A \land x \in C)$ , i.e. $x \in A \cap B$ or $x \in A \cap C$ , i.e. $x \in (A \cap B) \cup (A \cap C)$ . $\blacksquare$ (The reverse direction reverses every step — each line was an $\iff$ .)

The picture suggests; the proof confirms

Let me hammer the lesson's thesis one more time, because I genuinely cannot say it enough. A Venn diagram is a fantastic hypothesis generator — nothing more. Color the regions of $(A \cup B)'$ and of $A' \cap B'$ — they match, and that match is what tells you the identity is worth proving. Try it on the widget: highlight both expressions and confirm they shade the same regions.

venn lab — two sets

But a colored picture is not a QED. It can't handle infinitely many sets, it can't catch a subtle edge case, and it certainly can't be checked by a machine. The element proof can. The picture is a hypothesis; the element chase is the verdict. Carry that distinction into every proof you ever write — in this stratum and far beyond it. Draw the picture for intuition. Write the proof for truth. Never confuse the two, or you will lose arguments to people who are less creative and more careful than you, which should be unbearable.

🔬 SPECIMENS (worked examples)

Worked example 1 — a clean subset proof (no diagrams, no excuses)▸

Prove that $A \cap B \subseteq A$ for all sets $A, B$ .

We prove the inclusion by chasing an arbitrary element.

Proof. Let $x \in A \cap B$ . By definition of intersection, $x \in A \land x \in B$ . In particular, $x \in A$ (the first conjunct). Since $x$ was an arbitrary element of $A \cap B$ , every element of $A \cap B$ is in $A$ , so

$A \cap B \subseteq A. \qquad \blacksquare$

That's the entire move: unfold $\cap$ into an "and", then take the half you need. Notice we used only the definition of intersection and the trivial logical fact " $P \land Q \implies P$ ". No picture required — though the Venn diagram (the lens-shaped overlap sits inside $A$ 's circle) is exactly the hypothesis this proof confirms.

Worked example 2 — the second De Morgan law, by double inclusion▸

Prove $(A \cap B)' = A' \cup B'$ inside a universe $U$ .

Equality means double inclusion — two directions.

Direction 1: $(A \cap B)' \subseteq A' \cup B'$ . Let $x \in (A \cap B)'$ . Then $x \notin A \cap B$ , i.e. $\neg(x \in A \land x \in B)$ . By logical De Morgan, $\neg(x \in A) \lor \neg(x \in B)$ , that is $x \notin A \lor x \notin B$ . So $x \in A'$ or $x \in B'$ , hence $x \in A' \cup B'$ .

Direction 2: $A' \cup B' \subseteq (A \cap B)'$ . Let $x \in A' \cup B'$ . Then $x \in A'$ or $x \in B'$ , i.e. $x \notin A \lor x \notin B$ , which is $\neg(x \in A \land x \in B)$ . So $x \notin A \cap B$ , hence $x \in (A \cap B)'$ .

Both inclusions hold, so $(A \cap B)' = A' \cup B'$ . $\blacksquare$

Same engine as the first De Morgan law, with $\land$ and $\lor$ swapped throughout. The complement of an intersection is the union of complements — the connective flips.

Worked example 3 — the trap: a containment that is NOT equality (one wrong assumption, total wreckage)▸

A student claims $A \cup (B \cap C) = (A \cup B) \cap C$ . Find a counterexample, then state the correct identity and which single inclusion of the student's claim actually holds.

The student mangled the distributive law. Test with small sets. Take $A = \{1\}$ , $B = \emptyset$ , $C = \emptyset$ .

Left side: $A \cup (B \cap C) = \{1\} \cup (\emptyset \cap \emptyset) = \{1\} \cup \emptyset = \{1\}$ .
Right side: $(A \cup B) \cap C = (\{1\} \cup \emptyset) \cap \emptyset = \{1\} \cap \emptyset = \emptyset$ .

$\{1\} \ne \emptyset$ , so the claimed equality is false. One counterexample kills it dead.

The correct distributive law is $A \cup (B \cap C) = (A \cup B) \cap (A \cup C),$ with $A$ distributed across both factors — the student forgot to union $A$ into the second one.

As for which inclusion of the student's claim survives: chase it. If $x \in (A \cup B) \cap C$ , then $x \in C$ and $x \in A \cup B$ ; this does not force $x \in A \cup (B \cap C)$ (our counterexample's right side was empty, so there's nothing to check there). Going the other way, if $x \in A \cup (B \cap C)$ then $x \in A$ or $x \in B \cap C$ ; the $x \in A$ branch need not land in $C$ , so that fails too. Neither inclusion holds in general — the student's identity is broken in both directions, which is exactly why the counterexample was so easy to find. Moral: never trust a distributive law you didn't distribute across everything.

☠ KNOWN HAZARDS

Proving only one inclusion. $A \subseteq B$ does not give $A = B$ . Equality demands both directions. Half an equality proves nothing — it proves you got tired, which is not a proof technique.
"Proving" by Venn diagram. Coloring matching regions is evidence, not proof — it can't handle infinite families or be machine-checked. Always back the picture with an element chase. I cannot stress this enough. The diagram is a sketch, not an argument.
Picking a specific element. "Let $x = 3 \in A$ " proves nothing general. Take an arbitrary $x \in A$ so the conclusion holds for all of them. A specific example is not a proof; it is one data point.
Botching De Morgan's flip. The complement of a union is the intersection of complements: $(A \cup B)' = A' \cap B'$ , not $A' \cup B'$ . The connective flips — $\cup$ becomes $\cap$ . This is the most popular wrong answer I see, and it is baffling given that the logical version was covered two strata ago.

TL;DR

▸
To prove $A \subseteq B$ : take an arbitrary $x \in A$ , push it through the definitions, conclude $x \in B$ . That's element chasing.
▸
$A = B \iff A \subseteq B \text{ and } B \subseteq A$ . Proving an equality is always two subset proofs (double inclusion).
▸
De Morgan for sets: $(A \cup B)' = A' \cap B'$ and $(A \cap B)' = A' \cup B'$ — proven by element chasing, and identical to logical De Morgan.
▸
Distributive laws: $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ and dually — these are $\land/\lor$ distribution in bag costume.
▸
A Venn diagram is a hypothesis; an element proof is the verdict. A picture suggests, the proof confirms.

unlocks

Vector Spaces →