Lecture 2. Set algebra #

Overview #

Lecture 1 introduced what a set is: an unordered collection of distinct objects, compared by the subset relation and measured by cardinality. This lecture is about what we do with sets — how to combine and transform them, and, crucially, which algebraic laws these operations obey.

The payoff is twofold. First, we obtain a small toolkit of operations (union, intersection, difference, symmetric difference, complement) that let us build new sets from old ones. Second — and this is the heart of the chapter — these operations satisfy a fixed collection of identities that make set expressions manipulable symbolically, exactly the way $a(b+c) = ab + ac$ lets us manipulate numbers. The resulting system, the subsets of a fixed universe $U$ under $\cup$, $\cap$, and $\overline{\phantom{A}}$ together with the constants $\varnothing$ and $U$, is called the algebra of sets. In Lectures 4–5 we will recognise it as one concrete instance of a Boolean algebra; here we develop it directly and, above all, prove its laws.

Why insist on proofs? Because a picture (a Venn diagram) convinces us for two or three sets but proves nothing for arbitrary sets, and because the same reasoning patterns — membership tables, double inclusion, and characteristic functions — recur throughout discrete mathematics and directly mirror how a computer manipulates sets as machine words. Every law in this chapter is stated precisely and proved by at least one of these methods, usually more than one, so that you see the techniques as well as the results.

Roadmap: §2.1 recalls the prerequisites; §§2.2–2.4 define the operations and their pictures; §2.5 treats disjointness and partitions; §2.6 introduces characteristic functions, the workhorse for the rest of the chapter; §§2.7–2.9 state the laws, prove them by two independent methods, and derive the duality principle; §2.10 develops symmetric difference; §2.11 studies the Cartesian product (the bridge to relations in Lecture 3); §2.12 generalises union and intersection to arbitrary families; §2.13 states and proves the inclusion–exclusion principle for two and three sets; and §2.14 cashes everything out in three applications — bit-vector set operations, inclusion–exclusion counting, and the set operators of SQL.

2.1 Prerequisites from Lecture 1 #

We assume the following from Lecture 1 and recall them only briefly; each is used constantly below.

• Membership — $x \in A$ means “$x$ is an element of $A$”; $x \notin A$ is its negation. A set is completely determined by its members.
• Set-builder notation — $\{\,x : P(x)\,\}$ is the set of all $x$ satisfying the property $P$. A domain may be attached: $\{\,x \in U : P(x)\,\}$.
• Subset — $A \subseteq B$ means every element of $A$ is also in $B$: $A \subseteq B \iff (\forall x)(x \in A \Rightarrow x \in B)$.
• Set equality by double inclusion — $A = B$ iff $A \subseteq B$ and $B \subseteq A$. This antisymmetry criterion is our primary proof tool for set identities; see §2.8.
• Empty set — $\varnothing$, the unique set with no elements; $\varnothing \subseteq A$ for every $A$ (vacuously).
• Cardinality — $|A|$ is the number of elements of a finite set $A$; $|\varnothing| = 0$.
• Power set — $\mathcal{P}(A)$ is the set of all subsets of $A$, with $|\mathcal{P}(A)| = 2^{|A|}$.
• Ordered pairs — $(a,b) = (c,d)$ iff $a=c$ and $b=d$; order matters, so $(1,2)\ne(2,1)$ although $\{1,2\}=\{2,1\}$.

Throughout this lecture, whenever complements appear we fix a universal set $U$: the set of all objects currently under consideration. Every set we complement is understood to be a subset of $U$, and every “element” $x$ in a proof ranges over $U$.

Notational conventions used below. We write $A, B, C$ for arbitrary subsets of $U$. The logical connectives are $\lor$ (“or”, inclusive), $\land$ (“and”), $\lnot$ (“not”); these govern the set operations because “$x \in A \cup B$” is defined by “$x \in A \lor x \in B$”, and so on. Many set laws are therefore shadows of laws of propositional logic — a theme we make explicit in §2.8.

2.2 The four basic operations #

We now define the operations that combine or transform sets. In each case the definition is a set-builder expression whose defining property is a logical combination of membership statements. Read each definition twice: once as English, once as the logical predicate that makes it precise.

Union #

Motivation. To pool two collections into one — the customers who bought product $A$ or product $B$, the integers divisible by $2$ or by $3$ — we want every element that appears in at least one of them.

Definition (union). The union of $A$ and $B$ is

$$A \cup B = \{\,x : x \in A \ \lor\ x \in B\,\}.$$

