Foundations

Sets, relations, and functions

The vocabulary every other idea is built from

~10 minLesson 1 of 19Written by Claude Opus 4.8

The quiet vocabulary underneath everything else in this course: collections of things, the pairings between them, and the special pairings we call functions.

Three words carry an astonishing amount of weight in computer science and machine learning. A is a collection of distinct things. A pairs elements of one set with elements of another. A is a relation with one strict rule: every input gets exactly one output. When someone later says a neural network "learns a function," this is precisely the object they mean.

Three ideas, one sentence each

Set: a bag of distinct items, order does not matter, ${1, 2, 3} = {3, 1, 2}$ .
Relation: any collection of pairs, like "is-friends-with" linking people to people.
Function: a relation that never gives one input two answers, $f (x)$ is unambiguous.

Sets, and how we write them

A set is written with curly braces. Membership is the most basic question we can ask: is a thing in the set or not? We write $3 \in A$ ("3 is an element of $A$ ") and $7 \in / A$ ("7 is not"). Elements are distinct, a set has no duplicates, and unordered.

Listing every element gets tedious, so we use : describe the elements by a rule. Read the colon as "such that".

A = {x \in Z : 1 \leq x \leq 4} = {1, 2, 3, 4} A is the set of all integers x such that x is between 1 and 4.

The rule on the right of the colon is what makes sets scale to infinite collections you could never list by hand.

Four ways to combine sets

Given two sets $A$ and $B$ living inside some universe $U$ (the set of everything under discussion), four operations build new sets. Each has a set-builder definition, and each is just a plain-English condition on membership: union $A \cup B$ is in $A$ or $B$ ; intersection $A \cap B$ is in both; difference $A ∖ B$ is in $A$ but not $B$ ; and complement $A^{c} = U ∖ A$ is everything outside $A$ . Pick an operation below and watch which elements light up.

A \cup B = {x : x \in A or x \in B}

result = {1, 2, 3, 4, 5, 6}

Relations, and the functions among them

To pair things up, we first need a set of all possible pairs. The $A \times B$ is every ordered pair with a first coordinate from $A$ and a second from $B$ . A relation is then just any subset of that product, any selection of pairs you care about.

A \times B = {(a, b) : a \in A, b \in B}, R \subseteq A \times B

A function $f : X \to Y$ is a relation obeying one extra law: every element of the input set $X$ is paired with exactly one element of the output set $Y$ . No input left out, no input answered twice. Here $X$ is the domain (all legal inputs), $Y$ is the codomain (the declared target set), and the image is the subset of $Y$ that actually gets hit.

The one rule that makes it a function

Relation versus function is a single distinction: a relation may pair an input with zero, one, or many outputs; a function pairs each input with exactly one. Formally, if

(x, y_{1}) \in f

and

(x, y_{2}) \in f

, then

y_{1} = y_{2}

. That is the entire content of the vertical line test: a vertical line may cross the graph at most once.

Three shapes of function matter enough to have names. An injective (one-to-one) function never collapses two inputs onto the same output: $f (a) = f (b) \Rightarrow a = b$ . A surjective (onto) function reaches every corner of the codomain, so its image equals its codomain. A bijective function is both, a perfect one-to-one pairing, which is exactly what makes it reversible. And functions compose: feed the output of one into another, $(g \circ f) (x) = g (f (x))$ , the seed of how deep networks stack layers. Build a mapping below and read the verdict.

Build a mapping. Click an input, then an output, to toggle an arrow. A function gives every input exactly one arrow.

domain Xcodomain Y

valid functioninjectivesurjectivebijective

Draw some arrows to test the mapping.

Why this is the whole game

A trained model is a function

f : X \to Y

, from images to labels, or token-prefixes to next-tokens. Training is the search for a good

f

among billions of candidates. Meanwhile a relation, drawn as dots and arrows, is a graph, the structure the DSA path builds search and shortest-path algorithms on. Same two panels, two whole subjects.

A function is just a lookup with the one-output rule.

# A function maps each input to exactly one output
f = {"cat": 0, "dog": 1, "bird": 2}   # domain -> codomain

# A machine-learning model IS a function f: X -> Y
def model(x):            # X = images, Y = labels
    return classify(x)   # returns exactly one label per image

A machine-learning model is literally a function from inputs to outputs.

Check yourself

Which rule turns an ordinary relation into a function?

The property 'no two different inputs ever share the same output' is called:

What is the difference between a function's codomain and its image?

One is declared, the other is achieved. Try to state it, then check.

Lock it in

A set is distinct, unordered items; a relation is any set of pairs.
A function is a relation where every input has exactly one output.
Injective avoids collisions, surjective covers Y, bijective does both.
A trained model is literally a function f from X to Y.

Primary source

Richard Hammack's free Book of Proof devotes early chapters to sets, Cartesian products, relations, and functions. For the CS-flavored version with the same care, see MIT 6.042J, Mathematics for Computer Science.

Where this reappears

When we later say a neural network "learns a function," this is the function we mean, a map

f : X \to Y

we tune to fit examples. And the relations you drew as arrows here become graphs in the DSA path, where searching and shortest paths live.