Appearance
8.1 — Sets
Discrete mathematics is what you reach for when things come in whole pieces — people, votes, network links, moves in a game, rows in a table. Nothing in it is measured on a smooth scale, so calculus has nothing to say about it, and a different set of tools takes over. Those tools start with the simplest idea there is.
Every object in mathematics can be built from one idea: a collection of things. Numbers, functions, shapes, probabilities and matrices are all defined, at the bottom, as sets of something. It is the closest mathematics has to a universal building material.
A set is a collection of distinct objects, called its elements. That is the whole definition, and its usefulness comes from what it deliberately ignores: order does not matter and repetition does not count.
\{1,2,3\} = \{3,1,2\} = \{1,1,2,3\}
All the same set. If order matters you want a sequence; if repetition matters you want a multiset. The set is the version that has thrown both away, and that is exactly why it is simple enough to build everything else from.
1. Notation
3 \in A \quad\text{means 3 is an element of } A
3 \notin A \quad\text{means it is not}
Sets are written two ways.
By listing: A = \{2,4,6,8\}.
By a rule, called set-builder notation:
A = \{x \mid x \text{ is even and } 0 \lt x \lt 10\}
The vertical bar reads "such that". So: "the set of all x such that x is even and lies between 0 and 10".
The empty set \emptyset = \{\} has no elements. There is exactly one of it, and it is not the same as \{\emptyset\}, which is a set containing one thing — the empty set. That distinction sounds like word-play and matters enormously when sets are used to build the numbers.
Cardinality |A| is the number of elements. |\{2,4,6,8\}| = 4. For infinite sets this is Chapter 1.7's business, where cardinality comes in different sizes.
Standard sets, from Chapter 1.1: \mathbb{N} naturals, \mathbb{Z} integers, \mathbb{Q} rationals, \mathbb{R} reals, \mathbb{C} complex.
Subset: A \subseteq B means every element of A is in B. A proper subset A\subset B additionally requires them to be different.
\emptyset \subseteq A \text{ for every } A, \qquad A\subseteq A
The first is worth pausing on: the empty set is a subset of everything, because the statement "every element of \emptyset is in A" has no elements to check and is therefore true. This is called being vacuously true, and it is a small logical trap that Chapter 8.2 explains properly.
2. Operations
Union A\cup B — everything in either. Intersection A\cap B — everything in both. Difference A\setminus B — in A but not B. Complement A^c — everything in the universe under discussion that is not in A. Symmetric difference A\triangle B — in one or the other but not both. This is exclusive-or.
With A = \{1,2,3,4\} and B = \{3,4,5,6\}:
A\cup B = \{1,2,3,4,5,6\}, \quad A\cap B = \{3,4\}, \quad A\setminus B = \{1,2\}, \quad A\triangle B = \{1,2,5,6\}
The laws, which mirror ordinary algebra with one important difference:
A\cup B = B\cup A \qquad (A\cup B)\cup C = A\cup(B\cup C)
A\cap(B\cup C) = (A\cap B)\cup(A\cap C)
A\cup(B\cap C) = (A\cup B)\cap(A\cup C)
Both distributive laws hold, which is the difference from arithmetic — there, multiplication distributes over addition but addition does not distribute over multiplication.
De Morgan's laws are the ones worth memorising:
(A\cup B)^c = A^c\cap B^c, \qquad (A\cap B)^c = A^c\cup B^c
In words: "not (A or B)" is the same as "not A and not B". Negating swaps union and intersection.
You use these constantly in programming without naming them. The opposite of if (a || b) is if (!a && !b). Getting this wrong is a common bug, and knowing the law by name makes it automatic.
3. Power sets and products
The power set \mathcal{P}(A) is the set of all subsets of A.
\mathcal{P}(\{1,2\}) = \{\emptyset, \{1\},\{2\},\{1,2\}\}
|\mathcal{P}(A)| = 2^{|A|}
Because each element independently is in or out — Chapter 7.1's counting argument, and the reason the power set is sometimes written 2^A.
The Cartesian product A\times B is the set of all ordered pairs:
\{1,2\}\times\{a,b\} = \{(1,a),(1,b),(2,a),(2,b)\}
|A\times B| = |A|\times|B|
Named after Descartes, because \mathbb{R}\times\mathbb{R} is exactly the coordinate plane of Chapter 3.4 — every point is an ordered pair of reals.
Here order does matter: (1,a) and (a,1) are different pairs. The product is where ordering re-enters after sets threw it away, and it is how sequences, coordinates, relations and database joins are all built.
In a database, a table is a set of rows and a join is built on a Cartesian product filtered by a condition. Volume I, 7.1 says the same thing from the database side, and the reason relational databases are called relational is Chapter 8.4's notion of a relation, which is a subset of a Cartesian product.
4. Russell's paradox, and why the definition had to be repaired
Naively, any property defines a set: the set of all red things, the set of all prime numbers, the set of all sets.
In 1901 Bertrand Russell showed this breaks. Consider
R = \{x \mid x \notin x\}
the set of all sets that do not contain themselves. Most sets qualify — the set of all chairs is not itself a chair.
Now ask whether R contains itself.
If R \in R, then by its own definition R must not contain itself. Contradiction. If R \notin R, then it satisfies the defining property, so it must be in R. Contradiction.
Both answers are impossible.
The everyday version: a village barber shaves exactly those men who do not shave themselves. Who shaves the barber? Either answer is contradictory, and the resolution there is easy — no such barber can exist. The resolution in set theory is the same and much more disruptive: not every property defines a set.
Russell sent this to Gottlob Frege in 1902, just as Frege's life work on the foundations of arithmetic was going to press. Frege added an appendix beginning, "A scientist can hardly meet with anything more undesirable than to have the foundation give way just as the work is finished."
The repair is Zermelo–Fraenkel set theory, which replaces "any property defines a set" with axioms that only let you build new sets from existing ones. You may take a subset of a set you already have, or a power set, or a union — but you cannot conjure "the set of all sets" out of a description. That restriction blocks the paradox, and ZF with the axiom of choice (Chapter 3.6) is the standard foundation of mathematics today.
Chapter 11.5 continues this story into Gödel's theorems, where the ambition to make mathematics fully secure runs into a limit that cannot be repaired.
5. Building numbers out of nothing
To show what sets can do, here is how the natural numbers are constructed with no material other than the empty set. This is von Neumann's construction.
0 = \emptyset
1 = \{0\} = \{\emptyset\}
2 = \{0,1\} = \{\emptyset,\{\emptyset\}\}
3 = \{0,1,2\}
Each number is the set of all smaller numbers, so n has exactly n elements, which makes "how many" work out automatically. The successor of n is n\cup\{n\}.
From there: integers are pairs of naturals with a subtraction rule, rationals are pairs of integers with a division rule, reals are constructed from rationals by filling the gaps (Chapter 1.7), and complex numbers are pairs of reals. The whole tower of Chapters 1 and 2, built from the empty set and the operation of collecting things together.
Nobody works this way in practice. The point is that it can be done, which is what "mathematics has foundations" means.
Every formula above, built from scratch
None of the results in this chapter are worth memorising, because each one can be rebuilt in under a minute from something simpler. What follows is that rebuilding, one result at a time, so the formula and the reason for it sit on the same page as the explanation that needed them.
Sets
A\cup B = \{x : x\in A \text{ or } x\in B\}, \qquad A\cap B = \{x: x\in A \text{ and } x\in B\}
A\setminus B = \{x: x\in A \text{ and } x\notin B\}, \qquad A' = \{x : x\notin A\}
The laws, all of which can be checked by asking "which elements are in each side":
A\cup(B\cap C) = (A\cup B)\cap(A\cup C), \qquad A\cap(B\cup C) = (A\cap B)\cup(A\cap C)
(A\cup B)' = A'\cap B', \qquad (A\cap B)' = A'\cup B'
De Morgan's laws in plain English. "Not (in A or in B)" means "not in A and not in B" — if you are outside their union you are outside both. "Not (in A and in B)" means "outside at least one of them". The pattern is: push the negation inside and swap union with intersection. The same rule governs logic (\lnot(p\lor q) \equiv \lnot p\land\lnot q) and programming (!(a || b) is !a && !b).
|A\cup B| = |A|+|B|-|A\cap B|
|\mathcal{P}(A)| = 2^{|A|}
Where the power-set count comes from. To build a subset, go through the elements one at a time and decide "in or out". That is 2 choices per element, made independently, so 2^n subsets in total. The empty set (everything out) and A itself (everything in) are two of them.
|A\times B| = |A|\times|B|
6. Where this shows up in your life
Every database query. UNION, INTERSECT, EXCEPT and JOIN are exactly the operations of Section 2 and the product of Section 3.
Every search filter. "Red AND size 10 AND NOT out of stock" is an intersection of sets, and De Morgan's laws are how the query optimiser rewrites it.
Every type system. A union type is a set union; an intersection type is an intersection; never is the empty set. Volume I, 3.7.2 describes TypeScript's type vocabulary, and it is set theory with different syntax.
Every access control rule. Permissions are sets, roles are sets of permissions, and "does this user have access" is a membership test. Volume I, 8.4.10.
Every Set in every programming language, with its automatic deduplication — which is Section 1's rule that repetition does not count.
Every Venn diagram in a presentation.
Sets tell you what things there are. Logic tells you how to reason about statements concerning them, and it is the other foundation on which both mathematics and computing rest.