The “or” is inclusive: an element lying in both sets is included, and — because a set has no duplicates — it is listed only once.

Example 2.1. Let $A = \{1,2,3,4\}$ and $B = \{3,4,5,6\}$. Then $A \cup B = \{1,2,3,4,5,6\}$. The shared elements $3,4$ appear once.

Intersection #

Motivation. To find what two collections have in common — the customers who bought both products, the integers divisible by $2$ and by $3$ (i.e. by $6$).

Definition (intersection). The intersection of $A$ and $B$ is

$$A \cap B = \{\,x : x \in A \ \land\ x \in B\,\}.$$

Example 2.2. With the same $A, B$ as above, $A \cap B = \{3,4\}$.

Two order-of-magnitude sanity checks that hold for all $A,B$:

$$A \cap B \ \subseteq\ A \ \subseteq\ A \cup B,$$

and if $A \subseteq B$ then $A \cup B = B$ and $A \cap B = A$ (an element already in $B$ adds nothing new to the union, and every element of $A$ survives the intersection). The containment chain $A\cap B\subseteq A\subseteq A\cup B$ is a one-line element-chase; the $A\subseteq B$ equivalences are Exercise S4. Both are used silently all the time.

Difference #

Motivation. To remove one collection from another — everyone in $A$ who is not also in $B$.

Definition (relative difference). The difference $A \setminus B$ (read “$A$ minus $B$”) is what remains of $A$ after deleting everything that also lies in $B$:

$$A \setminus B = \{\,x : x \in A \ \land\ x \notin B\,\}.$$

It is not symmetric: in general $A \setminus B \ne B \setminus A$.

Example 2.3. With $A = \{1,2,3,4\}$, $B = \{3,4,5,6\}$:

$$A \setminus B = \{1,2\}, \qquad B \setminus A = \{5,6\}.$$

$A \setminus B$ keeps the part of $A$ outside $B$; $B \setminus A$ keeps the part of $B$ outside $A$. They are different sets — indeed disjoint here.

Complement #

Motivation. Often we want “everything except $A$” — the outcomes of a die that are not a six, the users who did not click. “Everything” must be pinned down, hence the universal set.

Definition (complement). Relative to a fixed universe $U$ with $A \subseteq U$, the complement of $A$ is everything in $U$ not in $A$:

$$\overline{A} = U \setminus A = \{\,x \in U : x \notin A\,\}.$$

The complement is meaningful only relative to a chosen $U$; changing $U$ changes $\overline{A}$.

Example 2.4. Take $U = \{1,2,3,4,5,6,7,8\}$ with $A = \{1,2,3,4\}$ and $B = \{3,4,5,6\}$. Then

$$\overline{A} = \{5,6,7,8\}, \qquad \overline{B} = \{1,2,7,8\}.$$

Remark (difference vs. complement). Difference is relative and needs no universe: $A \setminus B$ makes sense for any $A,B$. Complement is difference from the fixed universe: $\overline{A} = U \setminus A$. Conversely, difference reduces to complement plus intersection: $A \setminus B = A \cap \overline{B}$ (proved in §2.8). Keeping “relative to what?” in mind avoids many errors.

Common pitfall. $\overline{A}$ has no absolute meaning. If a problem speaks of complements without naming $U$, either $U$ is implicit from context (e.g. $U = \mathbb{Z}$) or the problem is ill-posed. Always identify $U$ first.

Two identities tie complements to the constants (proved in §2.8):

$$A \cup \overline{A} = U \quad(\text{a set and its complement fill the universe}), \qquad A \cap \overline{A} = \varnothing \quad(\text{they share nothing}).$$

2.3 Venn diagrams #

A Venn diagram represents sets as regions — usually circles — inside a rectangle that stands for the universal set $U$. Overlaps show shared elements; shading marks the region an expression denotes. To read an expression off a diagram, shade the part matching its defining predicate: for $A \cup B$ shade both circles entirely; for $A \cap B$ shade only the lens-shaped overlap; for $A \setminus B$ shade the crescent of $A$ outside $B$; for $\overline{A}$ shade everything outside circle $A$.

The relative position of two circles encodes the relationship between the sets:

Remark (a picture is not a proof). With three general circles a Venn diagram has $2^3 = 8$ regions (including the outside), one for every combination of “in/out of $A$, $B$, $C$”, and it faithfully depicts all cases. But for four or more sets three circles cannot show all $2^4 = 16$ combinations without distortion, and no finite picture can address arbitrary sets. Diagrams suggest identities and help us understand them; they do not prove them. Proof is the business of §2.8.

