# 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.

![Venn diagram of the union A ∪ B, with both circles shaded](img/l02_venn_union.png)

### 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$.

![Four Venn diagrams shading, in turn, the union A∪B, the intersection A∩B, the difference A∖B, and the complement of A](img/l02_venn_ops.png)

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

| Configuration | Example | Meaning |
|---|---|---|
| Overlapping circles | $A=\{1,2,3\}$, $B=\{3,4,5\}$ | $A \cap B = \{3\} \ne \varnothing$; neither contains the other |
| Separate circles | $A=\{1,2,3\}$, $B=\{4,5,6\}$ | $A \cap B = \varnothing$ (disjoint) |
| One circle inside the other | $A=\{1,2,3\}$, $B=\{2,3\}$ | $B \subseteq A$ |

![Three configurations of two circles: overlapping (A∩B≠∅), disjoint (A∩B=∅), and nested (B⊆A)](img/l02_venn_config.png)

> **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.

![Venn diagram of the symmetric difference A △ B: elements in exactly one of A, B](img/l02_venn_symdiff.png)

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.

![Disjoint sets (A ∩ B = ∅) beside a partition of S into disjoint blocks](img/l02_disjoint_partition.png)

**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).

| Law | Form 1 (with $\cup$) | Form 2 (with $\cap$) |
|---|---|---|
| **Commutative** | $A \cup B = B \cup A$ | $A \cap B = B \cap A$ |
| **Associative** | $A \cup (B \cup C) = (A \cup B) \cup C$ | $A \cap (B \cap C) = (A \cap B) \cap C$ |
| **Distributive** | $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$ | $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ |
| **Identity** | $A \cup \varnothing = A$ | $A \cap U = A$ |
| **Domination** | $A \cup U = U$ | $A \cap \varnothing = \varnothing$ |
| **Idempotent** | $A \cup A = A$ | $A \cap A = A$ |
| **Complement** | $A \cup \overline{A} = U$ | $A \cap \overline{A} = \varnothing$ |
| **Absorption** | $A \cup (A \cap B) = A$ | $A \cap (A \cup B) = A$ |
| **De Morgan** | $\overline{A \cup B} = \overline{A} \cap \overline{B}$ | $\overline{A \cap B} = \overline{A} \cup \overline{B}$ |
| **Double complement** | $\overline{\overline{A}} = A$ | — (self-dual) |
| **Complements of constants** | $\overline{U} = \varnothing$ | $\overline{\varnothing} = U$ |

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:

| $A$ | $B$ | $C$ | $B\cup C$ | $A\cap(B\cup C)$ | $A\cap B$ | $A\cap C$ | $(A\cap B)\cup(A\cap C)$ |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| 1 | 1 | 1 | 1 | **1** | 1 | 1 | **1** |
| 1 | 1 | 0 | 1 | **1** | 1 | 0 | **1** |
| 1 | 0 | 1 | 1 | **1** | 0 | 1 | **1** |
| 1 | 0 | 0 | 0 | **0** | 0 | 0 | **0** |
| 0 | 1 | 1 | 1 | **0** | 0 | 0 | **0** |
| 0 | 1 | 0 | 1 | **0** | 0 | 0 | **0** |
| 0 | 0 | 1 | 1 | **0** | 0 | 0 | **0** |
| 0 | 0 | 0 | 0 | **0** | 0 | 0 | **0** |

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."

![Venn diagram of De Morgan's law: the complement of A ∪ B equals Aᶜ ∩ Bᶜ](img/l02_demorgan.png)

**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:

| $A$ | $B$ | $A \cup B$ | $\overline{A \cup B}$ | $\overline{A}$ | $\overline{B}$ | $\overline{A} \cap \overline{B}$ |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| 1 | 1 | 1 | **0** | 0 | 0 | **0** |
| 1 | 0 | 1 | **0** | 0 | 1 | **0** |
| 0 | 1 | 1 | **0** | 1 | 0 | **0** |
| 0 | 0 | 0 | **1** | 1 | 1 | **1** |

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|.
$$

*Proof.* $A\triangle B = (A\setminus B)\cup(B\setminus A)$ is a disjoint union, and
$|A\setminus B|=|A|-|A\cap B|$, $|B\setminus A|=|B|-|A\cap B|$ (each part of $A$,
resp. $B$, outside the overlap). Adding gives $|A|+|B|-2|A\cap B|$. $\blacksquare$
The factor $2$ (versus the single subtraction in inclusion–exclusion, §2.13) reflects
that the shared elements are excluded from $A\triangle B$ entirely, not merely counted
once.

## 2.11 The Cartesian product

Sets are unordered, but coordinates, records, and strings are *ordered*. The
Cartesian product manufactures order out of unordered sets, and — crucially for
Lecture 3 — every relation is a subset of one.

**Definition (ordered pair; product).** Recall $(a,b)=(c,d)$ iff $a=c$ and $b=d$
(Lecture 1). The **Cartesian product** of $A$ and $B$ is the set of all ordered pairs
with first component from $A$ and second from $B$:

$$
A \times B = \{\,(a,b) : a \in A,\ b \in B\,\}.
$$

**Example 2.23.** $A = \{1,2,3\}$, $B = \{a,b,c\}$:

$$
A \times B = \{(1,a),(1,b),(1,c),\ (2,a),(2,b),(2,c),\ (3,a),(3,b),(3,c)\},
$$

nine pairs — one for each choice of first component paired with each choice of second.

### Cardinality

**Theorem 2.24 (product rule).** For finite sets, $\ |A \times B| = |A|\cdot|B|.$

*Proof.* Let $|A|=m$ and $|B|=n$, say $A=\{a_1,\dots,a_m\}$ with the $a_i$ distinct.
Group the pairs of $A\times B$ by first coordinate: for each fixed $i$, the set

$$
R_i = \{(a_i, b) : b \in B\}
$$

contains exactly $n$ pairs, since distinct $b$'s give distinct pairs (equality of
ordered pairs forces equal second coordinates). Distinct $i$'s give disjoint $R_i$
(pairs with different first coordinates cannot be equal), and every pair of
$A\times B$ lies in exactly one $R_i$. Thus $\{R_1,\dots,R_m\}$ partitions
$A\times B$ into $m$ blocks of size $n$, so by the addition principle (§2.13)

