Sets: The Nouns of Mathematics

Discover: a dataset, written as a set

Open almost any machine-learning paper and within a page or two you'll find its data described with set notation. Here is how the LoRA paper, the source of one of today's most widely used ways to fine-tune large language models, introduces the data for a task:

The words around it say this is “a training dataset of context-target pairs”, where each $x_i$ is a prompt and each $y_i$ the text the model should produce. Read it aloud: “calligraphic Z is the set of pairs x i, y i, for i from 1 to N”. Three conventions are packed into that one line. The curly braces make a set. The round brackets make an ordered pair, context first and target second. The subscript range says there's one pair for every index from 1 to $N$.

A few lines later, the paper describes its method as training “a much smaller-sized set of parameters $\Theta$ with $|\Theta| \ll |\Phi_0|$”, where $\Phi_0$ holds the weights of the original model. You met $\ll$ in Chamber 1. The vertical bars are new.

Learn: sets and membership

A set is a collection of distinct objects, called its elements. The only thing a set records is what's in it. Order doesn't matter and neither does repetition, so these are all the same set:

Listing elements between curly braces is called roster notation. The key verb is $\in$, “is an element of”: $2 \in \{1, 2, 3\}$ is true, and $4 \notin \{1, 2, 3\}$ says 4 is not an element. There's exactly one set with nothing in it, the empty set $\varnothing$. The size of a finite set, written $|A|$, is how many elements it has. Mathematicians call it the cardinality.

Machine learning is full of sets. A language model has a vocabulary $\mathcal{V}$ of tokens, and $|\mathcal{V}|$ is its vocabulary size. An image classifier picks from a set of labels such as $\{\text{cat}, \text{dog}, \text{bird}\}$. The LoRA sentence above says the set of trained parameters $\Theta$ has far fewer elements than the model's full set $\Phi_0$.

Sets can sit inside other sets. $A \subseteq B$, “A is a subset of B”, means every element of $A$ is also in $B$. A proper subset, $A \subsetneq B$, adds that $B$ has something extra. Two sets are equal exactly when each is a subset of the other, and that simple fact is the strategy behind every proof in this chamber.

Learn: set-builder notation

Rosters are fine for three elements. They're hopeless for a million, or for infinitely many. Set-builder notation describes a set by a rule instead:

Read it “the set of $x$ in $S$ such that $P$ of $x$”. Before the colon is where the candidates come from. After it is the test each candidate must pass. Some authors use a vertical bar instead of the colon, as in $\{x \mid P(x)\}$, and read it the same way. A third form puts a formula on the left to build the elements: $\{2k : k \in \mathbb{Z}\}$ is every integer doubled, which is the set of even numbers.

Here's one from machine learning. After a classifier makes predictions $\hat{y}_i$ for examples $i = 1, \ldots, n$, the set of its mistakes is

and its accuracy is $1 - |M|/n$. If you know Python, you've already written this. The set comprehension {i for i in range(n) if y_hat[i] != y[i]} is set-builder notation, almost symbol for symbol. (Python counts from 0, the paper from 1.)

Learn: the number systems

Every paper assumes a few standard sets of numbers and names them in blackboard bold (Chamber 1). They fit inside each other, and each one fills a gap in the one before:

The natural numbers $\mathbb{N}$ count things, but $3 - 5$ has no answer there, so we extend to the integers $\mathbb{Z}$. The integers can't do $1 \div 2$, so we extend to the rationals $\mathbb{Q}$, the fractions. Even fractions leave holes: the length $\sqrt{2}$ isn't a fraction (Chamber 3 proves it), so we fill the number line completely and get the reals $\mathbb{R}$. Weights, losses, learning rates and probabilities all live in $\mathbb{R}$. Computers store floating-point approximations of real numbers, but papers write $\mathbb{R}$.