2.4 Symmetric difference #

Motivation. The union collects “in $A$ or $B$ (or both)”; sometimes we want the exclusive version: “in exactly one of $A$, $B$”. This is the set of elements on which $A$ and $B$ disagree — the natural notion of “difference between two sets” and, as we will see, the set analogue of the logical XOR and of binary addition.

Definition (symmetric difference). The symmetric difference $A \triangle B$ collects the elements that lie in exactly one of the two sets:

$$A \triangle B = (A \setminus B) \cup (B \setminus A).$$

Example 2.5. With $A = \{1,2,3,4\}$, $B = \{3,4,5,6\}$:

$$A \triangle B = \{1,2\} \cup \{5,6\} = \{1,2,5,6\}.$$

These are exactly the elements $A$ and $B$ disagree on; the agreed-upon $3,4$ drop out.

The definition has a second, equally useful form.

Proposition 2.6. $\ A \triangle B = (A \cup B) \setminus (A \cap B).$

Proof. We show the two descriptions denote the same set by rewriting one into the other using difference-as-intersection-with-complement ($X \setminus Y = X \cap \overline{Y}$, §2.8) and the laws of §2.7. Starting from the right-hand side and using De Morgan and distributivity:

$$(A \cup B) \setminus (A \cap B) = (A \cup B) \cap \overline{A \cap B} = (A \cup B) \cap (\overline{A} \cup \overline{B}).$$

Distribute the right factor over $A \cup B$:

$$= \big[(A \cup B) \cap \overline{A}\big] \cup \big[(A \cup B) \cap \overline{B}\big].$$

Distribute again inside each bracket:

$$= \big[(A \cap \overline{A}) \cup (B \cap \overline{A})\big] \cup \big[(A \cap \overline{B}) \cup (B \cap \overline{B})\big].$$

Now $A \cap \overline{A} = \varnothing$ and $B \cap \overline{B} = \varnothing$, and $\varnothing$ is the identity for $\cup$, so the expression collapses to

$$= (B \cap \overline{A}) \cup (A \cap \overline{B}) = (A \setminus B) \cup (B \setminus A) = A \triangle B,$$

using $X \cap \overline{Y} = X \setminus Y$ and commutativity of $\cup$. $\blacksquare$

Example 2.7. Rechecking Example 2.5 by the second form: $A \cup B = \{1,2,3,4,5,6\}$, $A \cap B = \{3,4\}$, so $(A \cup B) \setminus (A \cap B) = \{1,2,5,6\}$ — the same set.

Unlike ordinary difference, symmetric difference is symmetric, and it enjoys a rich algebra developed fully in §2.10:

$$A \triangle B = B \triangle A, \qquad A \triangle \varnothing = A, \qquad A \triangle A = \varnothing, \qquad A \triangle U = \overline{A}.$$

Because every set is its own inverse ($A\triangle A=\varnothing$), symmetric difference obeys a cancellation law: $A\triangle B = A\triangle C \implies B = C$ (take the symmetric difference of both sides with $A$).

2.5 Disjoint sets and partitions #

Definition (disjoint). Two sets are disjoint if they have no element in common: $A \cap B = \varnothing$.

Example 2.8. $\{1,2,3\}$ and $\{4,5,6\}$ are disjoint; their circles do not overlap. $\{1,2,3\}$ and $\{3,4,5\}$ are not disjoint (they share $3$). Note that $A \setminus B$ and $B \setminus A$ are always disjoint, and both are disjoint from $A \cap B$ — this three-way split is the key to counting (§2.13).

Definition (pairwise disjoint). A family of sets $A_1, A_2, \dots, A_n$ is pairwise disjoint if $A_i \cap A_j = \varnothing$ whenever $i \ne j$.

Disjointness is what makes counting additive: if $A$ and $B$ are disjoint then $|A \cup B| = |A| + |B|$ with no correction term (the general case is inclusion– exclusion, §2.13).

Definition (partition). A partition of a set $S$ is a family of nonempty, pairwise-disjoint subsets whose union is all of $S$. Intuitively, a partition slices $S$ into non-overlapping “blocks” that together account for every element exactly once.

Example 2.9. $\{\{1,2\},\{3\},\{4,5,6\}\}$ is a partition of $\{1,2,3,4,5,6\}$. For any $A \subseteq U$, the pair $\{A, \overline{A}\}$ partitions $U$ (assuming both are nonempty). For any two sets, $\{A \setminus B,\ A \cap B,\ B \setminus A\}$ partitions $A \cup B$ (dropping any empty blocks).