$$
|A\times B| = \underbrace{n + n + \dots + n}_{m\ \text{terms}} = m\cdot n = |A|\cdot|B|. \qquad\blacksquare
$$

**Example 2.25.** In Example 2.23, $|A\times B| = 3\cdot 3 = 9$, matching the count.

### Algebraic properties, with proofs

**Theorem 2.26 (distribution over $\cup$ and $\cap$).** For all sets $A, B, C$:

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

(The same holds with the product on the right, and with $\setminus$ in place of
$\cap$.)

*Proof.* Elements of these sets are ordered pairs, so we chase a generic pair
$(x,y)$. For the union:

$$
(x,y)\in A\times(B\cup C) \iff (x\in A)\land(y\in B\cup C) \iff (x\in A)\land\big((y\in B)\lor(y\in C)\big).
$$

Distributivity of $\land$ over $\lor$ rewrites the right side as

$$
\big((x\in A)\land(y\in B)\big)\lor\big((x\in A)\land(y\in C)\big) \iff (x,y)\in A\times B \ \lor\ (x,y)\in A\times C \iff (x,y)\in(A\times B)\cup(A\times C).
$$

Every step is an "iff", so the two sets have the same elements and are equal. For the
intersection, replace the inner $\lor$ by $\land$ throughout and use idempotence and
associativity of $\land$ (collapsing the duplicated $x\in A$); the chain becomes
$(x\in A)\land(y\in B)\land(y\in C) \iff (x,y)\in A\times B \land (x,y)\in A\times C$.
$\blacksquare$

**Theorem 2.27 (behaviour at $\varnothing$; non-commutativity).**
1. $A \times \varnothing = \varnothing = \varnothing \times A$.
2. $A\times B=\varnothing \iff A=\varnothing \lor B=\varnothing$.
3. If $A$ and $B$ are nonempty, then $A \times B = B \times A \iff A = B$.

*Proof.* *(1)* There is no pair whose second (resp. first) component lies in
$\varnothing$, so the product is empty. *(2)* If either factor is empty, by (1) the
product is empty. Conversely, if both are nonempty, pick $a\in A$, $b\in B$; then
$(a,b)\in A\times B$, so the product is nonempty — contrapositive gives the claim.
*(3)* ($\Leftarrow$) trivial. ($\Rightarrow$) Suppose $A,B$ nonempty and
$A\times B=B\times A$. Take any $a\in A$ and any $b\in B$. Then $(a,b)\in A\times B = B\times A$, so $(a,b)$ has first component in $B$: $a\in B$. As $a\in A$ was
arbitrary, $A\subseteq B$. Symmetrically $b\in A$ for all $b\in B$, so $B\subseteq A$.
Hence $A=B$. $\blacksquare$

**Example 2.28 (non-commutativity).** $\{1,2\}\times\{a\} = \{(1,a),(2,a)\}$, but
$\{a\}\times\{1,2\} = \{(a,1),(a,2)\}$ — different pairs, so the products differ.

**Example 2.29 (distributivity, concrete).** $A=\{1,2\}$, $B=\{a\}$, $C=\{b\}$:
$A\times(B\cup C)=\{1,2\}\times\{a,b\}=\{(1,a),(1,b),(2,a),(2,b)\}$, while
$(A\times B)\cup(A\times C)=\{(1,a),(2,a)\}\cup\{(1,b),(2,b)\}$ — the same four pairs.

> **Common pitfall.** The Cartesian product does **not** distribute over itself, and
> a union of products need not be a product: $(A\times B)\cup(C\times D)$ is generally
> *not* of the form $E\times F$. For example $(\{1\}\times\{1\})\cup(\{2\}\times\{2\}) =\{(1,1),(2,2)\}$, which is not any Cartesian product (a nonempty product containing
> $(1,1)$ and $(2,2)$ must also contain $(1,2)$). Distribution is of $\times$ over
> $\cup/\cap$, not the reverse.

### Generalisation: $n$-fold products and powers

For $n$ sets we take ordered $n$-tuples:

$$
A_1 \times A_2 \times \cdots \times A_n = \{\,(a_1,\dots,a_n) : a_i \in A_i\ \text{for each } i\,\}, \qquad |A_1 \times \cdots \times A_n| = |A_1|\cdots|A_n|.
$$

**Example 2.30.** Adding $C = \{\star,\,!\}$ to $A=\{1,2,3\}$, $B=\{a,b,c\}$ gives
$A\times B\times C$ with $3\cdot 3\cdot 2 = 18$ triples, e.g. $(1,a,\star)$, $(3,c,!)$.

When all factors coincide we write the **power** $A^n = \underbrace{A \times \cdots \times A}_{n}$. In particular $\{0,1\}^n$ is the set of all **bit strings of length
$n$**, with $|\{0,1\}^n| = 2^n$. This set is the same as the set of characteristic
functions on an $n$-element universe (§2.6) and the same, up to naming, as
$\mathcal P(U)$ for $|U|=n$ (Lecture 1: $|\mathcal P(U)|=2^n$). We exploit this triple
identification in §2.14.