Subscripts trim these sets down. $\mathbb{R}_{\ge 0}$ is the non-negative reals, home of distances and variances. $\mathbb{R}_{+}$ is either the positive or the non-negative reals, depending on the author. Intervals are the pieces of $\mathbb{R}$ between two endpoints, and the bracket shape says whether each endpoint is included. A probability satisfies $p \in [0, 1]$, with both ends allowed. The sigmoid function (Chamber 4) outputs values in $(0, 1)$: it gets arbitrarily close to 0 and 1 but never reaches them.

Learn: union, intersection, difference and complement

Four operations make new sets from old ones. Each has a one-line definition in set-builder notation, and each is secretly a logic word:

The complement needs a universe $U$, the set of everything under discussion. Without one, “everything not in $A$” would include every number, every word and every cat. Two sets with nothing in common, $A \cap B = \varnothing$, are called disjoint. A training set and a test set should be disjoint, and Problem 2 below shows how to check.

The best way to get a feel for these operations is to play with them. In the lab, three sets cut the universe into eight regions, and every expression you build lights up some of them. Watch for the moment two different expressions light up the same regions.

Learn: proving De Morgan's law

In the lab, $(A \cup B)^c$ and $A^c \cap B^c$ lit up the same regions. Is that always true, for any sets at all, finite or infinite? Pictures can't settle that. A proof can.