Cross-reference. Partitions are exactly the “quotient” structure produced by an equivalence relation (Lecture 3): each block is an equivalence class. Keep the word in mind; it returns with force there.

2.6 Characteristic functions: the workhorse #

Before stating the laws we introduce a device that (i) makes every proof by “membership table” completely rigorous, (ii) reduces set identities to ordinary arithmetic, and (iii) is literally how a computer stores a set. It will pay for itself many times over.

Definition (characteristic function). Fix a universe $U$. The characteristic function (or indicator) of a set $A \subseteq U$ is the function $\chi_A : U \to \{0,1\}$ given by

$$\chi_A(x) = \begin{cases} 1 & \text{if } x \in A,\\ 0 & \text{if } x \notin A.\end{cases}$$

A set and its indicator carry exactly the same information, so two sets are equal iff their indicators agree everywhere:

Lemma 2.10 (equality criterion). $A = B \iff \chi_A(x) = \chi_B(x)$ for all $x \in U$. Likewise $A \subseteq B \iff \chi_A(x) \le \chi_B(x)$ for all $x$.

Proof. $A = B$ means $x \in A \Leftrightarrow x \in B$ for all $x$, i.e. $\chi_A(x)$ and $\chi_B(x)$ are both $1$ or both $0$ — that is, equal — for every $x$. For the subset statement, $A \subseteq B$ means $x\in A \Rightarrow x\in B$, i.e. $\chi_A(x)=1 \Rightarrow \chi_B(x)=1$; since the values are in $\{0,1\}$ this is exactly $\chi_A(x) \le \chi_B(x)$. $\blacksquare$

The operations translate into arithmetic on indicators. Here $x$ is an arbitrary element of $U$, and all products/sums are ordinary integer arithmetic.

Lemma 2.11 (arithmetic of indicators). For all $A, B \subseteq U$ and all $x \in U$:

$$\begin{aligned} \chi_{A \cap B} &= \chi_A \, \chi_B, & \chi_{A \cup B} &= \chi_A + \chi_B - \chi_A\chi_B,\\ \chi_{\overline{A}} &= 1 - \chi_A, & \chi_{A \setminus B} &= \chi_A(1 - \chi_B),\\ \chi_{A \triangle B} &= \chi_A + \chi_B - 2\chi_A\chi_B &&\equiv \chi_A \oplus \chi_B \pmod 2. \end{aligned}$$

Proof. Each is checked by the (at most) four cases of $(\chi_A(x),\chi_B(x))$. For intersection: $\chi_{A\cap B}(x)=1$ iff $x\in A$ and $x\in B$ iff $\chi_A(x)=\chi_B(x)=1$ iff the product $\chi_A(x)\chi_B(x)=1$; otherwise the product is $0$. For complement: $x\in\overline A$ iff $x\notin A$, so $\chi_{\overline A}(x)=1-\chi_A(x)$. For union, use the identity $A\cup B = \overline{\overline A \cap \overline B}$ (De Morgan) or check directly: if $x$ is in neither set both sides are $0$; if $x$ is in exactly one, both sides are $1$ (since $\chi_A\chi_B=0$); if in both, $\chi_A+\chi_B-\chi_A\chi_B = 1+1-1 = 1$. Difference and symmetric difference follow from $A\setminus B = A\cap\overline B$ and $A\triangle B=(A\setminus B)\cup(B\setminus A)$; note for the symmetric difference the two terms are disjoint, so the union’s correction term vanishes and $\chi_{A\triangle B}=\chi_A(1-\chi_B)+\chi_B(1-\chi_A) =\chi_A+\chi_B-2\chi_A\chi_B$, which is $0$ when the inputs agree and $1$ when they differ — exactly $\chi_A \oplus \chi_B$, the XOR. $\blacksquare$

Finally, indicators count:

Lemma 2.12 (counting via indicators). For finite $U$ and $A \subseteq U$,

$$|A| = \sum_{x \in U} \chi_A(x).$$

Proof. The sum adds $1$ for each $x \in A$ and $0$ for each $x \notin A$, so it equals the number of elements of $A$. $\blacksquare$

Why this matters. Lemma 2.10 turns “prove $L = R$” into “prove $\chi_L = \chi_R$ as functions”, and Lemma 2.11 turns that into an identity of polynomials in the $0/1$ variables $\chi_A, \chi_B, \dots$ — pure algebra, no quantifiers. A membership table (§2.8) is nothing more than evaluating those polynomials at all $2^n$ assignments. And in §2.14 we will see that a characteristic function is a bit-vector, so these lemmas are the specification of the machine’s AND, OR, NOT, XOR, and popcount.