> **Cross-reference (Lecture 3).** A **binary relation** from $A$ to $B$ is by
> definition a subset $R \subseteq A \times B$; an **$n$-ary relation** is a subset of
> $A_1\times\cdots\times A_n$ — the mathematical model of a database table with $n$
> columns. Everything Lecture 3 does with relations is built on the product defined
> here, and its cardinality and distributive laws are used there constantly.

## 2.12 Generalized (indexed) unions and intersections

Union and intersection of two sets extend to an arbitrary **family** (indexed
collection) of sets $\{A_i\}_{i\in I}$, where $I$ is an **index set** (possibly
infinite).

**Definition (generalized union / intersection).**

$$
\bigcup_{i \in I} A_i = \{\,x : x \in A_i \ \text{for some } i \in I\,\}, \qquad \bigcap_{i \in I} A_i = \{\,x : x \in A_i \ \text{for every } i \in I\,\}.
$$

An element qualifies for the union if it lies in *at least one* member, and for the
intersection if it lies in *every* member. These reduce to the binary operations when
$I=\{1,2\}$, and associativity (Theorem 2.14) guarantees the finite case
$A_1\cup\cdots\cup A_n$ is unambiguous.

**Example 2.31 (finite family).** Let $B_i = \{0,1,\dots,i\}$ for $i=1,2,3$, so
$B_1=\{0,1\}$, $B_2=\{0,1,2\}$, $B_3=\{0,1,2,3\}$. Then

$$
\bigcup_{i=1}^{3} B_i = \{0,1,2,3\}=B_3, \qquad \bigcap_{i=1}^{3} B_i = \{0,1\}=B_1.
$$

For a *nested* (increasing) family the union is the largest member and the
intersection the smallest.

**Example 2.32 (infinite families over $\mathbb R$).** Index by $n\in\mathbb N$:

$$
\bigcap_{n=1}^{\infty}\Big(-\tfrac1n,\ \tfrac1n\Big) = \{0\}, \qquad \bigcup_{n=1}^{\infty}\Big[\tfrac1n,\ 1\Big] = (0,1], \qquad \bigcup_{n=1}^{\infty}[-n,\ n] = \mathbb R.
$$

Take the first: $0$ lies in every interval $(-1/n,1/n)$, while any $x\ne 0$ fails once
$1/n<|x|$ (choose $n>1/|x|$), so it is excluded — the intersection is exactly
$\{0\}$. These examples show generalized operations reaching sets no *finite*
combination produces, which is why element-chasing (Method 2), not tables, is the
tool here.

**Theorem 2.33 (generalized De Morgan and distributive laws).** For any family
$\{A_i\}_{i\in I}$ and any set $B$:

$$
\overline{\bigcup_{i\in I} A_i} = \bigcap_{i\in I}\overline{A_i}, \qquad \overline{\bigcap_{i\in I} A_i} = \bigcup_{i\in I}\overline{A_i},
$$

$$
B \cap \bigcup_{i\in I} A_i = \bigcup_{i\in I}(B\cap A_i), \qquad B \cup \bigcap_{i\in I} A_i = \bigcap_{i\in I}(B\cup A_i).
$$

*Proof (first De Morgan law).* For every $x\in U$,

$$
x\in\overline{\textstyle\bigcup_i A_i} \iff x\notin\bigcup_i A_i \iff \lnot\big(\exists i:\, x\in A_i\big) \iff \forall i:\, x\notin A_i \iff \forall i:\, x\in\overline{A_i} \iff x\in\bigcap_i\overline{A_i},
$$

the central step being the quantifier duality $\lnot\exists \equiv \forall\lnot$.
By Lemma 2.10 the sets are equal. The other three identities are proved by the same
biconditional-chain method, using $\lnot\forall\equiv\exists\lnot$ and the
distributive laws of $\land,\lor$ over the quantifiers. $\blacksquare$

> **Remark.** Membership tables are *useless* for infinite families (infinitely many
> "columns"), so Theorem 2.33 can only be proved by element-chasing. This is the
> concrete reason both proof methods are worth learning: Method 2 is strictly more
> powerful.

## 2.13 The inclusion–exclusion principle

Counting the union of sets is the archetype of "correcting for overlap". Naively
adding $|A|+|B|$ double-counts the shared elements; inclusion–exclusion is the exact
correction. We first isolate the additive foundation.

**Addition Principle (rule of sum).** If $A_1,\dots,A_k$ are finite and pairwise
disjoint, then $\displaystyle\Big|\bigcup_{i=1}^k A_i\Big| = \sum_{i=1}^k |A_i|$.

*Proof.* By Lemma 2.12, $|X|=\sum_{x\in U}\chi_X(x)$. When the $A_i$ are pairwise
disjoint, each $x$ lies in at most one of them, so $\chi_{\bigcup_i A_i}(x) = \sum_{i}\chi_{A_i}(x)$ (at most one summand is $1$). Summing over $x\in U$ and swapping
the finite sums, $|\bigcup_i A_i| = \sum_{x}\sum_i \chi_{A_i}(x) = \sum_i \sum_x \chi_{A_i}(x) = \sum_i |A_i|$. $\blacksquare$

**Theorem 2.34 (inclusion–exclusion, two sets).** For finite sets $A, B$,

$$
|A \cup B| = |A| + |B| - |A \cap B|.
$$

*Proof (partition into disjoint pieces).* The three sets $A\setminus B$, $A\cap B$,
$B\setminus A$ are pairwise disjoint and their union is $A\cup B$ (every element of
the union is in $A$ only, both, or $B$ only). By the addition principle,

$$
|A\cup B| = |A\setminus B| + |A\cap B| + |B\setminus A|. \tag{$\ast$}
$$

