Sets, functions and relations

Take three collections, written in curly brackets: A = {1, 2, 3}, B = {1, 2} and C = {2, 3}. The claim under test is that removing the numbers B and C have in common gives the same result as removing B and then removing C from what is left. The only number B and C have in common is 2, so removing it leaves 1 and 3. Removing B from A leaves {3}, removing C from A leaves {1}, and nothing survives both. The two answers are 1 and 3 against nothing, so the claim is false, and three small collections settle it.

A set is a collection in which order does not matter and repeats collapse [S:23:502], and membership is written ∈, as in x ∈ A, for "is a member of". A subset is a set whose members all lie in another set, written with ⊆ [S:5:90]. B is a subset of A, because 1 and 2 are both members of A; {3} is a subset of A too, with 3 as its only member. Two distinctions do most of the work here, and they look alike on the page: membership relates an object to a set, while the subset relation relates two sets. !Each word is a count of arrows, read off one function at a time. Injective: no output receives two arrows, shown with two inputs into three outputs, where one output stays empty. Surjective: every output receives at least one arrow, shown with three inputs into two outputs, where one output receives two. Bijective: both counts hold, shown with three inputs into three outputs, where every arrow lands alone and nothing is left over. Each panel carries both verdicts, so the two counts are independent, and the word attaches to a picture. Status: schematic.

Two sets are equal when every member of one is a member of the other, so a proof of equality is two proofs of containment, one in each direction. The opening example is a proof of inequality, which is cheaper, because it exhibits a member of one side that the other side omits: 1 survives the first removal and not the second. The empty set, the set with no members, is a subset of every set. A set fails to be a subset only if it holds a member that the other lacks, and the empty set holds nothing to fail with. !Eight functions, and the grid holds every one of them. Each cell is one function from three inputs to two outputs. Its code names the output chosen by the first, second and third input in turn. So 111 sends all three to the first output, and 112 sends the first two there and the third to the second output. No cell is injective, because three arrows cannot land in two outputs without a collision. The two outlined cells are the constant functions, the only ones that leave an output empty, so the six that remain are surjective. Status: re-simulated.

Sets answer the question of which things, and functions answer the question of which output. A function assigns exactly one output to each allowed input [S:23:504]. Picture a column of inputs on the left and a column of outputs on the right, with an arrow from each input to its output. The phrase "exactly one" then becomes a counting rule you can apply to the picture: exactly one arrow leaves each input, so an input with two arrows leaving it, or none, means the rule is not a function [S:5:99].

Three words describe how the arrows arrive. A function is injective, also called one-to-one, when no output receives two arrows, and surjective, also called onto, when every output receives at least one. It is a bijection when both conditions hold, so the arrows pair the two sets off exactly [S:5:99]. These are counts of arrows rather than mysterious properties, and on a finite pair of sets the counts can be established by inspection.

Worked example. Count the functions from a three-element set to a two-element set.

Each of the three inputs picks one of the two outputs, and the selections are independent, so there are 2 × 2 × 2 = 8 functions. None of them is injective, because three inputs and two outputs compel two arrows into one output. A constant function sends every input to one fixed output, and exactly two of the eight are constant, one for each choice of output. Those two are the only ones that omit an output entirely, so 8 − 2 = 6 of the functions are surjective. From a three-element set to itself there are 3 × 3 × 3 = 27 functions, and 6 of them are bijections, since the first input has 3 choices, the second 2 and the third 1.

One example shows why the language is needed. A predictor is a function from inputs to answers, and take the predictors that answer by asking a fixed list of yes-or-no questions about the input. The claim that every such predictor asks at most ten questions quantifies over a set of functions, the collection of predictors of that shape, and it says "for every predictor in that collection". Without a way to write that sentence, the claim cannot be stated precisely, let alone proved.

A relation is a set of ordered pairs, which is to say a rule linking members of one set to members of another [S:5:99]. An ordered pair is two objects in a fixed order, written (a, b), so (2, 3) and (3, 2) are different pairs. "Less than" on the whole numbers is a relation, and "leaves the same remainder on division by 3" is another; under the second, 7 and 4 are linked, while 7 and 5 are not [S:16:143].

The remainder relation has three properties, and each has a name. It is reflexive, because every number is linked to itself; symmetric, because the link runs in both directions; and transitive, because if a is linked to b and b to c, then a is linked to c. A relation with all three is an equivalence relation, and it sorts the whole numbers into classes whose members share a remainder [S:16:143].