2.7 The algebra of sets: the laws #

The operations satisfy a fixed collection of identities (laws) holding for all subsets $A, B, C$ of a universe $U$. They are the axioms/theorems of the algebra of sets. Each law that involves $\cup$ and $\cap$ comes in a pair: swapping $\cup \leftrightarrow \cap$ and $U \leftrightarrow \varnothing$ throughout turns one column into the other. This symmetry is the duality principle (§2.9).

Two structural remarks worth internalising:

• Associativity lets us drop parentheses and write $A \cup B \cup C$ and $A \cap B \cap C$ unambiguously; more generally $A_1 \cup \dots \cup A_n$ and $A_1 \cap \dots \cap A_n$ are well-defined (§2.12).
• Distributivity is richer than in arithmetic. In numbers only $\times$ distributes over $+$ ($a(b+c) = ab+ac$), and $+$ does not distribute over $\times$. In set algebra both directions hold: $\cup$ over $\cap$ and $\cap$ over $\cup$. This extra symmetry is exactly what makes the algebra “Boolean”.

Common pitfall (arithmetic intuition misleads). Because $\cup$ resembles $+$ and $\cap$ resembles $\times$, students expect $A \cup (B \cap C) = (A\cup B)\cap (A\cup C)$ to fail the way $a + bc \ne (a+b)(a+c)$ does for numbers. It does not fail: it is a genuine law (Theorem 2.15). Set algebra is not number arithmetic; trust the proofs, not the analogy.

2.8 Proving the laws: two independent methods #

There are two standard, fully rigorous ways to prove a set identity $L = R$, plus the characteristic-function shortcut of §2.6 (which is really Method 1 made algebraic). Mastering both is more important than memorising the laws.

Method 1 — membership table. Every element $x \in U$ is classified by which of the sets $A, B, C, \dots$ it belongs to; with $n$ sets there are $2^n$ classes, encoded by $0/1$ columns. Build a table with one row per class and columns computing membership in $L$ and in $R$ (using $\cup \to \lor$, $\cap \to \land$, $\overline{\phantom{A}} \to \lnot$). If the $L$-column and the $R$-column are identical in every row, then every $x$ lies in $L$ iff it lies in $R$, so by Lemma 2.10, $L = R$. (This is exactly evaluating the indicator polynomials of §2.6 at all $2^n$ inputs.)

Method 2 — double inclusion (element-chasing). Prove $L \subseteq R$ and $R \subseteq L$ separately. For $L \subseteq R$: take an arbitrary $x \in L$, unfold the definitions, and deduce $x \in R$. When every step is an “iff”, the two inclusions are proved simultaneously by a single biconditional chain.

We now prove the core laws, deliberately showing each family by a different method so that both techniques are on display; the flagship distributive law is proved both ways.

Commutativity, associativity, idempotence (biconditional chains) #

These three rest directly on the corresponding laws of the logical connectives.

Theorem 2.13 (commutativity). $A \cup B = B \cup A$ and $A \cap B = B \cap A$.

Proof. For every $x \in U$,

$$x \in A \cup B \iff (x \in A)\lor(x \in B) \iff (x \in B)\lor(x \in A) \iff x \in B \cup A,$$

where the middle “iff” is the commutativity of the logical “or”. Since membership in the two sides agrees for every $x$, Lemma 2.10 gives $A \cup B = B \cup A$. The $\cap$ case is identical, using commutativity of “and”. $\blacksquare$

Theorem 2.14 (associativity). $A \cup (B \cup C) = (A \cup B) \cup C$ and $A \cap (B \cap C) = (A \cap B) \cap C$.

Proof. For every $x \in U$,

$$x \in A \cup (B \cup C) \iff (x\in A) \lor \big((x\in B)\lor(x\in C)\big) \iff \big((x\in A)\lor(x\in B)\big) \lor (x\in C) \iff x \in (A \cup B) \cup C,$$

the middle step being the associativity of “or”. By Lemma 2.10 the sets are equal. The $\cap$ case uses associativity of “and”. $\blacksquare$

Theorem (idempotence). $A \cup A = A$ and $A \cap A = A$.

Proof. $x \in A \cup A \iff (x\in A)\lor(x\in A) \iff x\in A$, since $p \lor p$ is logically equivalent to $p$. Dually $x\in A\cap A \iff (x\in A)\land(x\in A)\iff x\in A$. $\blacksquare$