Moreover $A$ is the disjoint union of $A\setminus B$ and $A\cap B$, so
$|A|=|A\setminus B|+|A\cap B|$, giving $|A\setminus B|=|A|-|A\cap B|$; symmetrically
$|B\setminus A|=|B|-|A\cap B|$. Substituting into $(\ast)$,

$$
|A\cup B| = \big(|A|-|A\cap B|\big) + |A\cap B| + \big(|B|-|A\cap B|\big) = |A|+|B|-|A\cap B|. \qquad\blacksquare
$$

*Second proof (characteristic functions).* By Lemma 2.11,
$\chi_{A\cup B}=\chi_A+\chi_B-\chi_A\chi_B=\chi_A+\chi_B-\chi_{A\cap B}$. Summing over
$x\in U$ and applying Lemma 2.12 term by term gives
$|A\cup B|=|A|+|B|-|A\cap B|$ at once. $\blacksquare$

**Example 2.35.** In a class of $30$ students, $18$ study French and $15$ study
German, with $7$ studying both. Then $|F\cup G| = 18 + 15 - 7 = 26$ study at least
one language, and $30-26 = 4$ study neither (the neither-count is $|U| - |F\cup G|$).

![Venn diagram for inclusion–exclusion: |A ∪ B| = |A| + |B| − |A ∩ B|](img/l02_incl_excl.png)

**Theorem 2.36 (inclusion–exclusion, three sets).** For finite $A, B, C$,

$$
|A\cup B\cup C| = |A|+|B|+|C| - |A\cap B| - |A\cap C| - |B\cap C| + |A\cap B\cap C|.
$$

*Proof (reduction to the two-set case).* Group $A\cup B\cup C = (A\cup B)\cup C$ and
apply Theorem 2.34:

$$
|A\cup B\cup C| = |A\cup B| + |C| - |(A\cup B)\cap C|. \tag{1}
$$

By the distributive law (Theorem 2.15), $(A\cup B)\cap C = (A\cap C)\cup(B\cap C)$;
apply Theorem 2.34 to *this* union:

$$
|(A\cup B)\cap C| = |A\cap C| + |B\cap C| - |(A\cap C)\cap(B\cap C)|. \tag{2}
$$

Now $(A\cap C)\cap(B\cap C) = A\cap B\cap (C\cap C) = A\cap B\cap C$ by commutativity
and idempotence. Substitute $|A\cup B| = |A|+|B|-|A\cap B|$ (Theorem 2.34) and $(2)$
into $(1)$:

$$
|A\cup B\cup C| = \big(|A|+|B|-|A\cap B|\big) + |C| - \big(|A\cap C|+|B\cap C|-|A\cap B\cap C|\big),
$$

which rearranges to the stated formula. $\blacksquare$

The pattern — *add singles, subtract pairwise overlaps, add back the triple overlap* —
continues.

> **Remark (general inclusion–exclusion).** For $n$ finite sets,
>

$$
\Big|\bigcup_{i=1}^n A_i\Big| = \sum_{\varnothing\ne S\subseteq\{1,\dots,n\}} (-1)^{|S|+1}\Big|\bigcap_{i\in S} A_i\Big|,
$$

> i.e. add all singletons, subtract all pairs, add all triples, and so on with
> alternating signs. It follows by expanding $\chi_{\bigcup_i A_i} = 1 - \prod_{i=1}^n(1-\chi_{A_i})$ (the union's complement is the intersection of the
> complements) and summing over $U$: the product expands into a signed sum of
> $\chi_{\bigcap_{i\in S}A_i}$ over subsets $S$, exactly the alternating formula.

## 2.14 Applications

### 2.14.1 Bit-vector set operations

Everything in §2.6 becomes a data structure. Fix a universe of size $n$ with a chosen
ordering $U = \{x_0, x_1, \dots, x_{n-1}\}$. Represent a subset $A\subseteq U$ by its
**bit vector** $b(A)\in\{0,1\}^n$ whose $i$-th bit is $\chi_A(x_i)$: bit $i$ is $1$ iff
$x_i \in A$. This is the characteristic function written as a binary word — the
identification $\mathcal P(U)\cong\{0,1\}^n$ of §2.11 made physical.

![Set operations as bitwise machine instructions: ∩ = AND, ∪ = OR, △ = XOR](img/l02_bitvector_ops.png)

Under this representation, Lemma 2.11 says the set operations are exactly the
bitwise machine instructions:

| Set operation | Bitwise op on $b(A), b(B)$ | Indicator identity |
|---|---|---|
| $A \cup B$ | `OR` | $\chi_A + \chi_B - \chi_A\chi_B$ |
| $A \cap B$ | `AND` | $\chi_A\chi_B$ |
| $\overline{A}$ | `NOT` | $1-\chi_A$ |
| $A \setminus B$ | `AND` with `NOT` : `a & ~b` | $\chi_A(1-\chi_B)$ |
| $A \triangle B$ | `XOR` | $\chi_A \oplus \chi_B$ |
| $x_i \in A$? | test bit $i$ : `(a >> i) & 1` | $\chi_A(x_i)$ |
| $\lvert A\rvert$ | `popcount` (population count) | $\sum_i \chi_A(x_i)$ |

**Worked example.** Let $U=\{1,2,3,4,5,6,7,8\}$ and index element $k$ to bit $k-1$.
For $A=\{1,2,3,4\}$ and $B=\{3,4,5,6\}$ (our running sets):

$$
b(A) = 0000\,1111_2 = 15, \qquad b(B) = 0011\,1100_2 = 60.
$$

Then