Claim (De Morgan's law). For any sets $A$ and $B$ in a universe $U$, $(A \cup B)^c = A^c \cap B^c$.

The strategy is element chasing. Two sets are equal when each is a subset of the other, and to show $X \subseteq Y$ you take an arbitrary element of $X$ (one you know nothing about beyond $x \in X$) and show it must be in $Y$.

Proof. First we show $(A \cup B)^c \subseteq A^c \cap B^c$. Let $x \in (A \cup B)^c$. By the definition of complement, $x \notin A \cup B$. If $x$ were in $A$ it would be in $A \cup B$, so $x \notin A$. By the same argument, $x \notin B$. So $x \in A^c$ and $x \in B^c$, which means $x \in A^c \cap B^c$.

Now the other direction, $A^c \cap B^c \subseteq (A \cup B)^c$. Let $x \in A^c \cap B^c$. Then $x \notin A$ and $x \notin B$. To be in $A \cup B$ an element must be in $A$ or in $B$, and $x$ is in neither, so $x \notin A \cup B$. That is, $x \in (A \cup B)^c$.

Each side is a subset of the other, so the two sets are equal. $\blacksquare$

Look at what made it work. We never drew a picture or picked an example. We unpacked each symbol into its definition, reasoned about a single arbitrary $x$, and repacked the result. Because $x$ was arbitrary, the argument covers every element of every pair of sets. The second law, $(A \cap B)^c = A^c \cup B^c$, has the same proof with “and” and “or” swapped, and you'll put it together yourself at the end of this chamber.

Learn: counting with inclusion–exclusion

How big is a union? Adding $|A| + |B|$ is tempting, but it counts every element of $A \cap B$ twice. The fix is called inclusion–exclusion, and here is its derivation in full.

1. 1

   Cut the union into disjoint pieces

   Every element of $A \cup B$ is in exactly one of three pieces: only in $A$, in both, or only in $B$. The pieces are disjoint, so their sizes simply add:

   $$|A \cup B| = |A \setminus B| + |A \cap B| + |B \setminus A|.$$
2. 2

   Cut A the same way

   $A$ splits into the disjoint pieces $A \setminus B$ and $A \cap B$, so $|A| = |A \setminus B| + |A \cap B|$. Rearranged:

   $$|A \setminus B| = |A| - |A \cap B|.$$
3. 3

   And B

   Likewise, $|B \setminus A| = |B| - |A \cap B|$.

4. 4

   Substitute and simplify

   Put the last two lines into the first:

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

Include both sets, then exclude the part you counted twice. For example, if 700 of 1000 training sentences mention a date, 400 mention a place and 250 mention both, then $700 + 400 - 250 = 850$ mention at least one, and $1000 - 850 = 150$ mention neither. With three sets the pattern continues: add the three sizes, subtract the three pairwise overlaps, then add back the triple overlap, which the subtraction removed once too often. Problem 1 puts that to work.

Learn: tuples, products and the sets of machine learning

Sets forget order, but data often can't. An ordered pair $(a, b)$ remembers which entry comes first: $(1, 2) \ne (2, 1)$, whereas $\{1, 2\} = \{2, 1\}$. An ordered list of $n$ entries, $(x_1, \ldots, x_n)$, is an $n$-tuple, and in a tuple repeats count too.

The Cartesian product $A \times B$, read “A cross B”, is the set of all ordered pairs with the first entry from $A$ and the second from $B$:

For example, $\{0, 1\} \times \{\text{x}, \text{y}\} = \{(0, \text{x}), (0, \text{y}), (1, \text{x}), (1, \text{y})\}$. Laid out as a grid, with one row per element of $A$ and one column per element of $B$, it has $|A|$ rows and $|B|$ columns, so $|A \times B| = |A| \cdot |B|$.

Now the sets you'll see in every paper come into focus:

• $\mathbb{R}^2 = \mathbb{R} \times \mathbb{R}$ is the plane: every point is a pair of real numbers.
• $\mathbb{R}^n$ is the set of all $n$-tuples of reals. A $28 \times 28$ greyscale image, like those in the MNIST digits dataset, is a list of 784 pixel values, so $\mathbf{x} \in \mathbb{R}^{784}$.
• $\mathbb{R}^{m \times n}$ is the set of all real grids with $m$ rows and $n$ columns. “$W \in \mathbb{R}^{512 \times 64}$” is a complete sentence: $W$ is a real matrix with 512 rows and 64 columns. Chamber 6 reads these shapes in depth.
• $\{1, \ldots, K\}$ is the usual label set of a classifier with $K$ classes.

Put together, a labelled dataset $\mathcal{D} = \{(\mathbf{x}_i, y_i)\}_{i=1}^{n}$ with $\mathbf{x}_i \in \mathbb{R}^d$ and $y_i \in \{1, \ldots, K\}$ is simply a subset of a product: $\mathcal{D} \subseteq \mathbb{R}^d \times \{1, \ldots, K\}$.

Read beyond the course

Sets are the first chapter of nearly every book on proofs and discrete mathematics. These are free, and each goes a step past this chamber.

Papers and lectures

Set notation is how papers say what type of thing each symbol is, and you can now read those sentences in any paper. Two short passages are worth reading today.

In Attention Is All You Need, go to Section 3.2.2, Multi-Head Attention. It's half a page. Skim the displayed $\mathrm{MultiHead}$ equation: $\mathrm{Concat}$ and $\mathrm{Attention}$ are named functions, and Chamber 9 reads attention in full. Then read slowly from “Where the projections are parameter matrices”. That sentence is four membership statements in a row, and it tells you the shape of every learned weight in the layer. The value $d_{\text{model}} = 512$ comes from the first paragraph of Section 3.1.

In the LoRA paper, reread Section 2, the source of this chamber's opening, and then the first paragraph of Section 4.1. There you'll find $W_0 \in \mathbb{R}^{d \times k}$, $B \in \mathbb{R}^{d \times r}$ and $A \in \mathbb{R}^{r \times k}$: more membership statements that fix shapes. Skip the experiments for now. Chamber 6 and the Linear Algebra course come back to what the shapes mean.

Watch

A quick tour of notation for discrete mathematics, worked through small examples. The set theory part reviews this chamber, and the parts on quantifiers and on sums and products preview Chambers 3 and 5. Pause whenever a symbol appears and say it aloud before she does.

Your turn

First match symbols to words and to Python, which has sets built in. Then assemble one proof and write another, and finish with three problems in code.