Remark. Notice the pattern: each set law is the image of a law of propositional logic under the dictionary $\cup\leftrightarrow\lor$, $\cap\leftrightarrow\land$, $\overline{\phantom A}\leftrightarrow\lnot$, $U\leftrightarrow \text{true}$, $\varnothing\leftrightarrow\text{false}$. This is not a coincidence; both are Boolean algebras (Lectures 4–5).

Distributivity — proved twice #

Theorem 2.15 (distributive law).

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

Proof 1 (membership table). Three sets give $2^3 = 8$ classes. We compute both sides:

The two bold columns — membership in $A\cap(B\cup C)$ and in $(A\cap B)\cup(A\cap C)$ — agree in all eight rows. By Lemma 2.10 the sets are equal. $\blacksquare$

Proof 2 (double inclusion). We prove each inclusion by element-chasing.

($\subseteq$) Let $x \in A \cap (B \cup C)$. Then $x \in A$, and $x \in B \cup C$, so $x \in B$ or $x \in C$.

• If $x \in B$: then $x \in A$ and $x \in B$, so $x \in A \cap B$, hence $x \in (A\cap B)\cup(A\cap C)$.
• If $x \in C$: then $x \in A$ and $x \in C$, so $x \in A \cap C$, hence $x \in (A\cap B)\cup(A\cap C)$.

In either case $x \in (A\cap B)\cup(A\cap C)$. Thus $A \cap (B\cup C) \subseteq (A\cap B)\cup(A\cap C)$.

($\supseteq$) Let $x \in (A\cap B)\cup(A\cap C)$. Then $x \in A\cap B$ or $x \in A\cap C$.

• If $x \in A\cap B$: then $x\in A$ and $x\in B$; since $x\in B$ we have $x\in B\cup C$, so $x\in A\cap(B\cup C)$.
• If $x \in A\cap C$: then $x\in A$ and $x\in C$; since $x\in C$ we have $x\in B\cup C$, so $x\in A\cap(B\cup C)$.

In either case $x \in A\cap(B\cup C)$. Thus $(A\cap B)\cup(A\cap C) \subseteq A\cap(B\cup C)$.

Both inclusions hold, so by the double-inclusion criterion the sets are equal. $\blacksquare$

Remark (which method when?). Membership tables are mechanical and unambiguous — ideal for checking an identity involving few sets, or when you are unsure it is even true. Double inclusion scales to statements a table cannot reach (arbitrary or infinitely many sets, §2.12) and often reveals why the identity holds. The characteristic-function method (Proof of Proposition 2.6 style, or Lemma 2.11) is the slickest for symbolic manipulation. All three are equally valid; use the one that fits.

The dual law $A \cup (B \cap C) = (A\cup B)\cap(A\cup C)$ is proved the same way (swap $\cup\leftrightarrow\cap$ throughout), or derived for free from the duality principle of §2.9.

Absorption — double inclusion and algebraic derivation #

Theorem 2.16 (absorption). $A \cup (A \cap B) = A$ and $A \cap (A \cup B) = A$.

Proof (double inclusion, first form). ($\supseteq$) Every $x \in A$ satisfies $x \in A \cup (A\cap B)$ by definition of union, so $A \subseteq A \cup (A\cap B)$. ($\subseteq$) Let $x \in A \cup (A\cap B)$. Then $x \in A$, or $x \in A\cap B$. In the first case $x\in A$ directly; in the second $x \in A\cap B$ implies $x \in A$. Either way $x \in A$, so $A \cup (A\cap B) \subseteq A$. Both inclusions give $A \cup (A\cap B) = A$. $\blacksquare$

Alternative proof (algebraic, from earlier laws). This shows laws can be derived from laws — the beginning of treating set algebra as a formal calculus:

$$A \cup (A \cap B) \overset{\text{identity}}{=} (A \cap U) \cup (A \cap B) \overset{\text{distrib.}}{=} A \cap (U \cup B) \overset{\text{domination}}{=} A \cap U \overset{\text{identity}}{=} A.$$

The second form $A \cap (A \cup B) = A$ follows dually. $\blacksquare$

De Morgan’s laws #

De Morgan’s laws describe how complement interacts with union and intersection:

$$\overline{A \cup B} = \overline{A} \cap \overline{B}, \qquad \overline{A \cap B} = \overline{A} \cup \overline{B}.$$

In words: the complement of a union is the intersection of the complements, and the complement of an intersection is the union of the complements. Slogan: “push the bar inward and flip the operation.”

