[1] TRUE3 %in% S[1] FALSE[1] 1 23 Sets and Functions
Sets are how mathematics says “a collection of things”. Functions are how it says “a rule that turns one thing into another”. Between them they underpin everything else in this book — a vector space is a set with rules, a linear map is a function, a random variable is a function, a model is a function you are trying to find.
Most of this chapter will feel familiar. The parts worth slowing down for are Section 3.6, which is where invertibility comes from, and Section 3.8, which is the vocabulary the calculus chapters assume.
3.1 Sets
A set is an unordered collection of distinct objects, called its elements.
\[ S = \{2, 4, 6, 8\} \]
Write \(2 \in S\) for “2 is in \(S\)” and \(3 \notin S\) for “3 is not”. Two properties follow from the definition and catch people out:
- Unordered: \(\{1,2\} = \{2,1\}\). If order matters you want a vector, not a set.
- Distinct: \(\{1,1,2\}\) is just \(\{1,2\}\). Sets do not count multiplicity.
Small sets can be listed. Larger ones need set-builder notation, which reads “the set of all \(x\) such that…”:
\[ E = \{\, x \in \mathbb{Z} \;:\; x \text{ is even} \,\} \qquad D = \{\, \mathbf{x} \in \mathbb{R}^2 \;:\; \|\mathbf{x}\| \leq 1 \,\} \]
The colon (sometimes a vertical bar) is “such that”. \(D\) here is the unit disc — every point within distance 1 of the origin.
Two more pieces of vocabulary. The empty set \(\emptyset = \{\}\) has no elements. The cardinality \(|S|\) is the number of elements, so \(|\{2,4,6,8\}| = 4\); infinite sets have infinite cardinality, and \(\mathbb{R}\) is infinite in a strictly larger way than \(\mathbb{N}\).
length(S)[1] 43.2 Set operations
| Operation | Notation | Meaning | R |
|---|---|---|---|
| Union | \(A \cup B\) | in \(A\) or \(B\) | union() |
| Intersection | \(A \cap B\) | in \(A\) and \(B\) | intersect() |
| Difference | \(A \setminus B\) | in \(A\) but not \(B\) | setdiff() |
| Complement | \(A^c\) | everything not in \(A\) | — |
| Subset | \(A \subseteq B\) | every element of \(A\) is in \(B\) | all(A %in% B) |
A complement only makes sense relative to some universal set \(U\) holding everything under discussion. In probability \(U\) is the sample space (Section 18.2).
De Morgan’s laws relate the operations, and are used constantly in probability:
\[ (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 neither A nor B.
3.3 Cartesian products
The Cartesian product \(A \times B\) is the set of all ordered pairs with the first element from \(A\) and the second from \(B\):
\[ A \times B = \{\, (a, b) \;:\; a \in A,\; b \in B \,\} \]
Unlike the operations above, this one builds structure rather than combining sets. Note the pairs are ordered, so \((1,2) \neq (2,1)\) even though \(\{1,2\} = \{2,1\}\).
expand.grid(a = c(1, 2), b = c("x", "y")) a b
1 1 x
2 2 x
3 1 y
4 2 yIf \(|A| = m\) and \(|B| = n\) then \(|A \times B| = mn\). This is where \(\mathbb{R}^n\) comes from: \(\mathbb{R}^2 = \mathbb{R} \times \mathbb{R}\) is the set of ordered pairs of reals — the plane — and \(\mathbb{R}^n\) is \(n\) copies. Every vector in this book is an element of a Cartesian product.
3.4 What a function is
A function \(f\) from a set \(A\) to a set \(B\) assigns to each element of \(A\) exactly one element of \(B\). Written:
\[ f: A \to B \]
Read “\(f\) maps \(A\) to \(B\)”. For a particular element, \(f: x \mapsto x^2\) uses a different arrow, read “\(x\) maps to \(x\) squared”.
The two quantifiers are the whole definition and both matter:
- Each element of \(A\) gets an output. No input may be left undefined.
- Exactly one output. An input cannot map to two different things.
So \(f(x) = \sqrt{x}\) is not a function on all of \(\mathbb{R}\) — negative inputs have no real output — and the rule “\(y\) such that \(y^2 = x\)” is not a function either, since \(x = 4\) would give both \(2\) and \(-2\). Restricting to \(f: \mathbb{R}_{\geq 0} \to \mathbb{R}_{\geq 0}\) with the positive root fixes both problems.
NoteIn machine learning
A trained model is a function: \(f: \mathbb{R}^p \to \mathbb{R}\) for regression, or \(\mathbb{R}^p \to \{1, \dots, K\}\) for classification. Training is a search through a set of candidate functions — the hypothesis space — for one that fits. Saying which set you are searching is how you specify a model class.
3.5 Domain, codomain, and range
For \(f: A \to B\):
- the domain is \(A\), the set of allowed inputs;
- the codomain is \(B\), the set outputs are declared to live in;
- the range (or image) is the set of values actually achieved.
The range is always a subset of the codomain, and often a strict one. For \(f: \mathbb{R} \to \mathbb{R}\), \(f(x) = x^2\), the codomain is all of \(\mathbb{R}\) but the range is only \(\mathbb{R}_{\geq 0}\) — no input produces a negative output.
That gap is not a technicality. It is exactly the gap between “the model could in principle output anything” and “here is what it actually outputs”, and it is why a linear model can predict a negative count.
| Function | Domain | Codomain | Range |
|---|---|---|---|
| \(x^2\) | \(\mathbb{R}\) | \(\mathbb{R}\) | \([0, \infty)\) |
| \(e^x\) | \(\mathbb{R}\) | \(\mathbb{R}\) | \((0, \infty)\) |
| \(\log x\) | \((0, \infty)\) | \(\mathbb{R}\) | \(\mathbb{R}\) |
| \(\sin x\) | \(\mathbb{R}\) | \(\mathbb{R}\) | \([-1, 1]\) |
| logistic | \(\mathbb{R}\) | \(\mathbb{R}\) | \((0, 1)\) |
3.6 Injective, surjective, bijective
Three properties, and the third is what “invertible” means.
Injective (one-to-one): different inputs give different outputs. No two arrows land on the same place.
\[ f(x_1) = f(x_2) \;\Longrightarrow\; x_1 = x_2 \]
Surjective (onto): every element of the codomain is hit. The range is the codomain.
Bijective: both. Every output is achieved, by exactly one input.
| Function | Injective? | Surjective? | Why |
|---|---|---|---|
| \(x^2\) on \(\mathbb{R} \to \mathbb{R}\) | No | No | \(f(-2) = f(2)\); nothing gives \(-1\) |
| \(x^2\) on \(\mathbb{R}_{\geq 0} \to \mathbb{R}_{\geq 0}\) | Yes | Yes | bijective after restricting |
| \(e^x\) on \(\mathbb{R} \to \mathbb{R}\) | Yes | No | never reaches \(0\) or below |
| \(e^x\) on \(\mathbb{R} \to (0,\infty)\) | Yes | Yes | bijective |
| \(2x + 1\) on \(\mathbb{R} \to \mathbb{R}\) | Yes | Yes | bijective |
Notice that the same rule changes status depending on the domain and codomain you declare. Injectivity and surjectivity are properties of \(f: A \to B\) as a whole, not of the formula.
A function is invertible exactly when it is bijective. Injective gives you at most one input per output; surjective gives you at least one. Together: exactly one, which is what an inverse needs in order to be well defined.
NoteIn machine learning
This is the same fact as Section 5.12, in general clothing. A matrix \(\mathbf{A}\) is a function \(\mathbb{R}^n \to \mathbb{R}^m\). A non-trivial null space means two inputs share an output, so it is not injective — and a singular matrix is exactly a non-injective linear map. “Not identifiable” and “not injective” are the same statement.
3.7 Composition and inverses
Composition applies one function to the result of another:
\[ (f \circ g)(x) = f(g(x)) \]
Read “\(f\) after \(g\)” — and note the order, since \(g\) runs first despite being written second. Composition is associative but not commutative, exactly like matrix multiplication (Section 5.10), and for the same reason: matrices are functions, and \(\mathbf{A}\mathbf{B}\) is composition.
g <- function(x) x + 1
fg <- function(x) f(g(x)) # square after adding 1
gf <- function(x) g(f(x)) # add 1 after squaring
c(fg = fg(3), gf = gf(3))fg gf
16 10 \((3+1)^2 = 16\) against \(3^2 + 1 = 10\). Order matters.
The inverse \(f^{-1}\) undoes \(f\):
\[ f^{-1}(f(x)) = x \qquad \text{and} \qquad f(f^{-1}(y)) = y \]
WarningWatch out
\(f^{-1}\) means the inverse function, not the reciprocal. \(\sin^{-1}(x)\) is arcsine, not \(1/\sin(x)\). But \(\sin^2(x)\) does mean \((\sin x)^2\). The superscript changes meaning at \(-1\), which is indefensible and universal.
NoteIn machine learning
Composition is the entire architecture of a neural network: a network of \(L\) layers is \(f_L \circ f_{L-1} \circ \cdots \circ f_1\). The chain rule (Section 11.6) is the statement about how to differentiate a composition, and backpropagation is that rule applied down the stack — which is why Section 13.8 is a short chapter rather than a new idea.
3.8 Function families you will meet
A small vocabulary covers most of applied mathematics.
| Family | Form | Where it shows up |
|---|---|---|
| Linear | \(f(x) = ax\) | passes through the origin |
| Affine | \(f(x) = ax + b\) | regression; usually called “linear” anyway |
| Polynomial | \(f(x) = \sum_k c_kx^k\) | Taylor approximation, basis expansion |
| Exponential | \(f(x) = e^x\) | growth, decay, likelihoods |
| Logarithm | \(f(x) = \log x\) | inverse of \(e^x\); turns products into sums |
| Logistic | \(f(x) = \frac{1}{1+e^{-x}}\) | squashing a real number into \((0,1)\) |
| ReLU | \(f(x) = \max(0, x)\) | neural network activations |
WarningWatch out
\(f(x) = ax + b\) is affine, not linear — a linear function must satisfy \(f(cx) = cf(x)\), and the intercept breaks that: \(f(0) = b \neq 0\). Everyone calls linear regression “linear” regardless. The distinction matters in Section 5.10, where a genuinely linear map must fix the origin.
Also: in this book and in R, \(\log\) means the natural logarithm, base \(e\). Use log10() or log2() when you want otherwise.
Growth rates are the reason these particular families matter, and they are wildly different.
draw_fun(
list(
`exp(x)` = exp,
`x` = function(x) x,
`log(x)` = log
),
from = 0.1,
to = 3,
ylab = "f(x)"
)The logistic function deserves its own look, because it is how a model turns an unbounded score into a probability.
logistic <- function(x) 1 / (1 + exp(-x))
draw_fun(logistic, from = -6, to = 6, ylab = "logistic(x)")At \(x=0\) it gives exactly \(0.5\); it is symmetric, so \(\text{logistic}(-x) = 1 - \text{logistic}(x)\). Its inverse is the logit, \(\log\frac{p}{1-p}\), which is the link function of logistic regression.
3.9 Indicator and piecewise functions
A piecewise function uses different rules on different parts of its domain:
\[ |x| = \begin{cases} x & x \geq 0 \\ -x & x < 0 \end{cases} \qquad \text{ReLU}(x) = \max(0, x) = \begin{cases} x & x > 0 \\ 0 & x \leq 0 \end{cases} \]
The corner at the origin is not a flaw. It is the source of both ReLU’s usefulness and its awkwardness: the function is continuous but has no derivative at \(0\), which Section 11.2 explains and which every deep learning framework quietly patches by defining the derivative there to be 0.
The indicator function returns 1 when a condition holds and 0 otherwise:
\[ \mathbf{1}\{x > 0\} = \begin{cases} 1 & x > 0 \\ 0 & \text{otherwise} \end{cases} \]
It is the bridge between logic and arithmetic, letting you write “count the cases where” as a sum:
\[ \#\{i : y_i = 1\} = \sum_{i=1}^{n}\mathbf{1}\{y_i = 1\} \]
In R, logical values become 1 and 0 the moment you do arithmetic on them:
That last line is worth noticing: a mean of indicators is a proportion, and it is the same identity that makes accuracy, error rate, and empirical probability all the same computation.
3.10 Summary
| Concept | Notation | Key point |
|---|---|---|
| Element of | \(x \in A\) | — |
| Set builder | \(\{x : P(x)\}\) | “:” is “such that” |
| Union, intersection | \(A \cup B\), \(A \cap B\) | or, and |
| Cartesian product | \(A \times B\) | ordered pairs; builds \(\mathbb{R}^n\) |
| Function | \(f: A \to B\) | each input, exactly one output |
| Range vs codomain | — | range is what is actually achieved |
| Bijective | — | invertible |
| Composition | \(f \circ g\) | \(g\) runs first |
| Indicator | \(\mathbf{1}\{\cdot\}\) | mean of indicators is a proportion |
3.11 Exercises
1. With \(A = \{1,2,3,4,5\}\) and \(B = \{4,5,6\}\), compute \(A \cup B\), \(A \cap B\), \(A \setminus B\) and \(B \setminus A\).
TipSolution
$union
[1] 1 2 3 4 5 6
$intersect
[1] 4 5
$A_minus_B
[1] 1 2 3
$B_minus_A
[1] 6Note \(A \setminus B \neq B \setminus A\) — set difference is not symmetric, just as subtraction is not.
2. Give the domain and range of \(f(x) = 1/(x-2)\).
TipSolution
Domain: all reals except 2, written \(\mathbb{R} \setminus \{2\}\) — at \(x = 2\) the expression is undefined.
Range: all reals except 0, since \(1/(x-2)\) can be made arbitrarily large or small but never equals zero.
A function’s domain is part of its definition, not an afterthought. Handing this function \(x = 2\) is not a rounding problem, it is a category error.
3. Is \(f(x) = x^3\) injective on \(\mathbb{R}\)? Is \(f(x) = x^2\)? What about \(x^2\) on \([0, \infty)\)?
TipSolution
\(x^3\) is injective: it is strictly increasing, so distinct inputs always give distinct outputs. It is also surjective onto \(\mathbb{R}\), hence bijective and invertible — the cube root.
\(x^2\) on \(\mathbb{R}\) is not injective, since \(f(-2) = f(2) = 4\).
\(x^2\) on \([0,\infty)\) is injective, and surjective onto \([0,\infty)\). Restricting the domain repaired it, which is exactly how \(\sqrt{\cdot}\) is defined.
4. With \(f(x) = 2x\) and \(g(x) = x + 3\), compute \((f \circ g)(1)\) and \((g \circ f)(1)\).
TipSolution
\((f \circ g)(1) = f(4) = 8\). \((g \circ f)(1) = g(2) = 5\).
f2 <- function(x) 2 * x
g2 <- function(x) x + 3
c(f_after_g = f2(g2(1)), g_after_f = g2(f2(1)))f_after_g g_after_f
8 5 Composition is not commutative — the same reason \(\mathbf{A}\mathbf{B} \neq \mathbf{B}\mathbf{A}\).
5. Verify numerically that the logit and the logistic are inverses, and that \(\text{logistic}(-x) = 1 - \text{logistic}(x)\).
TipSolution
6. Using an indicator, write the classification error rate of predictions yhat against truth y as a single expression, and compute it.
TipSolution
\[ \text{error} = \frac{1}{n}\sum_{i=1}^{n}\mathbf{1}\{\hat{y}_i \neq y_i\} \]
Two mistakes out of six. The indicator turned a logical question into arithmetic, and mean() of a logical vector does the sum and the division in one step.