A bijection is the strictest of the three arrow properties. It is the one that survives into the next section, where it becomes the definition of two sets having the same size.

The arrow count works only for finite sets. With infinite sets you cannot finish counting, and "same size" has to be redefined as the existence of a pairing rather than the agreement of two numbers. That redefinition is the next section, and it produces a result for which finite intuition provides no preparation.

The formal statement. A function $f$ from a set $A$ to a set $B$ is a set of ordered pairs with two clauses: every $a$ in $A$ appears as a first coordinate, and no $a$ appears twice. The function is injective when $f(a_1)=f(a_2)$ forces $a_1=a_2$. It is surjective when every $b$ in $B$ equals $f(a)$ for some $a$ in $A$. It is bijective when both hold. Each clause is a quantifier, so each negation is mechanical, and a proof can check the definitions instead of a picture.

The counting theorem. Let $A$ have $m$ members and $B$ have $n$. There are $n^m$ functions from $A$ to $B$, since each of the $m$ inputs chooses one of the $n$ outputs. A function is surjective when it omits no member of $B$. Count the functions that omit a fixed set of $k$ outputs: there are $(n-k{)}^m$. Inclusion and exclusion over the omitted outputs gives

The display says: count all functions, subtract those missing one output, add back those missing two, and continue to the end. At $m=3$ and $n=2$ it reads $8-2=6$, which is the core's count. No function is injective, because three inputs and two outputs force two arrows into one output.

The finite hypothesis. Both counts assume that $A$ and $B$ are finite, because they count choices. The pigeonhole clause fails for infinite sets. The map that sends $n$ to $n+1$ on the whole numbers is injective and omits 0, so an injection need not be a bijection and "three into two" is not a general argument. The next section turns that failure into the definition of size.

The edge case. Surjectivity belongs to the pair of formula and codomain, not to the formula. The rule $x\mapsto x^2$ is not surjective from $\mathbb{R}$ to $\mathbb{R}$, because no real square is negative. The same rule is surjective from $\mathbb{R}$ to the non-negative reals. The core's arrow count hides this, because a finite picture shows the codomain beside the arrows. Change the codomain and the property changes while the formula stays put.

The empty case. There is exactly one function from the empty set to any $B$: the empty set of pairs satisfies both clauses, because there are no inputs. There is no function from a nonempty set to the empty set. The core's "each input picks an output" says nothing about either case, and these are where readers first meet $0^0$ and empty products.

Where the arrow picture breaks. The two columns suggest that a function is a list of arrows. Most functions in this book have no finite list and no formula: a predictor is a function from inputs to labels, and a class of predictors is a set of such functions. The picture also suggests that the range is visible, when in practice only the codomain is stated.

What the core left out. It left out the codomain, and it left out the difference between a relation and a function. A relation is any set of pairs, so it may send one input to several outputs. "Exactly one" is the clause that turns a relation into a function [S:23:504].

Original sources. Sets, their operations and the definition of a function as a well-defined association are in the appendix of Hefferon's linear algebra text [S:23:502]. The subset relation and the cardinality of a finite set are in section 4.1, and the arrow count is in section 4.5 [S:5:90] [S:5:101]. Congruence modulo $n$, used as the running example of an equivalence relation, is section 5.2 of Hammack [S:16:143].

An open question. For binary classification the VC dimension characterises PAC learnability: a class is learnable exactly when its VC dimension is finite [S:79:70]. For a trained deep network there is no measure with the same authority. The open question is whether a quantity computed before training can predict the gap between training and test error across architectures, or whether the gap belongs to the trained weights alone. Evidence that would settle it: a measure computed from the architecture and the data before any fitting, which predicts test error across a wide range of models and tasks, with a theorem tying it to generalisation.

A frontier result. The VC dimension is where the set language of this section becomes a measurement. A class that shatters sets of every size cannot be learned, and the reason is a statement about sets of functions rather than about algorithms [S:79:70]. The sentence the text attaches to it is worth the space: if someone can explain every phenomenon, his explanations are worthless [S:79:70]. That is a claim about the size of a hypothesis class, and it takes one line to state.

What to read next. Read the appendix of [S:23:502] for sets and functions, and section 4.5 of [S:5:101] for the arrow count that this section turns into a proof. Read chapter 6 of [S:79:70] for the VC dimension, and chapter 5 of [S:79:61] for the theorem that explains why the class cannot be everything. Chapter 5 states the negative result and chapter 6 the positive one.