$$
\begin{aligned} b(A\cup B) &= 15\ \texttt{OR}\ 60 = 0011\,1111_2 = 63 &&\to \{1,2,3,4,5,6\},\\ b(A\cap B) &= 15\ \texttt{AND}\ 60 = 0000\,1100_2 = 12 &&\to \{3,4\},\\ b(A\triangle B) &= 15\ \texttt{XOR}\ 60 = 0011\,0011_2 = 51 &&\to \{1,2,5,6\},\\ b(A\setminus B) &= 15\ \texttt{AND}\ (\texttt{NOT}\ 60) = 0000\,0011_2 = 3 &&\to \{1,2\}, \end{aligned}
$$

matching Examples 2.1–2.5 exactly. De Morgan's law appears at the hardware level as
`NOT(a OR b) == (NOT a) AND (NOT b)`.

> **CS connection.** For $|U|\le 64$ a set fits in one machine word, so union,
> intersection, membership, and complement each cost a *single* CPU instruction, and
> $|A|$ costs one `POPCNT`. For larger universes one uses $\lceil n/w\rceil$ words
> ($w=64$), giving $O(n/w)$ time — the constant-factor speedup behind `std::bitset`
> (C++), `BitSet` (Java), `roaring bitmaps` in databases, and Python's arbitrary-width
> `int` used as a bit set. Sieve of Eratosthenes, graph reachability by bitset
> propagation, and DNA $k$-mer sets all lean on this. The **duality principle** even
> tells the compiler that an expression and its dual compile to the same-length
> instruction sequence with `AND`/`OR` swapped.

### 2.14.2 Inclusion–exclusion counting

Inclusion–exclusion turns "count things avoiding several forbidden properties" into
arithmetic. The template: let $A_i$ be the set of objects *having* property $i$; count
the union by Theorem 2.34/2.36; subtract from the total to count objects with *none*
of the properties.

**Example 2.37 (divisibility).** How many integers in $\{1,2,\dots,100\}$ are
divisible by $2$, $3$, or $5$? Let $A,B,C$ be the multiples of $2,3,5$ respectively.
The count of multiples of $d$ in $[1,100]$ is $\lfloor 100/d\rfloor$, and a number is
divisible by both $d$ and $e$ (coprime) iff divisible by $de$:

$$
|A|=50,\ |B|=33,\ |C|=20,\quad |A\cap B|=\lfloor100/6\rfloor=16,\ |A\cap C|=10,\ |B\cap C|=\lfloor100/15\rfloor=6,\quad |A\cap B\cap C|=\lfloor100/30\rfloor=3.
$$

By Theorem 2.36,

$$
|A\cup B\cup C| = 50+33+20 - 16-10-6 + 3 = 74.
$$

So $74$ integers are divisible by at least one of $2,3,5$, and $100-74 = 26$ are
divisible by none (i.e. coprime to $30$).

**Example 2.38 (survey).** Among $100$ people, $40$ use product $A$, $35$ use $B$,
$30$ use $C$; $15$ use $A$ and $B$, $12$ use $A$ and $C$, $10$ use $B$ and $C$, and
$5$ use all three. Then

$$
|A\cup B\cup C| = 40+35+30 - 15-12-10 + 5 = 73,
$$

so $73$ use at least one product and $100-73 = 27$ use none.

> **Common pitfall.** The pairwise data must be the sizes of the *intersections*
> ("use both $A$ and $B$"), not "use exactly $A$ and $B$ and nothing else". If a
> problem gives *exactly*-counts (region-by-region), do **not** plug them into
> Theorem 2.36; instead fill the Venn regions directly and add. Mixing the two
> conventions is the most common inclusion–exclusion error.

### 2.14.3 SQL set operations

A relational database table, under *set semantics*, is a set of rows (tuples), so the
algebra of this chapter is literally the algebra of query results. Standard SQL
provides three set operators, applied to two **union-compatible** queries (same number
of columns, compatible types) — the SQL echo of "you can only combine sets drawn from
the same universe":

| Set operation | SQL | Notes |
|---|---|---|
| $A \cup B$ | `A UNION B` | duplicates removed (true set union) |
| $A \cap B$ | `A INTERSECT B` | |
| $A \setminus B$ | `A EXCEPT B` (Oracle: `A MINUS B`) | |
| $A \triangle B$ | `(A EXCEPT B) UNION (B EXCEPT A)` | no dedicated keyword |
| $\overline{A}$ | `SELECT * FROM U EXCEPT SELECT * FROM A` | complement needs an explicit universe table `U` |

For instance, students taking at least one of two languages, and those taking both:
```sql
SELECT id FROM french_students
UNION
SELECT id FROM german_students;      -- ∪ : at least one

SELECT id FROM french_students
INTERSECT
SELECT id FROM german_students;      -- ∩ : both

SELECT id FROM french_students
EXCEPT
SELECT id FROM german_students;      -- ∖ : French but not German
```

> **Common pitfall (bag vs. set semantics).** Plain `UNION` removes duplicate rows —
> matching the mathematical union — but `UNION ALL` keeps them, implementing
> *multiset* (bag) union, which does **not** obey idempotence ($A \,\texttt{UNION ALL}\, A \ne A$ when $A$ has rows). The distinct-preserving operators (`UNION`,
> `INTERSECT`, `EXCEPT`) obey all the laws of §2.7; the `ALL` variants generally do
> not. Because deduplication costs a sort or hash, engines use bag semantics by
> default in many contexts — know which one your query is in.

> **Cross-reference.** SQL's `WHERE` clause combines conditions with `AND`, `OR`,
> `NOT`, which by the logic–set dictionary correspond to $\cap$, $\cup$, complement on
> the selected row-sets — so `WHERE p AND q` selects the intersection of the rows
> satisfying `p` and those satisfying `q`. The full theory of tables as $n$-ary
> relations is Lecture 3.

