Proving Set Identities

Element-chasing is the direct ancestor of the reasoning used in Boolean algebra and digital logic design, where the same identities (distributivity, De Morgan's laws) justify simplifying circuits, with $\cup,\cap,{}^c$ replaced by OR, AND, NOT gates acting on bits. In database theory, query optimizers rely on set-theoretic identities among relational operations (union, intersection, difference of tuples) to rewrite queries into equivalent but cheaper forms — correctness of every rewrite rule is, at bottom, an element-chasing proof. In topology, proofs that a space is Hausdorff, or that an intersection of closed sets is closed, routinely reduce to chasing a point through set-builder definitions of open and closed sets. In probability theory, identities among events (e.g. $P(A\setminus B) = P(A) - P(A\cap B)$) are typically first justified by exactly the set-theoretic identity for $A\setminus B$, proved by element-chasing, before probabilities are assigned. In formal verification and type theory (used in proof assistants such as Coq, Lean, and Agda), statements about sets or types are literally encoded as predicates, and "element-chasing" becomes the literal mechanized proof term: introduce a variable, destructure the hypothesis, construct the conclusion — the exact skeleton of the arguments given above. Finally, in cryptography, set-difference and intersection identities among key spaces or event sets in security proofs (e.g., bounding the probability that an adversary's guesses intersect a secret set) are verified with the same technique before any probability bound is computed.

Ask the tutor: Can you walk me through element-chasing both directions of $A \cup (B\cap C) = (A\cup B)\cap(A\cup C)$?

Think of membership in a set as a predicate — a statement that can be true or false of a given $x$. Then $x \in A \cup B$ is nothing but the disjunction "$x\in A$ or $x \in B$," and $x \in A \cap B$ is the conjunction "$x \in A$ and $x \in B$." Set operations are a picture-language for logical connectives. An identity like $A \setminus (B\cup C) = (A\setminus B)\cap(A \setminus C)$ is, underneath the notation, the logical equivalence

which is a fact about truth values that can be checked (in the finite propositional case) by a truth table, and which generalizes, via quantifiers, to arbitrary sets. Element-chasing is the bridge that lets you transport a fact about the logical connectives $\wedge,\vee,\neg$ into a fact about $\cap,\cup,\setminus$ — for every $A,B,C$, not just the ones you can draw. The Venn diagram below is not a proof, but it is exactly the right picture to guess the identity before chasing elements to confirm it holds in full generality (including cases the diagram cannot depict, such as $B, C$ overlapping in complicated infinite ways).

The diagram suggests the equality; the theorem below proves it holds for all sets, drawable or not.

This theorem licenses the two-inclusion strategy; the actual work in any specific identity is producing the proofs of (1) and (2), and that work is where the membership-unfolding rules from the definition come in. We now record, as a lemma, the precise unfolding rules used in every such proof — these are themselves immediate consequences of how $\cup,\cap,\setminus,{}^c$ are defined, so they require no further proof beyond restating the definitions.

Example 1 (an asymmetric identity: one distributive law with three distinct roles for $A,B,C$). Claim:

Proof. By Method of Element-Chasing it suffices to prove both inclusions. ($\subseteq$) Let $x$ be an arbitrary element with $x \in A \setminus (B \cup C)$. By the membership unfolding rule for $\setminus$,

So $x \in A$ and $\neg (x \in B \cup C)$. Unfolding $x \in B \cup C$ via the rule for $\cup$,

we get $\neg\big((x\in B) \vee (x \in C)\big)$. By De Morgan's law for propositions (a fact of propositional logic, not yet the set-theoretic De Morgan law we are foreshadowing — that one is proved using this technique, not assumed by it), this is logically equivalent to

i.e. $x \notin B$ and $x \notin C$. Combining with $x \in A$ (which we still have, unused so far in this branch), we get two facts:

(Here we use $x \in A$ twice: propositional logic permits reusing a conjunct, since $p \wedge \neg q \wedge \neg r$ entails both $p \wedge \neg q$ and $p \wedge \neg r$.) By the unfolding rule for $\setminus$ read in reverse, $x \in A \wedge x \notin B \iff x \in A \setminus B$, and similarly $x \in A \wedge x \notin C \iff x \in A \setminus C$. So $x \in A\setminus B$ and $x \in A \setminus C$; by the unfolding rule for $\cap$ (in reverse), $x \in (A\setminus B) \cap (A \setminus C)$. Since $x$ was arbitrary, $A \setminus (B\cup C) \subseteq (A\setminus B)\cap(A\setminus C)$. ($\supseteq$) Let $x$ be an arbitrary element with $x \in (A\setminus B)\cap(A\setminus C)$. Unfolding $\cap$: $x \in A\setminus B$ and $x \in A \setminus C$. Unfolding each $\setminus$: $(x \in A \wedge x \notin B)$ and $(x \in A \wedge x \notin C)$. In particular $x \in A$ (from either conjunct), and $x \notin B$, and $x \notin C$. So $\neg(x \in B)$ and $\neg (x\in C)$, which by propositional De Morgan gives $\neg\big((x \in B)\vee(x\in C)\big)$, i.e. $\neg(x \in B \cup C)$ by the $\cup$-rule. Combined with $x \in A$: $x \in A \wedge \neg(x \in B\cup C)$, i.e. $x \in A \setminus (B\cup C)$ by the $\setminus$-rule. Since $x$ was arbitrary, $(A\setminus B)\cap(A\setminus C) \subseteq A\setminus(B\cup C)$. Both inclusions hold, so by Method of Element-Chasing, $A\setminus(B\cup C) = (A\setminus B)\cap(A\setminus C)$. $\blacksquare$ Notice the identity used no special assumption about $A, B, C$ — not disjointness, not one containing another, not finiteness. That generality is exactly the point of the method: the proof only used the four unfolding rules and propositional logic.

Example 2 (an inclusion, not an equality, with unequal roles — illustrating that the two directions of the theorem's method genuinely can fail to be symmetric). Claim: for all sets $A, B, C$,

Proof. Let $x$ be an arbitrary element of $(A\cap B)\setminus C$. Unfolding $\setminus$: $x \in A \cap B$ and $x \notin C$. Unfolding $\cap$: $x \in A$ and $x \in B$. So we have three atomic facts:

We must show $x \in A \setminus (C \setminus B)$, i.e. by the $\setminus$-rule, that $x \in A$ and $x \notin (C \setminus B)$. The first conjunct, $x \in A$, is already in hand. For the second, unfold $x \in C \setminus B$: this means $x \in C \wedge x \notin B$. We must show the negation of this, i.e. $\neg(x \in C \wedge x \notin B)$, equivalently (propositional De Morgan again) $\neg(x\in C) \vee \neg(x \notin B) = (x \notin C) \vee (x \in B)$. We already know $x \notin C$ (one of our three atomic facts), so the disjunction $(x\notin C)\vee(x\in B)$ holds trivially (a disjunction holds whenever either disjunct does). Hence $\neg(x \in C\setminus B)$, i.e. $x \notin C\setminus B$. Combined with $x \in A$, we conclude $x \in A \setminus (C\setminus B)$. Since $x$ was an arbitrary element of $(A\cap B)\setminus C$, we have shown $(A\cap B)\setminus C \subseteq A\setminus(C\setminus B)$. $\blacksquare$ It is worth noting explicitly that the reverse inclusion is false in general: take $A = \{1,2\}$, $B = \{1\}$, $C = \{2\}$. Then $(A\cap B)\setminus C = \{1\}\setminus\{2\}=\{1\}$, while $C \setminus B = \{2\}\setminus\{1\} = \{2\}$, so $A\setminus(C\setminus B) = \{1,2\}\setminus\{2\} = \{1\}$ — equal here. Try instead $A=\{1,2,3\}$, $B=\{1\}$, $C=\{3\}$: then $(A\cap B)\setminus C = \{1\}\setminus\{3\}=\{1\}$, but $C\setminus B = \{3\}\setminus\{1\}=\{3\}$, so $A \setminus (C\setminus B) = \{1,2,3\}\setminus\{3\}=\{1,2\}$, which properly contains $\{1\}$ and is not a subset of it. This confirms the claim really is a one-directional inclusion, not a disguised equality — a fact one only discovers by attempting (and failing) to element-chase the reverse direction, which is itself part of the discipline of the method.