Theorem 2.17 (De Morgan). Both identities above hold for all $A, B \subseteq U$.

Proof 1 (biconditional chain / double inclusion at once). For every $x \in U$,

$$x \in \overline{A \cup B} \iff x \notin A \cup B \iff \lnot\big((x\in A)\lor(x\in B)\big) \iff (x\notin A)\land(x\notin B) \iff x\in\overline A \land x\in\overline B \iff x \in \overline{A}\cap\overline{B}.$$

The central step is De Morgan’s law of logic, $\lnot(p\lor q)\equiv(\lnot p)\land (\lnot q)$. Every link is an “iff”, so both inclusions hold and, by Lemma 2.10, $\overline{A\cup B}=\overline A\cap\overline B$. $\blacksquare$

Proof 2 (membership table). Four classes for the two sets:

The columns $\overline{A \cup B}$ and $\overline{A} \cap \overline{B}$ coincide in every row, proving the first law. The second law, $\overline{A\cap B}=\overline A\cup\overline B$, follows by the identical technique, or from the first by replacing $A,B$ with $\overline A,\overline B$ and taking complements (using double complement $\overline{\overline X}=X$), or instantly from duality (§2.9). $\blacksquare$

Example 2.18. With $U=\{1,\dots,8\}$, $A=\{1,2,3,4\}$, $B=\{3,4,5,6\}$: here $A \cap B = \{3,4\}$, so $\overline{A \cap B} = \{1,2,5,6,7,8\}$; and $\overline{A} = \{5,6,7,8\}$, $\overline{B} = \{1,2,7,8\}$, so $\overline{A} \cup \overline{B} = \{1,2,5,6,7,8\}$. Equal, as claimed.

Difference as intersection with complement #

We used this identity above; here is its proof, a clean one-line biconditional chain.

Proposition 2.19. $A \setminus B = A \cap \overline{B}.$

Proof. For all $x \in U$: $x \in A\setminus B \iff (x\in A)\land(x\notin B) \iff (x\in A)\land(x\in\overline B) \iff x \in A\cap\overline B.$ $\blacksquare$

This is the bridge that lets any expression in $\setminus$ be rewritten purely in $\cap, \cup, \overline{\phantom{A}}$, so the laws of §2.7 apply to it. For instance, $A \setminus (B \cup C) = A \cap \overline{B\cup C} = A \cap \overline B \cap \overline C = (A\setminus B)\cap(A\setminus C)$ — a De Morgan-flavoured law for difference (Exercise S3).

2.9 The duality principle #

Look again at the table in §2.7: the two columns are mirror images. This is a theorem, not an accident.

Definition (dual). The dual of a set-algebra statement built from $\cup, \cap, \varnothing, U$ (and $=$, $\subseteq$, complement) is obtained by interchanging

$$\cup \leftrightarrow \cap, \qquad \varnothing \leftrightarrow U,$$

leaving complements and the sets themselves unchanged. (Under $\subseteq$, one also reverses the inclusion, since $\subseteq$ becomes $\supseteq$.)

Duality Principle. If a set identity holds for all subsets of every universe, then so does its dual.

Justification. Take any identity $L = R$ valid for all sets in all universes. Replace every set variable $X$ appearing in it by its complement $\overline X$, and then take the complement of both entire sides. Complementing an expression and pushing the bars all the way inward, by repeated De Morgan and double complement, turns every $\cup$ into $\cap$, every $\cap$ into $\cup$, every $U$ into $\varnothing$, every $\varnothing$ into $U$, and returns each $\overline{X}$ to $X$ — precisely the dual transformation. Since the original identity held for all sets (in particular for the complemented ones), the transformed identity also holds universally. That transformed identity is the dual of $L=R$. $\blacksquare$

Example 2.20. The distributive law $A\cap(B\cup C)=(A\cap B)\cup(A\cap C)$ (Theorem 2.15) has dual $A\cup(B\cap C)=(A\cup B)\cap(A\cup C)$ — applying the swap $\cap\to\cup$, $\cup\to\cap$ gives the other distributive law. Absorption’s two forms are dual; the two De Morgan laws are dual; the two identity laws are mutually dual, as are the two domination laws. Having proved one member of each pair, duality delivers the other for free.

Common pitfall. Duality swaps $\cup\leftrightarrow\cap$ and $\varnothing\leftrightarrow U$ only. It does not touch complement bars and does not replace a set by its complement in the final statement. Also, duality is a statement about identities that hold universally; it says nothing about a one-off equation true for some particular sets.

2.10 The algebra of symmetric difference #

