Elements of set theory: operations, De Morgan and difference

In one sentence

Rewrite every set difference as $A \setminus B = A \cap B^{c}$, and the whole subject collapses into Boolean algebra where De Morgan does the rest.

Why the exam asks it

Because it is a free minute at the start of Part B for anyone who knows the rewrite, and a two-minute case analysis for anyone who does not. The identities look interchangeable on the page, so the question is really testing whether you can compute rather than recognise.

The idea

One move does almost all of the work:

$A \setminus B \;=\; A \cap B^{c}.$

Difference is not a third operation to memorise rules for. It is intersection with a complement, and once written that way every question becomes union, intersection and complement — where the laws are the ones you already trust.

De Morgan, the only law you need to hold

$(A \cup B)^{c} = A^{c} \cap B^{c}, \qquad (A \cap B)^{c} = A^{c} \cup B^{c}.$

Complementation swaps union and intersection. Everything else follows.

The worked case the papers keep setting

$A \setminus (B \setminus C)$. Apply the rewrite twice and push the complement inwards:

$A \setminus (B \setminus C) = A \cap (B \cap C^{c})^{c} = A \cap (B^{c} \cup C) = (A \cap B^{c}) \cup (A \cap C) = (A \setminus B) \cup (A \cap C).$

Four rewrites, no diagram. The last step is distributivity of $\cap$ over $\cup$.

Read it in words: something survives $A \setminus (B \setminus C)$ if it is in $A$ and not in the part of $B$ outside $C$. So either it misses $B$ altogether, or it is in $C$, where $B \setminus C$ cannot reach it.

Where intuition breaks

Difference is not associative. $(A \setminus B) \setminus C \ne A \setminus (B \setminus C)$ in general. Take $A = C = \{1\}$ and $B = \varnothing$. The left side is $(\{1\} \setminus \varnothing) \setminus \{1\} = \varnothing$; the right is $\{1\} \setminus (\varnothing \setminus \{1\}) = \{1\}$. The brackets are not decoration, and an option that has silently moved them is the standard wrong answer.

Difference is not commutative either, which is obvious stated plainly and easy to lose inside a longer expression.

$A \setminus (B \setminus C)$ is not $(A \setminus B) \cup C$. The $C$ term has to be cut down to $A \cap C$ first. An option offering the uncut $C$ is testing exactly this.

Symmetric difference is associative, unlike ordinary difference — $A \triangle B = (A \setminus B) \cup (B \setminus A)$ behaves like addition mod 2 on indicator functions, so brackets genuinely do not matter there. Knowing which of the two is associative is worth a mark on its own.

The exam's angle

Two methods, and use whichever is faster for the shape in front of you:

1. Rewrite and push complements. Best when the expression is short and the options are algebraic. Three lines, as above.

2. Test a small example. Best when the options are concrete or the expression is nested. Take $A = \{1,2\}$, $B = \{2,3\}$, $C = \{1,3\}$. One element sits in each pairwise overlap and nowhere else, so it is quick to evaluate and it kills almost every wrong option.

   It has a blind spot. Here $A \cap B \cap C$ is empty, and so is the part of each set outside the other two. An option that goes wrong only on the triple overlap therefore survives. When two still stand, switch to $A = \{1,4,5,7\}$, $B = \{2,4,6,7\}$, $C = \{3,5,6,7\}$. That fills all seven regions, and $8$ stays outside for complements.

   One counterexample kills an option outright — you never need to prove the survivor, only eliminate the rest.

Method 2 is underrated under time pressure. An identity that fails on a three-element example is finished, and checking costs seconds.

The night before

• $A \setminus B = A \cap B^{c}$. Always start here.
• De Morgan swaps $\cup$ and $\cap$ under complement.
• $A \setminus (B \setminus C) = (A \setminus B) \cup (A \cap C)$ — note the $A \cap$.
• $\setminus$ is neither associative nor commutative; $\triangle$ is associative.
• To disprove an identity, one small example is enough — provided the region the options disagree on is actually occupied in it.

In plain English

Think of a set difference as a filter with two conditions at once. "In $A$ but not in $B$" means "in $A$" and "outside $B$". That is the whole content of $A \setminus B = A \cap B^{c}$.

Once every minus sign is rewritten that way, only three operations are left: and, or, not. De Morgan is the rule for pushing a "not" through, and it swaps and with or.

Brackets are not decoration. Taking away "the part of $B$ outside $C$" is a different instruction from taking away $B$ and then adding $C$ back.

Where this shows up

Every database query is this algebra. WHERE active AND NOT banned is $A \cap B^{c}$, and SQL's EXCEPT is set difference outright. Query planners rewrite it into an anti-join using exactly the identity above.

Search filters on a shopping site do the same work: brand, price band, in stock, not discontinued.

Digital circuits are the same algebra under different names. AND, OR and NOT gates obey these laws, and De Morgan is what lets a chip designer build every circuit out of one kind of gate.