## Historical note

The algebra of sets is a nineteenth-century creation. **George Boole** (1815–1864),
in *The Mathematical Analysis of Logic* (1847) and *An Investigation of the Laws of
Thought* (1854), recast logic as algebra — his "elective symbols" combine essentially
as $\cap$ and $\cup$ do here, and the laws of §2.7 are, in modern dress, *Boole's*
laws (Lectures 4–5 return to "Boolean algebra" by name). **Augustus De Morgan**
(1806–1871), Boole's correspondent and a founder of symbolic logic, gave the
complement–union–intersection laws that bear his name. **John Venn** (1834–1923)
introduced his diagrams in an 1880 paper on the diagrammatic representation of
propositions. The set-theoretic *universe* of objects to which these operations apply
was supplied by **Georg Cantor** (1845–1918), whose work in the 1870s–1880s founded
set theory as an autonomous subject. The **inclusion–exclusion principle** grew from
work of **Abraham de Moivre** and was cast as a general counting principle by
**J. J. Sylvester** in the nineteenth century. Finally, the observation that
$(\mathcal P(U),\triangle,\cap)$ is a *ring* (§2.10) is part of the bridge between
Boolean algebras and ring theory made precise by **Marshall Stone** in the 1930s
(Stone's representation theorem). Thus a single small algebra sits at the meeting point
of logic, set theory, combinatorics, and abstract algebra — and, a century later, of
digital hardware.

## Chapter summary

- The **basic operations** are union $A\cup B$ (in either), intersection $A\cap B$
  (in both), difference $A\setminus B$ (in $A$ not $B$), complement
  $\overline A = U\setminus A$ (in $U$ not $A$), and symmetric difference
  $A\triangle B$ (in exactly one). Each is defined by a logical predicate on
  membership; $A\setminus B = A\cap\overline B$ (Prop. 2.19) reduces difference to the
  others.
- **Venn diagrams** picture sets as regions in $U$; they *illustrate* but do not
  *prove* identities beyond a handful of sets.
- Sets are **disjoint** when $A\cap B=\varnothing$; a **partition** slices a set into
  nonempty pairwise-disjoint blocks. Disjointness makes counting additive.
- The **characteristic function** $\chi_A$ identifies a set with a $0/1$ function and
  turns operations into arithmetic ($\cap\to$ product, $\cup\to a+b-ab$, complement
  $\to 1-a$, $\triangle\to$ XOR); $|A|=\sum_x\chi_A(x)$. Set equality $\iff$ indicator
  equality (Lemma 2.10).
- The **algebra of sets** obeys commutative, associative, distributive (both ways!),
  identity, domination, idempotent, complement, absorption, De Morgan, and
  double-complement laws, arranged in $\cup/\cap$ **dual** pairs. Each is a shadow of a
  law of propositional logic.
- A set identity is **proved** by a **membership table** (finitely many sets) or by
  **double inclusion / biconditional chains** (any sets, including infinite families) —
  and often most slickly by **characteristic functions**. The distributive and De
  Morgan laws were proved by more than one method.
- The **duality principle** ($\cup\leftrightarrow\cap$, $\varnothing\leftrightarrow U$)
  gives the dual of any universally valid identity for free.
- **Symmetric difference** is commutative, associative, has identity $\varnothing$ and
  is self-inverse ($A\triangle A=\varnothing$); $\cap$ distributes over it, making
  $(\mathcal P(U),\triangle,\cap)$ a **Boolean ring**. An element is in
  $A_1\triangle\cdots\triangle A_k$ iff it lies in an **odd** number of the sets.
- The **Cartesian product** $A\times B$ is the set of ordered pairs, with
  $|A\times B|=|A|\,|B|$ (Thm 2.24); it distributes over $\cup,\cap,\setminus$ (Thm
  2.26), is non-commutative for distinct nonempty factors (Thm 2.27), and generalises
  to $n$-tuples and powers $A^n$ — including bit strings $\{0,1\}^n$. It is the
  foundation of relations (Lecture 3).
- **Generalized** unions/intersections range over arbitrary indexed families and obey
  generalized De Morgan and distributive laws (Thm 2.33), provable only by
  element-chasing.
- The **inclusion–exclusion principle** counts unions by correcting for overlap:
  $|A\cup B|=|A|+|B|-|A\cap B|$ and the three-set formula (Thms 2.34, 2.36), with an
  alternating-sign generalisation to $n$ sets.
- **Applications:** bit vectors realise sets as machine words with $O(1)$ operations;
  inclusion–exclusion solves "at least one / none" counting; SQL's `UNION`,
  `INTERSECT`, `EXCEPT` are $\cup,\cap,\setminus$ on tables (with a bag-vs-set caveat).

## Exercises

### Warm-up

**W1.** For $A=\{2,4,6,8\}$ and $B=\{4,8,12\}$, compute $A\cup B$, $A\cap B$,
$A\setminus B$, $B\setminus A$, and $A\triangle B$.

**W2.** With $U=\{1,\dots,10\}$ and $A=\{2,4,6,8\}$, find $\overline A$. Then change
$U$ to $\{1,\dots,20\}$ and find $\overline A$ again. Explain in one sentence why the
answer changed.

**W3.** For $A=\{a,b,c,d\}$, $B=\{c,d,e,f\}$, compute $A\triangle B$ both as
$(A\setminus B)\cup(B\setminus A)$ and as $(A\cup B)\setminus(A\cap B)$, and check the
two agree. Verify $A\triangle B = B\triangle A$.

**W4.** Let $U=\{1,\dots,8\}$ with element $k$ stored in bit $k-1$. Write the $8$-bit
vectors of $A=\{2,4,6,8\}$ and $B=\{1,2,3,4\}$, then compute $b(A\cup B)$,
$b(A\cap B)$, and $b(A\triangle B)$ by bitwise `OR`, `AND`, `XOR`, and translate each
back to a set.

**W5.** List all $8$ elements of $\{0,1\}^3$. How many elements does $\{0,1\}^n$ have,
and why does this equal $|\mathcal P(U)|$ for $|U|=n$?

**W6.** In a group of $50$ people, $30$ like tea, $25$ like coffee, and $10$ like
both. How many like at least one drink? How many like neither?

**W7.** State the dual of each: (a) $A\cap U = A$; (b) $A\cup(A\cap B)=A$;
(c&#41; $\overline{A\cap B}=\overline A\cup\overline B$.

### Standard

**S1.** Prove the absorption law $A\cap(A\cup B)=A$ by double inclusion.

**S2.** Prove the distributive law $A\cup(B\cap C)=(A\cup B)\cap(A\cup C)$ by a
membership table (all $8$ rows).

**S3.** Using $X\setminus Y = X\cap\overline Y$ and the laws of §2.7, prove
$A\setminus(B\cup C) = (A\setminus B)\cap(A\setminus C)$ and
$A\setminus(B\cap C) = (A\setminus B)\cup(A\setminus C)$.

**S4.** Prove that the following are equivalent for all sets $A,B$:
(i) $A\subseteq B$; (ii) $A\cup B = B$; (iii) $A\cap B = A$.
(Hint: prove (i)$\Rightarrow$(ii)$\Rightarrow$(iii)$\Rightarrow$(i) by
element-chasing.)

**S5.** Prove $A\times(B\cap C) = (A\times B)\cap(A\times C)$ by chasing a generic
ordered pair.

**S6.** Of $200$ students, $120$ took calculus, $90$ took linear algebra, and $70$
took discrete math; $50$ took calculus and linear algebra, $40$ took calculus and
discrete math, $30$ took linear algebra and discrete math, and $20$ took all three.
How many took at least one of the three courses? How many took none?

**S7.** Prove the cardinality identity $|A\triangle B| = |A|+|B|-2|A\cap B|$, and use
it to find $|A\triangle B|$ when $|A|=12$, $|B|=9$, $|A\cap B|=5$.

**S8.** Compute, for the family $A_n=\{\,x\in\mathbb R : 0\le x\le 1/n\,\}$
($n\in\mathbb N$): $\bigcup_{n\ge1}A_n$ and $\bigcap_{n\ge1}A_n$. Justify each with a
one-line element argument.

**S9.** Given two tables `A(id)` and `B(id)`, write SQL statements returning the ids
in (a) $A\cup B$, (b) $A\cap B$, (c&#41; $A\setminus B$, (d) $A\triangle B$. State one
reason `A UNION ALL B` can differ from `A UNION B`.

### Challenge

**C1.** Prove that symmetric difference is associative,
$(A\triangle B)\triangle C = A\triangle(B\triangle C)$, using characteristic
functions, and deduce that $x\in A\triangle B\triangle C$ iff $x$ lies in an odd
number of $A,B,C$. Then list $A\triangle B\triangle C$ for $A=\{1,2,3\}$,
$B=\{2,3,4\}$, $C=\{3,4,5\}$.

**C2.** (a) Prove $A\times(B\setminus C) = (A\times B)\setminus(A\times C)$.
(b) Give sets showing $(A\times B)\cup(C\times D)$ need not be a Cartesian product.

**C3.** Prove the two-set inclusion–exclusion principle using characteristic functions
(sum $\chi_{A\cup B}=\chi_A+\chi_B-\chi_{A\cap B}$ over $U$), then extend the same idea
to re-derive the three-set formula by expanding
$\chi_{A\cup B\cup C}=1-(1-\chi_A)(1-\chi_B)(1-\chi_C)$.

**C4.** How many integers in $\{1,\dots,1000\}$ are divisible by none of $2,3,5,7$?
(Use four-set inclusion–exclusion; the general alternating formula in §2.13 helps.)

**C5.** Prove that $(\mathcal P(U),\triangle,\cap)$ satisfies the ring axioms with
"zero" $\varnothing$ and "one" $U$: additive associativity/commutativity, additive
identity and inverses, multiplicative associativity/identity, and distributivity of
$\cap$ over $\triangle$. Which extra property makes it a *Boolean* ring? (Connect to
Lectures 4–5.)

**C6.** In a three-set Venn diagram you are told: $|A|=30$, $|B|=28$, $|C|=26$,
$|A\cap B\cap C|=6$, exactly $10$ elements lie in $A$ and $B$ (whether or not in $C$),
exactly $8$ lie in $A\cap C$, exactly $9$ lie in $B\cap C$, and $|U|=80$. Find the
number of elements in exactly one of the three sets, and the number in none.

## Selected answers & hints

**W1.** $A\cup B=\{2,4,6,8,12\}$; $A\cap B=\{4,8\}$; $A\setminus B=\{2,6\}$;
$B\setminus A=\{12\}$; $A\triangle B=\{2,6,12\}$.

**W2.** $\overline A=\{1,3,5,7,9,10\}$ (for $U=\{1,\dots,10\}$), then
$\{1,3,5,7,9,10,11,\dots,20\}$ (for $U=\{1,\dots,20\}$). Complement is measured
against $U$, so enlarging $U$ enlarges $\overline A$.

**W4.** $b(A)=1010\,1010_2=170$, $b(B)=0000\,1111_2=15$;
$b(A\cup B)=1010\,1111_2 \to \{1,2,3,4,6,8\}$;
$b(A\cap B)=0000\,1010_2 \to \{2,4\}$;
$b(A\triangle B)=1010\,0101_2 \to \{1,3,6,8\}$.

**W5.** The eight strings $000,001,010,011,100,101,110,111$; $|\{0,1\}^n|=2^n$. Each
bit string is a characteristic function on the $n$-element universe, and characteristic
functions correspond bijectively to subsets, so this equals $|\mathcal P(U)|=2^n$.

**W6.** $30+25-10 = 45$ like at least one; $50-45 = 5$ like neither.

**W7.** (a) $A\cup\varnothing = A$; (b) $A\cap(A\cup B)=A$;
(c&#41; $\overline{A\cup B}=\overline A\cap\overline B$.

**S2.** Table columns $A,B,C,B\cap C,A\cup(B\cap C),A\cup B,A\cup C, (A\cup B)\cap(A\cup C)$; the fifth and eighth columns both read
$1,1,1,1,1,0,1,0$ down the eight rows (order $A B C$ from $111$ to $000$) — hint:
$A\cup(B\cap C)$ is $1$ whenever $A=1$, and when $A=0$ it is $1$ iff $B=C=1$.

**S4.** (i)$\Rightarrow$(ii): if $A\subseteq B$ then $A\cup B\subseteq B$ (both parts
lie in $B$) and $B\subseteq A\cup B$ always, so $A\cup B=B$. (ii)$\Rightarrow$(iii):
$A\cap B = A\cap(A\cup B) = A$ by absorption. (iii)$\Rightarrow$(i): if $A\cap B=A$
then every $x\in A$ satisfies $x\in A\cap B$, hence $x\in B$; so $A\subseteq B$.

**S6.** $120+90+70 - 50-40-30 + 20 = 180$ took at least one; $200-180 = 20$ took none.

**S7.** $A\triangle B$ is the disjoint union of $A\setminus B$ and $B\setminus A$, of
sizes $|A|-|A\cap B|$ and $|B|-|A\cap B|$; sum is $|A|+|B|-2|A\cap B|$. Numerically
$12+9-2\cdot5 = 11$.

**S8.** $\bigcap_{n\ge1}A_n=\{0\}$: $0\in A_n$ for all $n$, and any $x>0$ fails once
$1/n<x$. $\bigcup_{n\ge1}A_n=A_1=[0,1]$: the sets are nested decreasing, so the union
is the largest, $A_1$.

**C1.** With $a=\chi_A,b=\chi_B,c=\chi_C$ (mod $2$),
$\chi_{(A\triangle B)\triangle C}\equiv(a+b)+c\equiv a+(b+c)\equiv \chi_{A\triangle(B\triangle C)}$; the value is $1$ iff $a+b+c$ is odd, i.e. an odd
number of memberships. For the given sets, element counts are $1\!:1,\ 2\!:2,\ 3\!:3,\ 4\!:2,\ 5\!:1$, so the odd ones are $1,3,5$: $A\triangle B\triangle C= \{1,3,5\}$.

**C3.** Summing $\chi_{A\cup B}=\chi_A+\chi_B-\chi_{A\cap B}$ over $x\in U$ and using
$|X|=\sum_x\chi_X$ gives $|A\cup B|=|A|+|B|-|A\cap B|$. Expanding
$(1-a)(1-b)(1-c)=1-(a+b+c)+(ab+ac+bc)-abc$ and using $ab=\chi_{A\cap B}$ etc. yields
$\chi_{A\cup B\cup C}=\chi_A+\chi_B+\chi_C-\chi_{A\cap B}-\chi_{A\cap C}-\chi_{B\cap C} +\chi_{A\cap B\cap C}$; sum over $U$.

**C4.** Total $1000$; let $A,B,C,D$ be multiples of $2,3,5,7$. Singles:
$500,333,200,142$. Pairs (multiples of $6,10,14,15,21,35$):
$166,100,71,66,47,28$. Triples (of $30,42,70,105$): $33,23,14,9$. Quadruple (of
$210$): $4$. Then $|A\cup B\cup C\cup D| = (500{+}333{+}200{+}142) - (166{+}100{+}71{+}66{+}47{+}28) + (33{+}23{+}14{+}9) - 4 = 1175 - 478 + 79 - 4 = 772$.
Divisible by none: $1000 - 772 = 228$.

**C6.** "Exactly $10$ in $A$ and $B$" here means $|A\cap B|=10$ (the standard reading:
in both, regardless of $C$); similarly $|A\cap C|=8$, $|B\cap C|=9$. Then
$|A\cup B\cup C| = 30+28+26 -10-8-9 +6 = 63$, so $80-63 = 17$ are in none. For
"exactly one": elements in $A$ only $= 30 - (10+8) + 6 = 18$ (subtract the two pairwise
overlaps involving $A$, add back the triple counted out twice); $B$ only
$= 28 - (10+9) + 6 = 15$; $C$ only $= 26 - (8+9) + 6 = 15$. Total in exactly one
$= 18+15+15 = 48$.

## Further reading

- **K. H. Rosen, *Discrete Mathematics and Its Applications*.** Chapter 2 (Sets, set
  operations, set identities) and the treatment of inclusion–exclusion; Rosen's
  membership-table and "show each is a subset" proofs parallel §2.8, and his
  bit-string representation of sets matches §2.14.1.
- **S. S. Epp, *Discrete Mathematics with Applications*.** The chapter on set theory
  develops the element-method (double inclusion) proofs in careful detail — excellent
  companion reading for §2.8 and §2.12.
- For the algebraic viewpoint (Boolean algebras and Boolean rings, §2.10) and the
  duality principle, see the Boolean-algebra chapters of the same texts, previewing
  Lectures 4–5 of this course.