Symmetric difference deserves its own treatment because it turns $\mathcal P(U)$ into an object with even more structure than the $\cup/\cap$ algebra: a ring. The key is Lemma 2.11, which showed $\chi_{A\triangle B}\equiv \chi_A+\chi_B \pmod 2$ — symmetric difference is “addition of indicators modulo $2$”, i.e. bitwise XOR.

Theorem 2.21 (laws of $\triangle$). For all $A, B, C \subseteq U$:

1. Commutative: $A \triangle B = B \triangle A$.
2. Associative: $(A \triangle B) \triangle C = A \triangle (B \triangle C)$.
3. Identity: $A \triangle \varnothing = A$.
4. Self-inverse: $A \triangle A = \varnothing$; hence $A \triangle B = \varnothing \iff A = B$.
5. $\cap$ distributes over $\triangle$: $A \cap (B \triangle C) = (A\cap B)\triangle(A\cap C)$.

Proof. We work with characteristic functions and Lemma 2.10; write $a=\chi_A(x)$, $b=\chi_B(x)$, $c=\chi_C(x)$, and recall $\chi_{X\triangle Y}\equiv \chi_X+\chi_Y \pmod 2$ and $\chi_{X\cap Y}=\chi_X\chi_Y$.

(1) $\chi_{A\triangle B}\equiv a+b \equiv b+a \equiv \chi_{B\triangle A}\pmod 2$.

(2) $\chi_{(A\triangle B)\triangle C}\equiv (a+b)+c \equiv a+(b+c)\equiv \chi_{A\triangle(B\triangle C)}\pmod 2$, using associativity of integer addition. Since the indicators agree for every $x$, Lemma 2.10 gives equality of the sets.

(3) $\chi_{A\triangle\varnothing}\equiv a + 0 \equiv a \pmod 2$, so $A\triangle\varnothing = A$.

(4) $\chi_{A\triangle A}\equiv a + a = 2a \equiv 0 \pmod 2$, so $A\triangle A=\varnothing$. For the consequence: if $A\triangle B=\varnothing$ then $\chi_A+\chi_B\equiv 0$, i.e. $\chi_A\equiv\chi_B\pmod 2$; as both are $0/1$ this forces $\chi_A=\chi_B$, so $A=B$. Conversely $A=B$ gives $A\triangle A=\varnothing$.

(5) $\chi_{A\cap(B\triangle C)} = a\,(b+c \bmod 2)$. Modulo $2$ this is $a(b+c)=ab+ac\equiv (ab)+(ac)\pmod2$, and $ab=\chi_{A\cap B}$, $ac=\chi_{A\cap C}$, so it equals $\chi_{(A\cap B)\triangle(A\cap C)}$. (The step $a(b+c)\equiv ab+ac$ holds because multiplication distributes over addition in $\mathbb Z$ and reduction mod $2$ respects both operations.) Hence the two sets are equal. $\blacksquare$

CS connection (a Boolean ring). Properties (1)–(5), together with the idempotence $A\cap A=A$ and identity $A\cap U=A$, say exactly that $(\mathcal P(U),\ \triangle,\ \cap)$ is a commutative ring in which every element is its own additive inverse and every element is idempotent under multiplication — a Boolean ring, with “addition” $=\triangle$ (XOR), “multiplication” $=\cap$ (AND), “zero” $=\varnothing$, and “one” $=U$. This is the algebraic heart of digital logic and of Lecture 4–5’s Boolean algebra: XOR is addition mod $2$, AND is multiplication mod $2$. It also explains why solving “set equations” often feels like solving linear systems over the two-element field $\mathbb F_2$.

Corollary 2.22 (odd-occurrence rule). For any finite list of sets $A_1,\dots,A_k$, an element $x$ lies in $A_1\triangle A_2\triangle\cdots\triangle A_k$ if and only if $x$ belongs to an odd number of the $A_i$.

Proof. By associativity (Theorem 2.21(2)) the iterated symmetric difference is well-defined, and its indicator at $x$ is $\chi_{A_1}(x)+\cdots+\chi_{A_k}(x) \bmod 2$, which is $1$ exactly when an odd number of the summands are $1$, i.e. when $x$ is in an odd number of the $A_i$. $\blacksquare$

This is the set-theoretic version of “XOR detects odd parity”, the principle behind parity check bits and the classic puzzle of finding the one unpaired element in a list by XOR-ing everything together.

Cardinality of a symmetric difference.

$$|A \triangle B| = |A| + |B| - 2|A \cap B|.$$