0. Mathematical Language, Proofs & Limits
Sets, quantifiers, functions, proof techniques, limits, suprema, compactness and O-notation
Start here with ordinary arithmetic and school algebra. The reminders below help you recover the rest:
- Signed numbers, fractions, powers and solving simple equations: start with the warm-up.
- Reading a function such as $f(x)=x^2$: refreshed in Section 2.
- Finite sums and limits: introduced with examples in Section 4.
- Vector and derivative notation occurs in later applications. You can follow the scalar examples first; Primer A and Primer B include first-course refreshers before using those tools.
No earlier primer is needed. Read Sections 1–3 in order; return to the application boxes after the definitions feel familiar.
Book contents · Apply this chapter to a real decision · Glossary
The modules speak the language of analysis: "for every state in $C$ there exists an input", "$\sup_x\|J_f(x)\|$", "a compact sublevel set", "regret $O(\sqrt T)$". This primer makes that language precise and trains the proof patterns the modules repeat: induction over time steps, chains of inequalities, geometric series, and contradiction plus compactness.
All seven sections have local graded practice: 39 exercises in total, plus seven mixed review exercises below. Sections 1–3 offer three questions at each difficulty; Sections 4–7 offer an Easy, Medium and Hard sequence. Easy refreshes notation and calculations; Medium applies a definition or proof technique; Hard combines ideas and checks assumptions. Each exercise has a separate hint and a full worked answer.
Start with the Easy exercises in one section. Try each question before opening its hint, and write your reasoning before checking the answer. After checking, close the answer and try the question again from memory.
Jump to sets & logic, functions & fixed points, proofs, sequences, bounds, topology, or rates.
Warm-up: the algebra behind the examples
If a calculation is slowing you down, rebuild it one operation at a time. The examples below are enough to start the set and function exercises; you do not need calculus for Sections 1–3.
Signs and squares: $(-3)^2=(-3)(-3)=9$, whereas $-3^2=-(3^2)=-9$. Absolute value discards the sign: $|-3|=3$. Thus the distance between $-2$ and $1$ is $|-2-1|=3$.
Fractions: $\tfrac12+\tfrac13=\tfrac36+\tfrac26=\tfrac56$. Dividing by a nonzero fraction multiplies by its reciprocal: $2/(1/2)=4$. For $t\ge0$, $1/(t+1)$ is defined and positive; increasing its denominator decreases the value.
Powers: $2^{-3}=1/2^3=1/8$, $a^{m+n}=a^ma^n$, and $a^0=1$ for $a\ne0$. In particular, $0.5^0+0.5^1+0.5^2=1+1/2+1/4=7/4$. The index under a summation sign tells you where to start: $\sum_{t=0}^{2}0.5^t$ means precisely those three terms.
Equations and inequalities: $2x+1=5$ gives $2x=4$ and then $x=2$. Subtracting the same quantity from both sides preserves an inequality. Multiplying or dividing by a negative number reverses it: $-2x\le4$ gives $x\ge-2$. Hence $x^2\le4$ means $-2\le x\le2$, with both signs included.
A quick self-check: before closing this box, reconstruct $(-2)^2=4$, $\tfrac14+\tfrac12=\tfrac34$, $2^{-2}=\tfrac14$ and $-3x\gt6\iff x\lt-2$. If one line is unfamiliar, use its rule on a new number and check by substitution.
1. Sets, Quantifiers & Logic
Every safety statement in the modules has the same grammar: a set of states or parameters, a test its points must pass, and quantifiers saying whether one point, every point or every time step must pass it.
Example. For $h(x)=1-x_1^2-x_2^2$ the safe set $C=\{x\in\mathbb R^2:h(x)\ge0\}$ is the closed unit disc. $(0.6,0.8)\in C$, since $h=1-0.36-0.64=0$ (it lies on the edge), while $(1,1)\notin C$, since $h=-1$. Also $C\subseteq[-1,1]^2$, because $x\in C$ forces $x_i^2\le1$; the reverse inclusion fails, as $(1,1)$ shows.
Example. With $D=\{1,\dots,6\}$, $S=\{2,3\}$, $T=\{3,4,5\}$: $S\cup T=\{2,3,4,5\}$, $S\cap T=\{3\}$, $|D\setminus S|=|\{1,4,5,6\}|=4$, and $S\times\{1,2\}$ has $4$ pairs. Several constraints form an intersection, $\bigcap_i\{a: g_i(a)\ge0\}$; "a failure at some $t\le T$" is a union, $\bigcup_{t=0}^{T}\{x_t\notin C\}$.
Statements and implications
Intuition and example. An implication is a promise, broken only when $P$ holds and $Q$ fails; if $P$ never holds it is vacuously true, so a condition checked on an empty set certifies nothing. "$x\gt2\Rightarrow x^2\gt4$" is true; its converse is false ($x=-3$); its contrapositive "$x^2\le4\Rightarrow x\le2$" is true. Module 14 requires $\big(D(\xi)\le0\ \wedge\ f_{\rm cl}(\xi)\in\mathcal B\big)\vee V(\xi)\ge\rho$ for all $\xi\in\mathcal B$, with $D(\xi)\le0$ a decrease condition on $V$ (the module writes $F$). Since $P\vee Q\equiv(\neg Q\Rightarrow P)$: whenever $V(\xi)\lt\rho$, $V$ decreases and the successor $f_{\rm cl}(\xi)$ stays in $\mathcal B$.
Quantifiers, negation, and why their order matters
Intuition. In "$\forall x\ \exists y: P(x,y)$" you may answer each $x$ with its own $y$; "$\exists y\ \forall x: P(x,y)$" forces one $y$ before seeing $x$. Committing first is harder: $\exists y\,\forall x\,P$ implies $\forall x\,\exists y\,P$, but not conversely. Over $\mathbb R$, "$\forall x\ \exists y: y\gt x$" is true (answer $y=x+1$), while "$\exists y\ \forall x: y\gt x$" claims a largest real number and is false.
A parameter $a$ is certified from evaluated parameters $a'\in S$ through a Lipschitz bound $L$ on constraint functions $g_i$ (larger is safer). Module 6 compares two rules that differ only in quantifier order (the module also subtracts an accuracy $\epsilon$ and adds $S$ itself):
Take $S=\{0,2\}$, $a=1$, $L=1$ (both witnesses at distance $1$), $g_1(0)=2$, $g_1(2)=0.5$, $g_2(0)=0.5$, $g_2(2)=2$. Witness $0$ certifies constraint $1$ ($2-1\ge0$) but not constraint $2$ ($0.5-1\lt0$), and witness $2$ the opposite. No single witness works, so $a$ fails the first rule, but $a_1'=0$, $a_2'=2$ satisfy the second. Since "$\exists\forall$" implies "$\forall\exists$", the per-constraint rule always certifies at least as much.
With $\mathcal U$ the admissible control signals and $\varphi^u_x(t)$ the state at time $t$ from $x$ under $u$, the viability kernel of Module 7 is $X_V=\{x:\ \exists u\in\mathcal U\ \forall t\ge0:\ \varphi^u_x(t)\notin X_F\}$: some control avoids the failure set $X_F$ forever. Swap the quantifiers and negate the inside: $X\setminus X_V=\{x:\ \forall u\in\mathcal U\ \exists t\ge0:\ \varphi^u_x(t)\in X_F\}$, every control fails at some time, which is the unviability kernel $X_U$ of Module 1. The failure time $t$ may depend on $u$.
Order inside probabilities. "$\forall t:\ \mathbb P(x_t\in C)\ge1-\delta$" is much weaker than "$\mathbb P(\forall t:\ x_t\in C)\ge1-\delta$": with independent $5\%$ failure chances per step, all $20$ steps are safe only with probability $0.95^{20}\approx0.358$. The union bound $\mathbb P(\exists t\le T: x_t\notin C)\le\sum_{t=0}^{T}\delta_t$ connects the two (Primer C).
Reading aids. "Iff" (if and only if): prove both directions. "Without loss of generality" (WLOG): a reduction that loses no cases, by symmetry or by a change of variables. For example, an equilibrium $x^\ast$ of $x_{t+1}=F(x_t)$ is moved to the origin by $z=x-x^\ast$ and $\tilde F(z)=F(z+x^\ast)-x^\ast$, which gives $\tilde F(0)=0$; hence "WLOG $x^\ast=0$", provided constraint sets and functions such as $V$ are shifted too. "s.t." means "such that", or "subject to" in optimization.
Practice: Sets, Quantifiers & Logic
Start by listing elements and reading symbols aloud. The Medium exercises ask you to translate statements; the Hard exercises combine quantifiers with constraints. If a definition feels unfamiliar, revisit this section before trying again.
Exercise 0.S1 — Easy: Read a set-builder expression
Let $X=\{-2,-1,0,1,2,3\}$, $A=\{x\in X:x^2\le4\}$, and $B=\{x\in X:x\gt0\}$. List $A$ and $B$. Is $2\in A$? Is $B\subseteq A$? Give a reason for each answer.
Show hint
Show answer
$A=\{-2,-1,0,1,2\}$: their squares are $4,1,0,1,4$, while $3^2=9\gt4$. The positive elements give $B=\{1,2,3\}$.
Yes, $2\in A$, because $2^2=4\le4$. But $B\not\subseteq A$: $3\in B$ and $3\notin A$. Notice the difference between membership ($2\in A$) and inclusion (one set inside another).
Exercise 0.S2 — Easy: Union, intersection, difference and complement
Use the universe $X=\{0,1,2,3,4,5\}$ and sets $A=\{0,2,4\}$, $B=\{2,3,4\}$. Compute $A\cup B$, $A\cap B$, $A\setminus B$, and $A^c$.
Show hint
Show answer
$A\cup B=\{0,2,3,4\}$: collect every element that appears in either list, counting repeats once. $A\cap B=\{2,4\}$: these appear in both.
$A\setminus B=\{0\}$: start with $A$ and remove $2,4$, which also belong to $B$. Finally $A^c=X\setminus A=\{1,3,5\}$. Complements depend on the universe: this complement contains only elements of $X$, not every real number outside $A$.
Exercise 0.S3 — Easy: True or false, with a witness
Decide whether each statement is true. Explain a true universal statement, give a witness for a true existential statement, and explain why a false statement fails.
- $\forall x\in\mathbb R:\ x^2\ge0$.
- $\exists x\in\mathbb R:\ x^2=-1$.
- For every real $x$ there is a real $y$ with $y=x+2$.
- There is one real $y$ such that $y=x+2$ for every real $x$.
Show hint
Show answer
- True: a real number times itself is nonnegative, including $0^2=0$.
- False: the first fact rules out a negative square.
- True: for any given $x$, choose $y=x+2$. This is a real number and satisfies the required equation.
- False: whatever $y$ was chosen, the allowed choice $x=y$ would require $y=y+2$, hence $0=2$. A witness that can depend on $x$ need not work for every $x$ at once.
Exercise 0.S4 — Medium: Negate every quantifier
Negate both statements, keeping the domains unchanged. Then decide whether the original statements are true.
- $\forall x\in\mathbb R:\ x^2\ge1$.
- There exists $x\in[0,1]$ such that $x\gt y$ for every $y\in[0,1]$.
Show hint
Show answer
For (1), the negation is “there exists $x\in\mathbb R$ with $x^2\lt1$”. Take $x=0$: $0^2=0\lt1$, so the original is false.
For (2), the negation is “for every $x\in[0,1]$ there exists $y\in[0,1]$ with $x\le y$”. Choose $y=x$ for each $x$. This proves the negation, so the original is false: no point is strictly greater than itself. Both the quantifier order and the inequality changed.
Exercise 0.S5 — Medium: Converse, contrapositive and necessary conditions
For real $x$, consider $P$: “$x\gt3$” and $Q$: “$x^2\gt9$”. Write and assess $P\Rightarrow Q$, its converse, and its contrapositive. In the original implication, is $P$ necessary or sufficient for $Q$? What is $Q$ for $P$?
Show hint
Show answer
The original is $x\gt3\Rightarrow x^2\gt9$, which is true: both numbers are positive and squaring preserves their order.
The converse is $x^2\gt9\Rightarrow x\gt3$. It is false: $x=-4$ has square $16\gt9$ but is not greater than $3$.
The contrapositive is $x^2\le9\Rightarrow x\le3$. It is true, because the premise gives $-3\le x\le3$. Thus $P$ is sufficient for $Q$, and $Q$ is necessary for $P$. The false converse shows that $P$ is not necessary for $Q$.
Exercise 0.S6 — Medium: An infinite union and intersection
For each integer $k\ge1$, let $A_k=[-1/k,1/k]$. Find $\bigcup_{k\ge1}A_k$ and $\bigcap_{k\ge1}A_k$. Justify why no nonzero real number lies in the intersection.
Show hint
Show answer
The union is $[-1,1]$: $A_1=[-1,1]$ already supplies every point in it, and every $A_k$ is contained in $A_1$.
The intersection is $\{0\}$. First, $0\in A_k$ for every $k$. Now let $x\ne0$. Choose an integer $k\gt1/|x|$; then $1/k\lt|x|$, so $x\notin A_k$. Membership in the intersection requires membership in every interval, so that one failure excludes $x$.
Exercise 0.S7 — Hard: Prove De Morgan’s law for an interval
In the universe $\mathbb R$, set $A=\{x:x\ge-1\}$ and $B=\{x:x\le2\}$. Find $(A\cap B)^c$. Prove that it equals $A^c\cup B^c$ by following an arbitrary real $x$ through the membership conditions.
Show hint
Show answer
$A\cap B=[-1,2]$, so its complement is $(-\infty,-1)\cup(2,\infty)$. The endpoints $-1$ and $2$ belong to the intersection and are excluded from its complement.
This holds for every real $x$, so the two sets contain exactly the same elements and are equal.
Exercise 0.S8 — Hard: One input per state or one input for all states
Let $X=\{a,b,c\}$ be states and $U=\{L,R\}$ be inputs. A pair is safe exactly when it belongs to $S=\{(a,L),(b,R),(c,L),(c,R)\}$. Decide whether each statement is true:
- For every $x\in X$ there exists $u\in U$ with $(x,u)\in S$.
- There exists $u\in U$ such that $(x,u)\in S$ for every $x\in X$.
Negate statement (1) and assess its negation.
Show hint
Show answer
State $a$ permits only $L$, state $b$ only $R$, and state $c$ both. Statement (1) is true: use $L$ at $a$, $R$ at $b$, and, for example, $L$ at $c$.
Statement (2) is false. Input $L$ fails at $b$, while $R$ fails at $a$; these are all the possible inputs.
The negation of (1) is “there exists $x\in X$ such that for every $u\in U$, $(x,u)\notin S$”. It is false: every state has at least one permitted input. Failure of a single shared input does not mean some state has no input.
Exercise 0.S9 — Hard: Find the parameter range for a quantified claim
Let $a\ge0$, $C=[-1,1]$, and $U=[-a,a]$. An input $u$ cancels a state $x$ when $x+u=0$. For which $a$ is it true that every $x\in C$ has a cancelling $u\in U$? For which $a$ can one fixed $u\in U$ cancel every $x\in C$? Prove both answers.
Show hint
Show answer
The first claim holds exactly when $a\ge1$. Necessity: at $x=1$ cancellation requires $u=-1$, which lies in $[-a,a]$ only if $a\ge1$. Sufficiency: if $a\ge1$, for any $x\in[-1,1]$ choose $u=-x$. Then $|u|=|x|\le1\le a$, so $u\in U$, and $x+u=0$.
The shared-input claim is false for every $a\ge0$, however large. Cancelling $x=1$ requires $u=-1$, while cancelling $x=-1$ requires $u=1$. One real input cannot equal both.
2. Functions, Maps & Fixed Points
Controllers, networks, Bellman operators and SafeOpt's set expansion are functions, and many safety objects are their fixed points.
Intuition and example. The image collects outputs, the preimage the inputs that land in $B$. Safe sets and sublevel sets are preimages: $C=\{x:h(x)\ge0\}=h^{-1}([0,\infty))$, the zero level set is $h^{-1}(\{0\})$, and $\mathcal V(c)=\{x:V(x)\le c\}=V^{-1}((-\infty,c])$. For $f(x)=x^2$: $f([-1,2])=[0,4]$, $f^{-1}([1,4])=[-2,-1]\cup[1,2]$, $f^{-1}([-3,-1])=\emptyset$, and $f^{-1}(\{1\})=\{-1,1\}$, although $f$ has no inverse.
Injective, surjective, inverse. $f:X\to Y$ is injective if $f(x)=f(x')\Rightarrow x=x'$, surjective if $\forall y\ \exists x: f(x)=y$, and bijective if both; then an inverse $f^{-1}:Y\to X$ with $f^{-1}(f(x))=x$ and $f(f^{-1}(y))=y$ exists. $2x+1$ is bijective on $\mathbb R$; $x^2$ is neither on $\mathbb R$, but bijective on $[0,\infty)$ with inverse $\sqrt y$; $x\mapsto Ax$ is bijective iff $A$ is square and invertible. Strictly increasing functions are injective, which is why Module 5 can invert a continuity modulus $\phi$. Pitfall: $f^{-1}(B)$ of a set is a preimage and always exists; $f^{-1}(y)$ of a point needs a bijection.
Examples. Admissible inputs of a safety filter, a GP confidence interval $x\mapsto[\mu_t(x)\pm\beta_t\sigma_t(x)]$, successor sets $\{f(x,u):u\in U\}$. The sign relation $\{(a,1):a\gt0\}\cup\{(0,b):|b|\le1\}\cup\{(a,-1):a\lt0\}$ is monotone but, with its vertical segment, not a function. Used in Module 10, Module 12 (activations replaced by $\Delta v\mapsto\{D\Delta v: D\text{ diagonal, entries in }[\alpha,\beta]\}$) and Module 14 (monotone relations).
Fixed points and contractions
Intuition and example. In one dimension fixed points are where the graph of $g$ crosses the diagonal $y=x$; the iteration walks a staircase ("cobweb") between graph and diagonal, which a contraction pulls into the crossing (see the explorer). For $g(x)=0.5x+1$, solving $x=0.5x+1$ gives $x^\ast=2$. From $x_0=0$: $x_1=1$, $x_2=1.5$, $x_3=1.75$, $x_4=1.875$; the errors $2,1,0.5,0.25,0.125$ halve because $|g(x)-g(y)|=0.5|x-y|$. This is value iteration $V_{k+1}=1+\gamma V_k$ for one state with reward $1$ and $\gamma=0.5$: the iterates are the partial sums $1+\gamma+\dots+\gamma^{k-1}$ of Section 4, with limit $1/(1-\gamma)$.
Conclusion. $g$ has exactly one fixed point $x^\ast\in X$, the iterates converge to it from every $x_0\in X$, and for all $k$
Why each assumption matters. $L\lt1$: $g(x)=x+1$ ($L=1$) has no fixed point, and $g(x)=-x$ ($L=1$) makes $x_0,-x_0,x_0,\dots$ oscillate. Self-map: $g(x)=x/2+1$ contracts on $[0,1]$ but its fixed point $2$ lies outside. Closedness: $g(x)=x/2$ maps $(0,1]$ into itself, yet the iterates tend to $0\notin(0,1]$. It holds in every complete normed space (Primer A), e.g. for value functions.
Proof of uniqueness and of the first bound. If $g(x^\ast)=x^\ast$ and $g(y^\ast)=y^\ast$, then $\|x^\ast-y^\ast\|=\|g(x^\ast)-g(y^\ast)\|\le L\|x^\ast-y^\ast\|$, so $(1-L)\|x^\ast-y^\ast\|\le0$ and $x^\ast=y^\ast$. Also $\|x_k-x^\ast\|=\|g(x_{k-1})-g(x^\ast)\|\le L\|x_{k-1}-x^\ast\|$, and $k$ repetitions give $L^k\|x_0-x^\ast\|$. $\blacksquare$ Existence and the a priori bound need limits and the geometric series: walkthrough in Section 4.
Monotone set operators and their limits
(a) If $S_0\subseteq\Phi(S_0)$, then $S_0\subseteq S_1\subseteq\cdots$ with at most $|D|-|S_0|$ strict increases, and the final set $\bar S$ is the least fixed point containing $S_0$.
(b) If $\Phi(X^0)\subseteq X^0$, then $X^0\supseteq X^1\supseteq\cdots$ with at most $|X^0|$ strict decreases, and the final set is the greatest fixed point contained in $X^0$.
Proof of (a). If $S_{k-1}\subseteq S_k$, monotonicity gives $S_k=\Phi(S_{k-1})\subseteq\Phi(S_k)=S_{k+1}$, so by induction the sets grow. Each strict increase adds one of the $|D|-|S_0|$ points outside $S_0$. Once $S_{k+1}=S_k$, all later sets are equal and $\Phi(\bar S)=\bar S$. If $T\supseteq S_0$ is a fixed point, $S_k\subseteq T$ implies $S_{k+1}=\Phi(S_k)\subseteq\Phi(T)=T$, so $\bar S\subseteq T$. (b) reverses the inclusions. $\blacksquare$
Worked example (SafeOpt's reachable set, Module 4). Grid $D=\{0,\dots,8\}$, distance $|x-x'|$, Lipschitz constant $L=1$, threshold $h=0$ (safe means $f(x)\ge0$), no estimation error. The operator $R(S)=S\cup\{x\in D:\ \exists x'\in S:\ f(x')-L|x-x'|\ge h\}$ certifies $x$ through a witness whose value exceeds the threshold by $L$ times the distance; it is monotone and $S\subseteq R(S)$. With $f=(1.8,\,2.3,\,1.4,\,2.4,\,1.4,\,2.4,\,1.4,\,0.4,\,1.4)$ (consecutive values differ by at most $1$, so $f$ is $1$-Lipschitz) and $S_0=\{0\}$:
| $k$ | $S_k$ | new points (witness check) |
|---|---|---|
| 1 | $\{0,1\}$ | $1$ from $x'=0$: $1.8-1\ge0$ |
| 2 | $\{0,\dots,3\}$ | $2,3$ from $x'=1$: $2.3-2\ge0$ |
| 3 | $\{0,\dots,5\}$ | $4,5$ from $x'=3$: $2.4-2\ge0$ |
| 4 | $\{0,\dots,7\}$ | $6,7$ from $x'=5$: $2.4-2\ge0$ |
| 5 | $\{0,\dots,7\}$ | none: the fixed point $\bar R(S_0)$ |
Four strict increases, well within $|D|-|S_0|=8$. Point $8$ is safe ($f(8)=1.4$) but unreachable: every witness fails, e.g. $0.4-1\lt0$ from $7$ and $2.4-3\lt0$ from $5$. This is remark (ii) of Module 4. Shrinking iterations compute viability kernels: $X^0=X\setminus X_F$, $X^{k+1}=X^k\cap\operatorname{Pre}(X^k)$ keeps the states from which some input stays in the current set; by (b) it stops at the largest $Y\subseteq X\setminus X_F$ with $Y\subseteq\operatorname{Pre}(Y)$. Game and shield papers write greatest fixed points as $\nu X.(\cdots)$, least ones as $\mu X.(\cdots)$. Reachability in a directed graph is the least fixed point of $X\mapsto S\cup\operatorname{Post}(X)$, found by breadth-first search (Module 6 adds Dijkstra's shortest paths). Caution: SafeOpt's "closure" is this fixed point, not a topological closure, and on continuous domains the iteration need not stop.
Practice: Functions, Maps & Fixed Points
The Easy exercises refresh function notation and substitution. Medium adds preimages and contraction estimates; Hard asks you to explain which assumptions make an argument work. If a definition feels unfamiliar, revisit this section before trying again.
Exercise 0.F1 — Easy: Domain, codomain and actual outputs
Let $f:X\to Y$ be $f(x)=x^2$, where $X=\{-2,-1,0,1,2\}$ and $Y=\{0,1,4,9\}$. State the domain, codomain and image $f(X)$. Is $f$ injective? Is it surjective onto $Y$?
Review: functions and fixed points
Show hint
Show answer
The domain is $X$ and the codomain is $Y$. Evaluating the five inputs gives $4,1,0,1,4$, so the image is $f(X)=\{0,1,4\}$.
The map is not injective: distinct inputs $-1$ and $1$ both produce $1$. It is not surjective onto $Y$: the declared output $9$ has no preimage in $X$. Being allowed as an output is different from actually being reached.
Exercise 0.F2 — Easy: Compute two compositions
On $\mathbb R$, let $f(x)=2x-1$ and $g(x)=x^2$. Find $(f\circ g)(2)$ and $(g\circ f)(2)$, then write a formula for each composition at a general $x$.
Review: functions and fixed points
Show hint
Show answer
First $g(2)=4$, then $f(4)=7$, so $(f\circ g)(2)=7$. In the other order, $f(2)=3$, then $g(3)=9$, so $(g\circ f)(2)=9$.
The order of composition matters; the two functions are different.
Exercise 0.F3 — Easy: A fixed point and three iterations
Let $g(x)=(x+3)/4$. Solve $g(x^\ast)=x^\ast$. Starting at $x_0=-1$, calculate $x_1,x_2,x_3$ using $x_{k+1}=g(x_k)$. What happens to the distance from the fixed point at each step?
Review: functions and fixed points
Show hint
Show answer
$x^\ast=(x^\ast+3)/4$ gives $4x^\ast=x^\ast+3$, hence $x^\ast=1$.
The distances from $1$ are $2,1/2,1/8,1/32$ for $k=0,1,2,3$. Each is one quarter of the previous distance, since $g(x)-1=(x-1)/4$.
Exercise 0.F4 — Medium: Images and preimages of intervals
For $f:\mathbb R\to\mathbb R$, $f(x)=x^2$, find $f([-3,1])$, $f^{-1}([1,4])$, and $f^{-1}(\{-1\})$. Explain why the preimage notation is meaningful even though this $f$ has no inverse function.
Review: functions and fixed points
Show hint
Show answer
$f([-3,1])=[0,9]$: $0$ is reached at $x=0$, $9$ at $x=-3$, and every value $y\in[0,9]$ is reached by $x=-\sqrt y\in[-3,0]$.
For the second set, $1\le x^2\le4$ means $1\le|x|\le2$, so $f^{-1}([1,4])=[-2,-1]\cup[1,2]$. No real square is $-1$, so $f^{-1}(\{-1\})=\emptyset$.
A preimage is a set of all inputs passing an output test. It does not require a unique input for each output. An inverse function would require that uniqueness and surjectivity; $x^2$ on $\mathbb R$ has neither.
Exercise 0.F5 — Medium: The same formula with four choices of domain and codomain
Classify each map as injective, surjective, both, or neither. All use the formula $f(x)=x^2$.
- $\mathbb R\to\mathbb R$.
- $\mathbb R\to[0,\infty)$.
- $[0,\infty)\to\mathbb R$.
- $[0,\infty)\to[0,\infty)$.
For the bijective map, write its inverse.
Review: functions and fixed points
Show hint
Show answer
- Neither: $f(-1)=f(1)$ prevents injectivity, and no negative output is reached.
- Surjective only: every $y\ge0$ is reached by $x=\sqrt y$, but the repeated inputs $-1,1$ remain.
- Injective only: for nonnegative $x,x'$, $x^2=(x')^2$ implies $x=x'$. Negative outputs in the codomain are still unreachable.
- Both: the two arguments above prove injectivity and surjectivity. The inverse is $f^{-1}(y)=\sqrt y$ on $[0,\infty)$.
Domain and codomain are part of a function’s specification; its formula alone does not determine these properties.
Exercise 0.F6 — Medium: An alternating contraction and an error target
Let $g(x)=-x/2+3$ on $\mathbb R$, and $x_0=0$. Find the fixed point and the first three iterates. Prove that $g$ has contraction factor $1/2$. Use the exact error to find the smallest integer $k\ge0$ for which $|x_k-x^\ast|\le1/100$.
Review: functions and fixed points
Show hint
Show answer
Solving $x^\ast=-x^\ast/2+3$ gives $x^\ast=2$. The iterates are $x_1=3$, $x_2=3/2$, $x_3=9/4$. Also $|g(x)-g(y)|=|x-y|/2$, proving the contraction property.
At $k=7$ the error is $1/64\gt1/100$; at $k=8$ it is $1/128\lt1/100$. Errors decrease each step, so $k=8$ is the first qualifying iteration. A negative slope causes alternation without preventing contraction.
Exercise 0.F7 — Hard: Why images do not preserve intersections
For $f(x)=x^2$, $A=\{-2\}$ and $B=\{2\}$, compare $f(A\cap B)$ with $f(A)\cap f(B)$. Then prove that for any injective function $f:X\to Y$ and any $A,B\subseteq X$, these two sets are equal.
Review: functions and fixed points
Show hint
Show answer
Here $A\cap B=\emptyset$, so $f(A\cap B)=\emptyset$. But $f(A)=f(B)=\{4\}$, making $f(A)\cap f(B)=\{4\}$. Different inputs produced the same output.
For any function, if $y\in f(A\cap B)$, there is an $x\in A\cap B$ with $f(x)=y$. Thus $y$ belongs to both $f(A)$ and $f(B)$; this proves one inclusion.
Conversely, suppose $y\in f(A)\cap f(B)$. There are $a\in A$ and $b\in B$ with $f(a)=y=f(b)$. When $f$ is injective, $a=b$. This common input belongs to $A\cap B$, so $y\in f(A\cap B)$. The reverse inclusion follows, proving equality.
Exercise 0.F8 — Hard: Grow a set until it stops
Let $D=\{0,1,2,3,4\}$, with $F(0)=1$, $F(1)=2$, $F(2)=2$, $F(3)=4$, $F(4)=3$. Define $\Phi(S)=S\cup F(S)$ for $S\subseteq D$, where $F(S)=\{F(x):x\in S\}$. Start with $S_0=\{0\}$ and iterate $S_{k+1}=\Phi(S_k)$. Find the final set, prove $\Phi$ is monotone, and explain why $3,4$ are not added.
Review: functions and fixed points
Show hint
Show answer
Hence $S_2$ is a fixed point of $\Phi$, and all later iterates equal it. There are two strict increases.
If $A\subseteq B$, every input used to form $F(A)$ also belongs to $B$, so $F(A)\subseteq F(B)$. Combining this with $A\subseteq B$ gives $A\cup F(A)\subseteq B\cup F(B)$, proving monotonicity. States $3,4$ form a separate cycle: neither is the successor of $0,1,2$, so neither can be reached from the seed $0$.
Exercise 0.F9 — Hard: Audit the contraction theorem
In each case, say which assumption of the contraction theorem fails and whether a fixed point in $X$ exists.
- $X=(0,1]$, $g(x)=x/2$.
- $X=[0,1]$, $g(x)=x/2+1$.
- $X=[-1,1]$, $g(x)=-x$.
Review: functions and fixed points
Show hint
Show answer
- Closedness fails: $1,1/2,1/4,\dots$ lie in $X$ and tend to $0\notin X$. The map stays in $X$ and contracts by $1/2$, but its only possible fixed point is $0$, so it has none in $X$.
- The self-map assumption fails: $g(1)=3/2\notin X$. It contracts by $1/2$ and $X$ is closed, but its fixed-point equation gives $x=2\notin X$.
- Strict contraction fails: $|g(x)-g(y)|=|x-y|$, so a factor below $1$ cannot work for distinct inputs. The fixed point $0$ exists, but from $1$ the iterates are $1,-1,1,-1,\dots$ and do not converge.
A failed assumption removes the theorem’s guarantee. It does not by itself prove that every part of the conclusion is false.
3. Reading and Writing Proofs
A proof is a chain of statements, each following from assumptions, definitions or earlier steps by a rule you can name.
Step 4 pays off in Module 5: the LoSBO safety proof uses only the Lipschitz constant, the noise bound and the seed, never $\beta_t$, the kernel or the RKHS norm, hence "for any $\beta_t$".
Direct proofs and chains of inequalities
Tools for chains. $\|a+b\|\le\|a\|+\|b\|$ and $\big|\|a\|-\|b\|\big|\le\|a-b\|$; multiplying by $c\ge0$ keeps the direction, by $c\lt0$ flips it; increasing functions ($e^x$, $\ln x$, $\sqrt x$) keep it. One strict link makes the chain strict.
Contrapositive, contradiction, pigeonhole
To prove $P\Rightarrow Q$ one may prove the contrapositive $\neg Q\Rightarrow\neg P$. Example: "if $\|x\|\le\varepsilon$ for every $\varepsilon\gt0$, then $x=0$"; if $x\ne0$, then $\varepsilon=\|x\|/2$ violates the premise. $\blacksquare$ ("To show $a=b$, show $|a-b|\le\varepsilon$ for every $\varepsilon\gt0$" returns in every limit argument.) A proof by contradiction assumes the conclusion false and derives something impossible. The pigeonhole principle is the simplest case: $n+1$ objects in $n$ boxes put two in one box.
Proof. The $|X|+1$ states $x_0,\dots,x_{|X|}$ lie in a set of size $|X|$, so $x_i=x_j$ for some $0\le i\lt j\le|X|$ (pigeonhole). Determinism gives $x_{i+m}=x_{j+m}$ for all $m\ge0$ (induction on $m$), so from time $i$ on the trajectory repeats $x_i,\dots,x_{j-1}$, and $j-1\le|X|-1$. $\blacksquare$
Induction, including induction over time
Induction over time steps proves "safe at every step": safe now, and safe now plus the certificate imply safe next. The walkthrough proves a discrete-time barrier certificate this way and shows the trap to avoid.
Counterexamples and "it suffices to show"
One counterexample disproves a "for all". "Every bounded sequence converges": $(-1)^t$ does not. "A continuous function on a bounded set attains its maximum": $x$ on $(0,1)$ does not. "If $V$ decreases along trajectories, they converge to $0$": Module 11 gives a discontinuous $F$ with $x_t=1+2^{-t}\to1$. "A barrier condition on the boundary suffices": it can fail where $\nabla h=0$ (Module 1; Section 6 below). "It suffices to show $Q$" means that $Q$ implies the goal: to show $A=B$ it suffices to show $A\subseteq B$ and $B\subseteq A$; LoSBO's proof starts "it suffices that $f\ge h$ on every $S_t$", because every query is taken from $S_t$.
Practice: Reading and Writing Proofs
Write a reason beside each step. Easy exercises practise one proof move; Medium builds complete arguments; Hard combines the proof with an audit of its assumptions. If a definition feels unfamiliar, revisit this section before trying again.
Exercise 0.P1 — Easy: A direct proof by completing the square
Prove $x^2+2x+2\ge1$ for every real $x$. When does equality hold? Give a general argument, not just numerical checks.
Show hint
Show answer
The equality is obtained by expanding the square; the inequality uses $(x+1)^2\ge0$ for every real $x$. Equality holds exactly when $x+1=0$, hence when $x=-1$. Because $x$ was arbitrary, this proves the claim for all real inputs.
Exercise 0.P2 — Easy: Prove a contrapositive about even numbers
Let $n$ be an integer. Prove: if $n^2$ is even, then $n$ is even. Use the contrapositive. Recall that an even integer has the form $2m$ and an odd integer the form $2m+1$, for an integer $m$.
Show hint
Show answer
Assume $n$ is odd, so $n=2m+1$ for some integer $m$. Then
The number $2m^2+2m$ is an integer, so the last expression is odd. This proves “$n$ odd implies $n^2$ odd”, the contrapositive of the requested claim. Every integer is even or odd, so these are exactly the required negations.
Exercise 0.P3 — Easy: Disprove three universal claims
Give a counterexample to each claim over real numbers, and explicitly check why it fails.
- For every $x$, $x^2\ge x$.
- If $xy=0$, then both $x=0$ and $y=0$.
- If $x^2=y^2$, then $x=y$.
Show hint
Show answer
- Take $x=1/2$. Its square is $1/4\lt1/2$, contradicting the proposed inequality.
- Take $x=0,y=1$. Their product is $0$, but $y\ne0$, so the premise holds and the conclusion fails.
- Take $x=-1,y=1$. Both squares are $1$, but the numbers differ.
One valid counterexample is enough to refute a universal claim. Many examples where it works would not prove it.
Exercise 0.P4 — Medium: Write an induction proof from start to finish
Prove that $\sum_{j=1}^{n}j=n(n+1)/2$ for every integer $n\ge0$, with the sum at $n=0$ defined to be $0$. State the base case, induction hypothesis, induction step and conclusion explicitly.
Show hint
Show answer
Base case: at $n=0$, the empty sum is $0=0(0+1)/2$.
Induction hypothesis: assume for some $n\ge0$ that the sum through $n$ is $n(n+1)/2$.
Induction step:
The first line separates the final term, the second uses the hypothesis, and the third factors out $n+1$. This is precisely the claimed formula with $n+1$ in place of $n$.
Conclusion: by induction, the formula holds for every integer $n\ge0$.
Exercise 0.P5 — Medium: Repair a proof with a sign mistake
A proposed proof says: “If $a\le b$, multiplying by $a$ gives $a^2\le ab$, and multiplying by $b$ gives $ab\le b^2$. Hence $a^2\le b^2$.” Explain the gap, give a counterexample, and repair the argument under the additional assumption $0\le a\le b$.
Show hint
Show answer
The proof never checks the signs of $a$ and $b$. Its multiplication steps preserve the inequality only when the multiplier is nonnegative. For $a=-3,b=-2$, the premise $-3\le-2$ is true but the conclusion $9\le4$ is false.
Under $0\le a\le b$, both multipliers are nonnegative, so the original two steps are valid. Equivalently, $b^2-a^2=(b-a)(b+a)\ge0$: both factors are nonnegative. Thus $a^2\le b^2$ follows with the added assumption.
Exercise 0.P6 — Medium: Prove that an interval stays invariant
Let $x_{t+1}=x_t/2+1/4$ and $x_0\in C=[0,1]$. First show that any point of $C$ maps back into $C$. Then use induction to prove $x_t\in C$ for all integers $t\ge0$. Where is the assumption on $x_0$ used?
Show hint
Show answer
If $x\in C$, then $0\le x\le1$, so $1/4\le x/2+1/4\le3/4$. Since $[1/4,3/4]\subseteq[0,1]$, the next state belongs to $C$.
For induction, let $P(t)$ mean $x_t\in C$. The base case $P(0)$ is exactly the assumption $x_0\in C$. If $P(t)$ holds, apply the one-step argument at $x=x_t$ to obtain $P(t+1)$. Thus $P(t)$ holds at every time.
Without the initial-state assumption the base case can fail: $x_0=2$ lies outside $C$, and even $x_1=5/4$ is outside.
Exercise 0.P7 — Hard: Prove uniqueness without assuming existence
Let $X$ be a nonempty subset of $\mathbb R$ and $g:X\to X$ satisfy $|g(x)-g(y)|\le |x-y|/3$ for all $x,y\in X$. Prove that $g$ has at most one fixed point. Does your proof also show that a fixed point exists? Give a counterexample if it does not.
Show hint
Show answer
Suppose $g(a)=a$ and $g(b)=b$. Write $d=|a-b|\ge0$. Then
Subtracting $d/3$ gives $2d/3\le0$. Together with $d\ge0$ this forces $d=0$, hence $a=b$.
This proves only that two different fixed points cannot exist. For a counterexample to existence, take $X=(0,1]$ and $g(x)=x/3$. It maps $X$ into itself and has the stated contraction factor, but $x=x/3$ forces $x=0\notin X$. Closedness, an extra hypothesis of the full theorem, is missing.
Exercise 0.P8 — Hard: Remove circular reasoning from a safety proof
Let $C=[-1,1]$ and suppose a map $F:\mathbb R\to\mathbb R$ satisfies $|F(x)|\le(4/5)|x|$ only for $x\in C$. From $x_0\in C$, define $x_{t+1}=F(x_t)$. A proposed proof says: “The trajectory is in $C$, so the bound applies at every step, so the trajectory stays in $C$.” Explain the circularity and replace it with an induction proof of $|x_t|\le(4/5)^t|x_0|$ and $x_t\in C$.
Show hint
Show answer
The proposed proof assumes the all-time membership that it is meant to establish. The hypothesis on $F$ cannot be used outside $C$.
At $t=0$, the quantitative bound is equality, and $|x_0|\le1$ by assumption. For the step, assume $|x_t|\le(4/5)^t|x_0|$. Since $(4/5)^t\le1$, this implies $|x_t|\le1$, so $x_t\in C$ and the bound on $F$ is available. Therefore
This proves the quantitative bound at $t+1$ and membership in $C$ there. Induction proves both claims at every time, without assuming future membership.
Exercise 0.P9 — Hard: When a finite simulation proves an all-time claim
A fixed deterministic map on $X=\{a,b,c,d\}$ has $F(a)=b$, $F(b)=c$, $F(c)=b$, $F(d)=d$. Start at $x_0=a$; state $d$ is failure. List the first five states. Explain why $d$ is never reached. More generally, justify why checking $x_0,\dots,x_3$ suffices for any fixed deterministic map on this four-state set. Can that conclusion fail if the map changes with time?
Show hint
Show answer
The first five states are $a,b,c,b,c$. Once $b$ repeats, its successor is again $c$, whose successor is $b$. Thus the trajectory cycles through $b,c$ and never visits $d$.
For any fixed map on four states, among $x_0,\dots,x_4$ there are indices $0\le i\lt j\le4$ with $x_i=x_j$. Applying the same map gives $x_{i+1}=x_{j+1}$; repeating this argument gives $x_{i+m}=x_{j+m}$ for every $m\ge0$. The trajectory from $i$ therefore cycles through $x_i,\dots,x_{j-1}$. Every state ever visited already appeared by time $j-1\le3$, proving the general claim.
The conclusion can fail with a changing map: let $F_t$ send every state to $a$ for $t=0,1,2$ and to $d$ for $t\ge3$. Starting at $a$, the first four states are all $a$, but $x_4=d$. Repetition alone is insufficient when the future rule changes.
4. Sequences, Limits & Series
Iterates, trajectories and learning curves are sequences; most guarantees concern their limits and rates.
Intuition and example. Whatever tolerance $\varepsilon$ you name, the sequence is eventually within $\varepsilon$ of $a$ and stays there; $T$ may grow as $\varepsilon$ shrinks. $a_t=1/(t+1)\to0$: any integer $T\ge1/\varepsilon$ works, since $t\ge T$ gives $1/(t+1)\le1/(T+1)\lt1/T\le\varepsilon$ ($T=100$ for $\varepsilon=0.01$). $(-1)^t$ has no limit: with $\varepsilon=1$, both $1$ and $-1$ would lie within $1$ of $a$, and then $2\le|1-a|+|a+1|\lt2$.
Rules. Limits respect sums, products and quotients (nonzero denominator limit). $a_t\le b_t$ for all $t$ gives $\lim a_t\le\lim b_t$, but strict inequalities may become equalities ($1/(t+1)\gt0$, limit $0$). Squeeze: $a_t\le c_t\le b_t$ with $a_t,b_t\to\ell$ gives $c_t\to\ell$. Continuity: if $g$ is continuous at $a$ and $a_t\to a$, then $g(a_t)\to g(a)$.
Example (Module 11). If $V\ge0$ and $V(x_{t+1})\le V(x_t)$, then $V(x_t)\to v^\ast\ge0$, but nothing forces $v^\ast=0$ ($1+\frac1{t+1}$ decreases to $1$); that needs compactness and strict decrease (end of Section 6). For $x_{t+1}=x_t/(1+x_t^2)$, $V(x)=x^2$, $x_0=1$, the values (rounded where needed) $1,\ 0.25,\ 0.16,\ 0.119,\ 0.095,\dots$ decrease and converge. Pointwise vs uniform: $f_n\to f$ pointwise if $f_n(x)\to f(x)$ for each $x$ ($T$ may depend on $x$), uniformly if $\sup_x|f_n(x)-f(x)|\to0$; $x^n\to0$ pointwise on $[0,1)$ but not uniformly. On a finite set pointwise implies uniform (take the largest $T$).
Series, the geometric series and discounting
Discounting. If $|r_t|\le R_{\max}$ and $0\le\gamma\lt1$, then $\big|\sum_t\gamma^tr_t\big|\le\frac{R_{\max}}{1-\gamma}$ and the tail from $T$ on is at most $\frac{\gamma^TR_{\max}}{1-\gamma}$; $1/(1-\gamma)$ is the effective horizon ($\gamma=0.99$ counts about $100$ steps).
Example ($\gamma=0.9$). The limit is $10$. With $0.9^{10}\approx0.3487$, the first ten terms give $S_{10}\approx6.513$ and the tail is approximately $3.487$. Capturing $99\%$ needs $\gamma^T\le0.01$, i.e. $T\ge\ln0.01/\ln0.9\approx43.7$: $44$ terms. Because $\ln(1/\gamma)\ge1-\gamma$ (proved below), $T\ge\ln(1/\varepsilon)/(1-\gamma)$ always guarantees $\gamma^T\le\varepsilon$; here it asks for $47$. The explorer's lower panel computes this for any $\gamma$.
If a square matrix has operator norm $\|A\|\lt1$ (Primer A), then $(I-A)^{-1}=\sum_{t\ge0}A^t$: indeed $(I-A)(I+A+\dots+A^{T-1})=I-A^T$ and $\|A^T\|\le\|A\|^T\to0$. For an MDP transition matrix $P_\pi$ (rows sum to $1$, so $\|\gamma P_\pi\|_\infty=\gamma$), $(I-\gamma P_\pi)^{-1}=\sum_t\gamma^tP_\pi^t$ collects the discounted visits: the "Neumann series read along trajectories" of Module 9. Module 11 uses $(I-P)^{-1}=\sum_tP^t$ for transient chains.
Telescoping. $\sum_{t=0}^{T-1}(b_{t+1}-b_t)=b_T-b_0$: intermediate terms cancel in pairs. Since $\frac1{r(r+1)}=\frac1r-\frac1{r+1}$, $\sum_{r=1}^{R}\frac1{r(r+1)}=1-\frac1{R+1}\to1$, which is why a failure probability $\delta'$ can be split into pieces $\delta'/(r(r+1))$ (Module 5). Summing a Lyapunov or dissipation inequality $V(x_{t+1})-V(x_t)\le-\varepsilon\|x_t\|^2$ over $t\lt T$ telescopes the left side, and with $V\ge0$:
Application. For $\varepsilon\gt0$, $\varepsilon\sum_{t\lt T}\|x_t-x_\ast\|^2\le V(x_0)$ for all $T$ gives $x_t\to x_\ast$ by (a) and (c): Step D in Module 14; likewise in Module 11.
A limit and a sum cannot always be exchanged: for $a_{n,t}=1$ if $t=n$ (else $0$), $\lim_n\sum_ta_{n,t}=1$ but $\sum_t\lim_na_{n,t}=0$, although all terms are nonnegative. Two sums, or a sum and an expectation, may be exchanged when the terms are nonnegative (Tonelli), e.g. $\mathbb E\big[\sum_tX_t\big]=\sum_t\mathbb E[X_t]$ for $X_t\ge0$. A limit may be exchanged with a sum or an expectation under domination: $a_{n,t}\to a_t$ with $|a_{n,t}|\le b_t$, $\sum_tb_t\lt\infty$, gives $\sum_ta_{n,t}\to\sum_ta_t$, and $Y_n\to Y$ almost surely (Section 5) with $|Y_n|\le Z$, $\mathbb E[Z]\lt\infty$, gives $\mathbb E[Y_n]\to\mathbb E[Y]$ (dominated convergence; bounded convergence if $Z$ is constant). Nonnegative terms that increase with $n$ are another sufficient condition (monotone convergence).
For discounted sums the geometric tail suffices: if $|r_t|\le R_{\max}$, then $\big|\mathbb E\big[\sum_t\gamma^tr_t\big]-\sum_{t\lt T}\gamma^t\mathbb E[r_t]\big|\le\frac{\gamma^TR_{\max}}{1-\gamma}\to0$, so $\mathbb E\big[\sum_t\gamma^tr_t\big]=\sum_t\gamma^t\mathbb E[r_t]$: "bounded rewards and $\gamma\lt1$ kill the tail" in Module 9, the occupancy measures of Module 8. The CVaR walkthrough of Module 1 differentiates inside an expectation by bounded convergence.
Limits of functions; the exponential and the logarithm
$\lim_{x\to a}f(x)=\ell$ means $\forall\varepsilon\gt0\ \exists\delta\gt0: 0\lt|x-a|\lt\delta\Rightarrow|f(x)-\ell|\lt\varepsilon$, equivalently $f(x_t)\to\ell$ for every sequence $x_t\to a$ with $x_t\ne a$; one-sided limits $x\downarrow a$, $x\uparrow a$ use only $x\gt a$ or $x\lt a$, and $f$ is continuous at $a$ iff $\lim_{x\to a}f(x)=f(a)$.
Consequences. $(1-p)^n\le e^{-pn}$: $n$ independent trials all miss an event of probability $p$ with probability at most $e^{-pn}$ (for $p=0.01$, $n=300$: $0.99^{300}\le e^{-3}$, with $0.99^{300}\approx0.0490$ and $e^{-3}\approx0.0498$), the origin of sample sizes like $\ln(1/\beta)/\varepsilon$ in Module 15. With $x=\gamma$: $\ln(1/\gamma)\ge1-\gamma$, so $\gamma^T\le e^{-(1-\gamma)T}$. A soft maximum becomes a maximum: for $q_1,\dots,q_n$ with maximum $m$ and $\alpha\gt0$, $e^{m/\alpha}\le\sum_ie^{q_i/\alpha}\le n\,e^{m/\alpha}$, so
by the squeeze rule; for $q=(1,\,0.5,\,0.9)$ the soft maximum is approximately $1.921$, $1.032$ and $1.0000005$ at $\alpha=1,\ 0.1,\ 0.01$. This is the temperature limit of entropy-regularised Bellman equations (Module 7, Primer E).
Convergence rates
Reaching $e_k\le\varepsilon$ takes $k\ge\ln(e_0/\varepsilon)/\ln(1/q)$ iterations at a linear rate, growing like $\ln(1/\varepsilon)$, but $k\ge1/\varepsilon^2$ for $1/\sqrt k$. For $\varepsilon=10^{-6}$, $e_0=1$: $20$ iterations at $q=0.5$ against $10^{12}$. On a logarithmic plot a linear rate is a straight line, a sublinear one flattens (see the explorer). Used for geometric Lyapunov decay and interior-point iteration counts $O(\sqrt n\log(1/\varepsilon))$ in Module 2, $O(1/\sqrt T)$ primal-dual rates in Module 8, and gradient descent in Primer B.
With limits and the geometric series, Banach's existence proof (Section 2) takes six steps.
Practice: Sequences, limits and series
Work from Easy to Medium before trying Hard. Use the review link for a missing definition, then try again with the explanation closed.
Exercise 0.4a — Easy: Turn a tolerance into an index
Let $a_t=3/(t+1)$ for integers $t\ge0$. Write the first four terms, state the limit, and find the smallest $T$ such that $|a_t|\lt0.1$ for every $t\ge T$.
Review: Sequences, limits and series
Show hint
Solve $3/(t+1)\lt0.1$ first, then remember that $t$ is an integer and the inequality is strict.
Show worked solution
Compute: substituting $t=0,1,2,3$ gives $3,\ 3/2,\ 1,\ 3/4$. The numerator stays fixed while the denominator grows, so $a_t\to0$.
Solve: the denominator is positive, so multiplying gives $3\lt0.1(t+1)$, hence $t+1\gt30$ and $t\gt29$. Therefore the smallest integer threshold is $T=30$.
Check the quantifier: for every $t\ge30$, $3/(t+1)\le3/31\approx0.09677\lt0.1$. The preceding term is $a_{29}=0.1$, so $T=29$ fails the strict inequality.
Exercise 0.4b — Medium: Bound the part of a return you have not summed
With discount $\gamma=1/2$ and rewards $|r_t|\le2$, bound the absolute infinite return. Compute the first four terms and the omitted tail when $r_t=2$ always. What is the smallest number $T$ of terms guaranteeing a tail at most $0.01$ for every permitted reward sequence?
Review: Sequences, limits and series
Show hint
The first $T$ terms have indices $0,\dots,T-1$; the tail bound is $2\gamma^T/(1-\gamma)$.
Show worked solution
Infinite bound: the triangle inequality gives $|\sum_{t\ge0}2^{-t}r_t|\le2\sum_{t\ge0}2^{-t}=2/(1-1/2)=4$. Constant rewards $2$ attain this bound.
Four terms: $2+1+1/2+1/4=15/4=3.75$. The exact tail is $4-3.75=1/4$; the formula also gives $4\cdot2^{-4}=1/4$.
Accuracy: require $4\cdot2^{-T}\le0.01$, or $2^T\ge400$. Since $2^8=256\lt400\le512=2^9$, $T=9$. At $T=8$ the worst tail is $0.015625$; at $T=9$ it is $0.0078125$. This is an absolute error target, not a percentage of the return.
Exercise 0.4c — Hard: Extract convergence from a telescoping inequality
Suppose $V_t\ge0$, $V_0=3$, and $V_{t+1}-V_t\le-\tfrac12\|x_t\|^2$ for every $t\ge0$. Prove $x_t\to0$. Bound the total number of indices with $\|x_t\|\ge0.2$. Does this give a time after which all such indices have disappeared?
Review: Sequences, limits and series
Show hint
Sum through $t=T-1$. Every index above the threshold contributes at least $0.2^2$ to the sum of squared norms.
Show worked solution
Telescope: adding the inequalities cancels all intermediate $V_t$ and gives $\tfrac12\sum_{t=0}^{T-1}\|x_t\|^2\le V_0-V_T\le3$. Thus every partial sum is at most $6$.
Conclude convergence: these partial sums are nondecreasing and bounded, so the nonnegative series $\sum_t\|x_t\|^2$ converges. Its terms must tend to $0$; taking square roots gives $\|x_t\|\to0$, which means $x_t\to0$.
Count excursions: each index with $\|x_t\|\ge0.2$ costs at least $0.04$ of the budget $6$, so there are at most $6/0.04=150$ such indices over all time.
Interpret the limit: only finitely many excursions means there is a last one, but the budget does not tell us its index. A single excursion could occur arbitrarily late while spending only $0.04$. A numerical time bound needs more information about the dynamics.
5. Supremum, Infimum & Bounds
Worst cases over infinite sets (largest gradient, worst disturbance, best policy) are suprema; unlike maxima they always exist, possibly as $\pm\infty$.
Intuition and examples. A supremum is a ceiling you can approach but may never touch: $[0,1)$ has supremum $1$ and no maximum. $\sup_{r\ge0}(1-e^{-r})=1$ is not attained (a bounded continuity modulus in Module 5), while $\sup_xe^{-x^2}=1$ is a maximum. The Lipschitz constant $L^\star(f)=\sup_{x\ne y}|f(x)-f(y)|/|x-y|$ of $\sin$ is $1$, approached as $x,y\to0$ but never attained. To prove $\sup A=s$, show that $s$ is an upper bound and find $a_n\in A$ with $a_n\to s$.
Example. SafeOpt starts from $C_0(x)=[h,\infty)$ on the seed, so $l_0(x)=h$ and $u_0(x)=+\infty$, and from $C_0(x)=\mathbb R$ elsewhere ($l_0=-\infty$). If data contradict an earlier band, $C_t(x)=\emptyset$, and the conventions would give $l_t=+\infty\gt u_t=-\infty$; Module 4 treats this as a failed confidence event or numerical error, not as a certificate; one empty intersection alone does not prove that the assumptions are false.
Proofs. (2) "$\le$": $a+b\le\sup A+\sup B$. "$\ge$": pick $a\gt\sup A-\frac\varepsilon2$, $b\gt\sup B-\frac\varepsilon2$, so $\sup(A+B)\gt\sup A+\sup B-\varepsilon$ for every $\varepsilon\gt0$. (1) is similar. (3): $f(x)+g(x)\le\sup f+\sup g$ for every $x$; it is strict for $f(x)=x$, $g(x)=-x$ on $[0,1]$ ($0\lt1$). (5): $\inf_x\phi(x,y)\le\phi(x',y)\le\sup_{y'}\phi(x',y')$ for all $x',y$; take $\sup_y$ on the left and $\inf_{x'}$ on the right. $\blacksquare$ For $\phi(x,y)=(x-y)^2$ on $\{0,1\}^2$: $\inf_x\sup_y\phi=1$ but $\sup_y\inf_x\phi=0$.
Limit superior and limit inferior
$\limsup_ta_t:=\lim_{T\to\infty}\sup_{t\ge T}a_t$ and $\liminf_ta_t:=\lim_{T\to\infty}\inf_{t\ge T}a_t$ always exist in $\overline{\mathbb R}$, because $\sup_{t\ge T}a_t$ is nonincreasing and $\inf_{t\ge T}a_t$ nondecreasing in $T$; a sequence converges iff they are equal and finite. Example. Let $r_t=1$ if $4^k\le t\lt2\cdot4^k$ for some integer $k\ge0$, else $r_t=0$ ($t\ge1$). The average $\frac1T\sum_{t=1}^{T}r_t$ approaches $\frac23$ at the end of each block of ones and $\frac13$ at the end of each block of zeros: $\liminf=\frac13$, $\limsup=\frac23$, no limit. A long-run constraint $\liminf_T\frac1T\sum_{t\lt T}r_t\ge c$ says that for every $\varepsilon\gt0$ the average is at least $c-\varepsilon$ for all large $T$ (it may stay slightly below $c$ forever, like $c-\frac1T$), whether or not the average settles (Module 8).
Preview: almost everywhere and almost surely
Intuition and example. A ReLU network is differentiable except at the kinks where a hidden unit switches: finitely many pieces of hyperplanes $w^\top x+b=0$ (whole hyperplanes for one hidden layer), a measure-zero set. Every Lipschitz function on $\mathbb R^n$ is differentiable a.e. (Rademacher). If $U$ is uniform on $[0,1]$ and $Z=U$ except $Z=10$ when $U=\frac12$, then $\operatorname*{ess\,sup}Z=1$, although the supremum over all outcomes is $10$. Almost-sure safety tolerates failures on a probability-zero set of disturbances; robust safety tolerates none (Primer C). Used in Module 1 (a.s. safety, $\operatorname*{ess\,sup}$), Module 12 and Module 10 (differentiable a.e.), Module 13 (gradient norm $1$ almost everywhere) and Module 8 (a.s. convergence).
Practice: Suprema, infima and bounds
Work from Easy to Medium before trying Hard. Use the review link for a missing definition, then try again with the explanation closed.
Exercise 0.5a — Easy: A bound need not belong to the set
For $A=(-2,3]$, find $\inf A$, $\sup A$, the minimum and the maximum. Repeat for $B=\{1-1/n:n=1,2,\dots\}$. Explain any missing extrema.
Review: Suprema, infima and bounds
Show hint
First identify the floor and ceiling; then ask whether each is actually an element.
Show worked solution
Interval: every member of $A$ is above $-2$ and at most $3$. Values approach $-2$ from above, and $3$ belongs to $A$. Hence $\inf A=-2$, $\sup A=3$, no minimum, and maximum $3$.
Sequence of values: $B$ begins $0,1/2,2/3,3/4,\dots$. Every member is nonnegative, and $0$ is included at $n=1$, so the infimum and minimum are both $0$.
Upper bound: $1-1/n\lt1$ for every finite $n$, but these values tend to $1$. Therefore $\sup B=1$ and no maximum exists. To check leastness explicitly, for any $\varepsilon\gt0$ choose $n\gt1/\varepsilon$; then $1-1/n\gt1-\varepsilon$.
Exercise 0.5b — Medium: Separate a supremum from a limit superior
For $a_t=(-1)^t+1/(t+1)$, $t\ge0$, compute $\sup_ta_t$, $\inf_ta_t$, $\limsup_ta_t$ and $\liminf_ta_t$. Which bounds are attained, and does the sequence converge?
Review: Suprema, infima and bounds
Show hint
Split into even and odd indices. A limit superior ignores any fixed finite beginning.
Show worked solution
Even indices: $a_{2k}=1+1/(2k+1)$ decreases from $2$ towards $1$. Hence the supremum of the entire sequence is $2$, attained at $t=0$.
Odd indices: $a_{2k+1}=-1+1/(2k+2)$ is always above $-1$ and decreases towards it. The infimum is $-1$, never attained.
Tails: every tail still contains infinitely many even and odd indices. Their limiting upper and lower values are $1$ and $-1$, respectively, so $\limsup a_t=1$ and $\liminf a_t=-1$.
Convergence check: since the two tail limits differ, the sequence has no single limit. The isolated initial value $2$ affects the supremum but not the limit superior.
Exercise 0.5c — Hard: Compute both orders of a minimax problem
Let $x,y\in\{0,1\}$ and let $\phi(0,0)=0$, $\phi(0,1)=2$, $\phi(1,0)=1$, $\phi(1,1)=0$. Compute $\min_x\max_y\phi(x,y)$ and $\max_y\min_x\phi(x,y)$. Explain why changing the order changes the result.
Review: Suprema, infima and bounds
Show hint
Treat $x$ as a row and $y$ as a column. For min-max take row maxima first; for max-min take column minima first.
Show worked solution
Commit $x$ first: row $x=0$ has worst value $\max(0,2)=2$; row $x=1$ has worst value $\max(1,0)=1$. The minimising player chooses $x=1$, giving $\min_x\max_y\phi=1$.
Commit $y$ first: column $y=0$ has best response $\min(0,1)=0$; column $y=1$ has best response $\min(2,0)=0$. Thus $\max_y\min_x\phi=0$.
Reason: in each expression the second player can respond to the first player's choice. The minimiser gains that advantage in max-min, producing $0\le1$, as the general max-min inequality predicts. Equality requires additional structure; a finite set by itself does not supply it.
6. Open, Closed & Compact Sets; Continuity
Safety is decided at the boundary of the safe set; optimizers and positive margins exist thanks to compactness. We work in $\mathbb R^n$ with the Euclidean distance (other norms give the same open, closed and compact sets, Primer A).
When is the boundary the zero level set? If $h$ is continuously differentiable (the partial derivatives in $\nabla h=(\partial h/\partial x_1,\dots,\partial h/\partial x_n)$ exist and are continuous) and $\nabla h(x)\ne0$ wherever $h(x)=0$ ($0$ is a regular value), then $\partial C=\{h=0\}$ and $\operatorname{Int}C=\{h\gt0\}$. Reason: take $x_0$ with $h(x_0)=0$ and follow the gradient, $\varphi(s)=h(x_0+s\nabla h(x_0))$. By the chain rule (Primer B), $\varphi(0)=0$ and $\varphi'(0)=\|\nabla h(x_0)\|^2\gt0$, so $\varphi\lt0$ for small $s\lt0$: every ball around $x_0$ contains points with $h\lt0$, hence $x_0\notin\operatorname{Int}C$, and $x_0\in\partial C$ because $C$ is closed. Without regularity this fails: $h(x)=x^2$ gives $C=\mathbb R$ and $\partial C=\emptyset$ although $h(0)=0$; and $h(x)=-x^3$ with $\dot x=1$ passes the boundary check $\dot h=-3x^2\dot x=0\ge0$ at $0$, yet the state leaves $C=(-\infty,0]$ at once. Why the boundary matters: a continuous trajectory that starts in $C$ and ends outside must cross $\partial C$ (intermediate value theorem for $t\mapsto h(x(t))$), so invariance can be checked on a regular boundary alone (Nagumo, Module 10).
With $\operatorname{dist}(y,C)=\inf_{c\in C}\|y-c\|$, the tangent cone of a closed $C$ at $x$ is $T_C(x)=\{v:\liminf_{\tau\downarrow0}\operatorname{dist}(x+\tau v,C)/\tau=0\}$, which equals $\{v:\nabla h(x)^\top v\ge0\}$ at a regular boundary point; Nagumo: $C$ is forward invariant iff $f(x)\in T_C(x)$ on $\partial C$ (unique solutions). The Hausdorff distance $d_H(A,B)=\max\{\sup_{a\in A}\operatorname{dist}(a,B),\sup_{b\in B}\operatorname{dist}(b,A)\}$ of nonempty compact sets ($d_H([0,1],[0,1.5])=0.5$) measures the convergence of reachable sets in Module 10.
Compact sets and the extreme value theorem
Examples. $[0,1]^d$, closed balls and ellipsoids $\{x:x^\top Px\le c\}$ with $P\succ0$ (bounded since $x^\top Px\ge\lambda_{\min}(P)\|x\|^2$, Primer A) are compact; $\mathbb R^n$, $(0,1]$ and $\{x:x_1^2-x_2^2\le1\}$ (closed, unbounded) are not. Sublevel sets need care: $V(x)=x^2/(1+x^2)$ is positive away from $0$, and $\{V\le0.5\}=[-1,1]$, but $\{V\le c\}=\mathbb R$ for every $c\ge1$.
Coercivity. If $S$ is closed and nonempty, $f$ continuous and $f(x)\to\infty$ as $\|x\|\to\infty$, then $f$ has a minimizer on $S$ (Weierstrass on the compact set $\{x\in S:f(x)\le f(x_0)\}$). So the safety filter $\min_u\|u-u_{\rm nom}\|^2$ subject to $a+b^\top u\ge0$ has a solution on an unbounded feasible set, whereas $\max_{u\in\mathbb R^m}b^\top u$ ($b\ne0$) has none. Positive margins: if $V$ is continuous, $V(0)=0$ and $V\gt0$ elsewhere, then $\min_KV\gt0$ on every nonempty compact $K$ with $0\notin K$.
Claim. Let $F$ be continuous with $F(0)=0$, $V$ continuous with $V(0)=0$ and $V(x)\gt0$ for $x\ne0$, $\mathcal V(c)=\{V\le c\}$ compact, and $V(F(x))\lt V(x)$ on $\mathcal V(c)\setminus\{0\}$. Then trajectories of $x_{t+1}=F(x_t)$ from $x_0\in\mathcal V(c)$ stay in $\mathcal V(c)$ and converge to $0$.
(1) Induction: $x_t\in\mathcal V(c)$ gives $V(x_{t+1})\le V(x_t)\le c$ ($F(0)=0$ covers $x_t=0$). (2) Monotone convergence: $v_t=V(x_t)\downarrow v^\ast\ge0$. (3) Contradiction and compactness: if $v^\ast\gt0$, all $x_t$ lie in the compact $K=\{v^\ast\le V\le c\}$, which excludes $0$; the continuous $\Delta V(x)=V(F(x))-V(x)$ is negative there, so $\max_K\Delta V=-\eta\lt0$ and $v_t\le v_0-t\eta\to-\infty$, impossible. (4) For $\varepsilon\gt0$, $m_\varepsilon=\min\{V(x):x\in\mathcal V(c),\|x\|\ge\varepsilon\}\gt0$ (if that compact set is nonempty), and $v_t\lt m_\varepsilon$ forces $\|x_t\|\lt\varepsilon$. $\blacksquare$
Audit. Induction, monotone convergence, suprema, Weierstrass (twice) and contradiction all appear. Without continuity of $F$ step (3) fails (Module 11: $x_t=1+2^{-t}\to1$). The argument gives no rate: for $F(x)=x/(1+x^2)$, $V=x^2$, one finds $\eta=v^\ast\big(1-(1+v^\ast)^{-2}\big)\to0$ as $v^\ast\to0$, matching the sublinear $1/\sqrt{2t}$ of Section 2.
Uniform continuity, nets, and gridding with a Lipschitz margin
$f$ is uniformly continuous on $X$ if $\forall\varepsilon\gt0\ \exists\delta\gt0\ \forall x,y\in X:\|x-y\|\lt\delta\Rightarrow|f(x)-f(y)|\lt\varepsilon$: one $\delta$ for all points (for continuity $\delta$ may depend on the point). Continuous functions on compact sets are uniformly continuous (Heine–Cantor), and $L$-Lipschitz ones are too, with $\delta=\varepsilon/L$ for $L\gt0$ (any $\delta$ works if $L=0$: $f$ is constant); $1/x$ on $(0,1]$ and $x^2$ on $\mathbb R$ are continuous but not uniformly so.
Example. $h(x)=1-x^2$ on $X=[-0.95,0.95]$ has $L=\max_X|h'|=1.9$. The $20$ points $-0.95,-0.85,\dots,0.95$ form a $0.05$-net; the margin $L\tau=0.095$ is cleared by the smallest grid value $h(\pm0.95)=0.0975$, so $h\ge0$ on $X$ is certified. Spacing $0.2$ ($\tau=0.1$, margin $0.19$) fails although $h\ge0$ is true: finer grids certify more, at a cost growing like $\tau^{-d}$ (Section 7).
Connectedness, semicontinuity and density
Connectedness. $A$ is path-connected if any two points are joined by a continuous path inside $A$; path components are the maximal path-connected subsets (for open sets they coincide with the usual connected components, in general not). Continuous images of path-connected sets are path-connected, so a continuous parameterisation from $\mathbb R^N$ reaches only one path component of a set that has several. A finite grid in Euclidean space has no continuous path joining distinct points; its connectivity depends on an adjacency rule, and certified reachability is a third notion (Module 6, Module 4, Module 13, Module 11).
Semicontinuity. $f$ is lower semicontinuous if $f(x)\le\liminf_tf(x_t)$ whenever $x_t\to x$, equivalently if every $\{f\le c\}$ is closed; the Weierstrass argument still yields minima on nonempty compact sets. Example: $f=0$ on $(-\infty,0]$, $f=1$ on $(0,\infty)$ (Module 8).
Density. A class $\mathcal G$ is dense in $\mathcal F$ in the sup norm on a compact $X$ if $\forall f\in\mathcal F\ \forall\varepsilon\gt0\ \exists g\in\mathcal G:\sup_X|f-g|\le\varepsilon$: arbitrarily good approximation, not exact representation (Module 13).
Practice: Topology, existence and grid certificates
Work from Easy to Medium before trying Hard. Use the review link for a missing definition, then try again with the explanation closed.
Exercise 0.6a — Easy: Describe an interval all the way to its boundary
Working in $\mathbb R$, find the interior, closure and boundary of $A=(-1,1]$. Is $A$ open, closed, bounded or compact? Is $B=\{0,1\}$ compact?
Review: Topology, existence and grid certificates
Show hint
An interior point needs a small interval around it inside the set. A closed set keeps every limit of its convergent sequences.
Show worked solution
Interior: every $x$ strictly between $-1$ and $1$ has a small interval around it in $A$. At $1$, every such interval extends above $1$, so $\operatorname{Int}A=(-1,1)$.
Closure and boundary: adding the missing limit $-1$ gives $\operatorname{cl}A=[-1,1]$. Removing the interior leaves $\partial A=\{-1,1\}$. A boundary point need not belong to the original set.
Classify: $A$ is not open (it contains noninterior point $1$), not closed (a sequence $-1+1/n$ in $A$ tends to missing point $-1$), and bounded. In $\mathbb R$, compact means closed and bounded, so $A$ is not compact. The finite set $B$ is closed and bounded and therefore compact, even though it has no interior.
Exercise 0.6b — Medium: Decide whether a smallest value is attained
For $f(x)=x^2$, decide whether a minimum exists on each of $(0,1]$, $[0,1]$ and $\mathbb R$. State which cases follow directly from the extreme value theorem and explain the remaining cases.
Review: Topology, existence and grid certificates
Show hint
Find the infimum first. Compactness is sufficient for a continuous function to attain it, but not necessary.
Show worked solution
On $(0,1]$: $f(x)\gt0$ for every permitted $x$, while $f(1/n)=1/n^2\to0$. The infimum is $0$ but there is no minimiser. The domain is bounded but not closed.
On $[0,1]$: the continuous function is on a nonempty compact interval, so the theorem applies. Explicitly $f(0)=0\le f(x)$, giving the unique minimiser $0$.
On $\mathbb R$: the domain is not compact, so that theorem alone does not apply. Nevertheless $x^2\ge0$ with equality only at $0$, so a unique minimum exists. Coercivity ($x^2\to\infty$ as $|x|\to\infty$) is another route to existence here. Failure of a sufficient condition is not proof of nonexistence.
Exercise 0.6c — Hard: Certify the space between measurements
An unknown $3$-Lipschitz function $h:[0,1]\to\mathbb R$ satisfies $h(g)\ge0.35$ at $G=\{0,0.2,0.4,0.6,0.8,1\}$. Prove a uniform lower bound. Would measurements at $\{0,0.4,0.8,1\}$ with the same lower bound suffice? Give a counterexample if not.
Review: Topology, existence and grid certificates
Show hint
Use half the largest gap as the covering radius. For the counterexample try $h(x)=0.35-3\operatorname{dist}(x,G)$.
Show worked solution
Fine grid: the gaps are $0.2$, so each point is within $0.1$ of a grid point. For a nearest $g$, $h(x)\ge h(g)-3|x-g|\ge0.35-0.3=0.05$. Thus every point has a positive margin of at least $0.05$.
Coarse grid: the largest gap is $0.4$, so the covering radius is $0.2$. The same argument gives only $0.35-0.6=-0.25$, which does not certify nonnegativity.
Show the limitation is real: let $G_c=\{0,0.4,0.8,1\}$ and $h_c(x)=0.35-3\operatorname{dist}(x,G_c)$. Distance to a nonempty set is 1-Lipschitz: comparing to a nearest point and using the triangle inequality bounds its change by $|x-y|$. Therefore $h_c$ is 3-Lipschitz and equals $0.35$ on the grid. At $x=0.2$, its value is $0.35-3(0.2)=-0.25$. Positive samples alone do not prove safety between them.
7. Asymptotic Notation & Rates
Rates and costs are stated up to constants ("$\gamma_T=O((\log T)^{d+1})$" for the information gain of a GP, Module 3, where $\gamma_T$ is not a discount factor; "an $O(t^3)$ determinant"); here is what that promises.
Examples. $3n^2+10n+5=\Theta(n^2)$: for $n\ge10$, $10n\le n^2$ and $5\le n^2$, so $3n^2\le3n^2+10n+5\le5n^2$. $\ln n=o(n^a)$ and $n^k=o(e^{an})$ for all $a\gt0$, $k$. Module 12 writes $\log\det(N+\varepsilon E)=\log\det N+\varepsilon\operatorname{tr}(N^{-1}E)+O(\varepsilon^2)$ as $\varepsilon\to0$, and Module 2 an error "within $O(\eta)$", i.e. at most $C\eta$ for small step sizes $\eta$.
| $T$ | $10^2$ | $10^4$ | $10^6$ | $10^8$ | $10^{10}$ |
|---|---|---|---|---|---|
| $\sqrt T$ | $10$ | $100$ | $1000$ | $10^4$ | $10^5$ |
| $T^{2/3}$ | $21.5$ | $464$ | $10^4$ | $2.15\cdot10^5$ | $4.64\cdot10^6$ |
| $(\ln T)^3$ | $97.7$ | $781$ | $2637$ | $6251$ | $12208$ |
Comparing rates. $(\ln T)^3=o(\sqrt T)$ and $\sqrt T=o(T^{2/3})$, yet $(\ln T)^3$ exceeds $\sqrt T$ for every $T$ from $4$ to about $2.4\cdot10^7$: an $o$-statement says nothing about a particular $T$.
Operation counts. A dense Cholesky factorisation, determinant or solve of a $t\times t$ matrix costs $O(t^3)$ operations (about $t^3/3$ for Cholesky), a matrix-vector product $O(t^2)$; doubling $t$ multiplies $O(t^3)$ by about $8$. Total cost is iterations times cost per iteration: interior-point SDP solvers need $O(\sqrt n\log(1/\varepsilon))$ iterations of $O(mn^3+m^2n^2+m^3)$ each. $O$ predicts growth, not seconds. Grids explode with dimension: $m$ points per axis give $m^d$ points, e.g. $100^3=10^6$ but $100^6=10^{12}$.
Examples. By Hoeffding's inequality (Primer C), the mean of $n$ independent $[0,1]$-valued samples is within $\varepsilon$ of its expectation with probability $1-\delta$ once $n\ge\ln(2/\delta)/(2\varepsilon^2)$, a sample complexity $O(\varepsilon^{-2}\log(1/\delta))$: $738$ samples for $\varepsilon=\delta=0.05$. $R_T\le4\sqrt{T\gamma_T}$ with $\gamma_T=(\ln T)^2$ gives $R_T/T\le4\ln T/\sqrt T\to0$ (sublinear), yet this bound is $0.37$ at $T=10^4$ and reaches $0.1$ only at $T=246{,}639$. Check products as a whole: Module 6 needs $\beta_N^2\gamma_N=o(N)$, and $\sqrt N\cdot\sqrt N=N$ although each factor is $o(N)$. Bandits and regret are developed in Primer E.
Practice: Rates, constants and computational budgets
Work from Easy to Medium before trying Hard. Use the review link for a missing definition, then try again with the explanation closed.
Exercise 0.7a — Easy: Prove a growth class with actual constants
For $f(n)=2n^2+3n+1$, $n\ge1$, prove $f(n)=\Theta(n^2)$ using explicit constants. Is $f(n)=o(n^2)$?
Review: Rates, constants and computational budgets
Show hint
For $n\ge1$, both $n$ and $1$ are at most $n^2$. Little-$o$ asks for a ratio tending to zero.
Show worked solution
Lower bound: the extra terms are nonnegative, so $f(n)\ge2n^2$. This proves $\Omega(n^2)$ with constant $c=2$ and threshold $n_0=1$.
Upper bound: $3n\le3n^2$ and $1\le n^2$, hence $f(n)\le(2+3+1)n^2=6n^2$. This proves $O(n^2)$ with $C=6$ at the same threshold. Having both bounds gives $\Theta(n^2)$.
Ratio: $f(n)/n^2=2+3/n+1/n^2\to2$, not $0$. Thus $f$ is not $o(n^2)$. Big-$O$ permits a nonzero limiting ratio; little-$o$ does not.
Exercise 0.7b — Medium: Translate accuracy into work
Algorithm A guarantees error at most $4/\sqrt T$ after $T\ge1$ iterations, each costing $100$ operations. Algorithm B guarantees error at most $8/T$, each iteration costing $1000$ operations. Find sufficient iteration and operation budgets for error at most $0.1$. Which is cheaper under these bounds?
Review: Rates, constants and computational budgets
Show hint
Solve each explicit inequality for $T$, round upward, then multiply by the cost per iteration.
Show worked solution
A: $4/\sqrt T\le0.1$ implies $\sqrt T\ge40$, hence $T\ge1600$. The sufficient work budget is $1600\cdot100=160{,}000$ operations.
B: $8/T\le0.1$ implies $T\ge80$. Its sufficient work budget is $80\cdot1000=80{,}000$ operations.
Compare carefully: B needs half as many operations under the stated guarantees, although each iteration costs ten times more. These are sufficient worst-case budgets; observed errors could be smaller. A rate without its constants and per-iteration cost would not settle this comparison.
Exercise 0.7c — Hard: Combine two rates without losing their meaning
Suppose $0\le R_T\le5\sqrt T\log T$ for $T\ge2$, where $R_T$ is cumulative regret and $\log$ is natural. Prove the average regret tends to zero and give the resulting upper bound at $T=10^4$. Separately, show why $a_T=o(T)$ and $b_T=o(T)$ do not imply $a_Tb_T=o(T)$.
Review: Rates, constants and computational budgets
Show hint
Divide cumulative regret by $T$. For the second claim use two square-root sequences.
Show worked solution
Average: $0\le R_T/T\le5\log T/\sqrt T$. Since $\log T=o(T^{1/2})$, the right side tends to $0$. The squeeze theorem therefore gives $R_T/T\to0$, so the regret is sublinear; individual trial regrets need not all tend to zero.
Finite budget: at $T=10^4$, $\sqrt T=100$ and $\log T\approx9.21034$, giving $R_T/T\le0.46052$. An asymptotically vanishing bound can still be substantial at a particular budget.
Product counterexample: set $a_T=b_T=\sqrt T$. Each ratio $a_T/T=b_T/T=1/\sqrt T$ tends to $0$, but $a_Tb_T=T$ and its ratio to $T$ is $1$. Products require multiplying the full expressions and then testing the resulting ratio.
Interactive: Fixed-Point Iteration & Geometric Series
Iterate $x_{k+1}=g(x_k)$ for several maps (cobweb and log-scale error against Banach's a priori bound) and sum the discounted series $\sum_t\gamma^t$.
Cobweb: $g$ (blue), $y=x$ (grey), staircase $(x_0,x_0)\to(x_0,x_1)\to(x_1,x_1)\to\cdots$ (orange), fixed point (green). Errors: $|x_k-x^\ast|$ (dots) and, if a factor $L\lt1$ is known, the bound $L^{k-k_0}|x_{k_0+1}-x_{k_0}|/(1-L)$ (dashed).
Blue: fraction $1-\gamma^t$ of the limit collected by $t$ terms; teal: the remaining fraction $\gamma^t$; orange: horizon $T$; purple: first $T$ with $\gamma^T\le0.01$.
What to look for. (1) Affine, $a=0.5$: the dots lie on the (exact) bound; $a=0.99$ needs $1833$ iterations; $a\lt0$ spirals; $|a|\ge1$ breaks the theorem ($a=1$: no fixed point; $a=-1$: nonfixed starts alternate; $|a|\gt1$: nonfixed starts run away; for $a\ne1$, a start at $x^\ast=1/(1-a)$ stays fixed). (2) Cosine from $x_0=1$: the bound asks for $87$ iterations, $32$ suffice (slope $0.674$ near $x^\ast$ versus $L=0.841$). (3) Logistic: $r=2.8$ converges without a global contraction, $r=2$ quadratically, $r=3.2,\ 3.5,\ 3.56$ end on (approximate) cycles of period $2,4,8$, and at $r=3.9$ the orbit is chaotic: no short cycle shows up. (4) Slow map: the dots bend, sublinear convergence. (5) The button's iterates $V_k$ are the partial sums below.
From the mathematics to a real decision
A useful mathematical answer changes what someone can responsibly do. A temperature reading may support accepting a chamber, choosing a cooling command, or waiting for another solver iteration. Those are different decisions, and they require different statements. This chapter follows a constructed thermal-chamber model from a single reading to a claim about every future step. The numbers are teaching choices, not measurements from a particular machine. Their purpose is to make the order of the reasoning visible.
- Translate an acceptance rule into containment of sets and explain what a failed test means.
- Place control choices and unknown disturbances in the correct quantifier order.
- Build an all-time conclusion from a one-step bound without assuming the conclusion.
- Turn an error recurrence into a finite iteration budget, including its unavoidable error floor.
Begin with the decision and its units
Let $x$ be temperature above a chosen reference, measured in degrees Celsius, and let the allowed interval be $C=[0,5]$. This is a specification: for this hypothetical task a temperature deviation in that interval is acceptable. It is not a claim that the interval is physically appropriate for any actual chamber. A sensor reading $y$ comes with a deterministic error bound $|x-y|\le\varepsilon$. The word deterministic means that every error in the interval is permitted; no probability distribution has been assumed.
The possible true values form $I(y)=[y-\varepsilon,y+\varepsilon]$. Acceptance follows when $I(y)\subseteq C$. Notice the change from a statement about one number to a statement about all numbers compatible with the information. Checking only $y\in C$ answers whether the displayed reading is acceptable. It does not answer whether the unknown temperature is acceptable. If containment fails, the information allows an unacceptable temperature; it may also allow acceptable temperatures. The correct conclusion is that this acceptance test has not certified the chamber.
This distinction is useful whenever a calculation is an upper or lower bound rather than an exact observation. Write down what the bound encloses before deciding what its sign proves. A positive upper bound on an error does not mean that this error occurred. A negative lower bound on a safety margin does not mean the actual margin is negative. Both statements describe the limits of the information.
Choose before the disturbance arrives
Now consider one minute between commands. The constructed update is $x^+=1.1x+u+w$, where $x^+$ is the next temperature deviation, $u\in[-1,0]$ is a commanded cooling contribution in degrees Celsius per step, and $w\in[0,0.4]$ is an unknown warming contribution in the same units. The coefficient $1.1$ is dimensionless. This simplified model assumes that the current $x$ is known exactly, the command is realized exactly, and the stated disturbance interval contains the actual disturbance. Sensor uncertainty would require another universal quantifier over the possible current temperatures.
The command is selected after observing $x$ and before observing $w$. Therefore the desired one-step statement is:
Read this aloud as a sequence of information: show me an allowed temperature; I choose a command; any allowed disturbance may then occur. If $u$ were allowed to depend on $w$, the calculation would describe a different device with information available before the action. Mathematical punctuation is recording a physical timing assumption.
Decision. At $x=4.5$ degrees Celsius, find every command that keeps the next step in $C$, whatever allowed warming occurs. Since the update increases with $w$, its complete range is $[4.95+u,5.35+u]$. There is no need to test infinitely many disturbances separately: the two endpoints bound every intermediate value.
Translate containment. The lower endpoint must be at least zero and the upper endpoint at most five. Thus $u\ge-4.95$ and $u\le-0.35$. Intersect these conditions with the actuator interval $[-1,0]$ to obtain $u\in[-1,-0.35]$. The intersection matters: a mathematically useful command is irrelevant if the actuator cannot issue it.
Select and check. Choose $u=-0.5$. The successor interval is $[4.45,4.85]$, contained in $[0,5]$. The nominal disturbance $w=0$ would predict $4.45$; accounting for every allowed disturbance raises the upper prediction to $4.85$. This verifies one step from the stated temperature. It has not yet verified a whole trajectory or a chamber with unmodeled delays.
To cover every $x\in C$, one explicit choice is $u(x)=-0.18x$. This command lies in $[-0.9,0]\subseteq[-1,0]$, and the resulting successor interval is $[0.92x,0.92x+0.4]$. Its lower endpoint is nonnegative; its upper endpoint is at most $0.92(5)+0.4=5$. We have supplied a witness for the existential quantifier at every state, using one formula rather than infinitely many separate calculations.
No single fixed command works for the entire interval. At $x=0$, allowing $w=0$ forces $u\ge0$, hence $u=0$. At $x=5$, allowing $w=0.4$ forces $u\le-0.9$. These requirements conflict. Feedback changes the available decision because the command may depend on the observed temperature. This conclusion follows from the two boundary states, not from how many points were simulated.
Extend the claim one step at a time
Suppose the same update and disturbance bounds apply at every integer time $t\ge0$, and apply the feedback $u_t=-0.18x_t$. To prove $x_t\in C$ for all time, first state the base case $x_0\in C$. Next assume only that the current $x_t$ lies in $C$. The one-step calculation then shows $x_{t+1}\in C$ for every permitted $w_t$. Induction completes the argument. It permits disturbances to change arbitrarily from step to step, because the one-step result did not require them to be constant or independent.
The proof is conditional. If a disturbance exceeds $0.4$, if the command arrives late, or if the temperature is not known as assumed, a hypothesis has changed. The proof remains mathematically valid while its applicability to that modified situation needs new work. Keeping hypotheses beside the step where they are used makes that limitation understandable rather than an unexplained disclaimer at the end.
A limit does not automatically give a stopping time
A controller may run a numerical calculation before issuing its command. Let $e_k$ be a nonnegative temperature prediction error bound after iteration $k$. An error recurrence describes how an earlier error is reduced and how new approximation error is introduced. The geometric factor explains the improvement; the additive term explains why unlimited iteration can still leave a nonzero bound.
Model and goal. Suppose $e_0=0.8$ degrees Celsius and $e_{k+1}\le0.6e_k+0.02$. Each iteration costs $2$ milliseconds and initialization costs $5$ milliseconds. We require a certified error at most $0.06$ degrees Celsius before issuing a command. The recurrence and timings are stipulated teaching assumptions.
Unroll the recurrence. The first bounds are $e_1\le0.5$ and $e_2\le0.32$. Repeating substitution gives $e_k\le0.8(0.6)^k+0.02\sum_{j=0}^{k-1}(0.6)^j$. Multiplying the finite sum by $1-0.6$ cancels adjacent powers, so the sum is $(1-0.6^k)/0.4$. Therefore:
Solve the actual tolerance. We need $0.75(0.6)^k\le0.01$, equivalently $(0.6)^k\le1/75$. Taking logarithms gives $k\ge\log(1/75)/\log(0.6)$; division reverses the inequality because $\log(0.6)$ is negative. Check the neighboring integers: at $k=8$ the bound is $0.06259712$, and at $k=9$ it is $0.057558272$. Nine iterations suffice, costing $5+9(2)=23$ milliseconds. Eight are not certified by this bound.
Interpret the limit. The bound approaches $0.05$, so a demand of $0.04$ cannot be established from this recurrence. A demand of exactly $0.05$ is also not reached by this finite bound. Actual errors might be smaller, but this information alone cannot certify them. Improving the additive approximation term could be more useful than buying more iterations.
Using $w=0$ in the chamber or dropping $0.02$ from the error recurrence makes the arithmetic easier while changing the claim. Repair the argument by writing the range of every unknown contribution and retaining it through each inequality. A successful nominal trajectory and a convergent geometric term are both useful calculations; each becomes a robust conclusion only after every remaining term is accounted for.
Application practice: information, action and guarantees
Exercise 0.B1 — Easy: Accept a reading with a bounded error
A chamber must have $x\in[0,5]$ degrees Celsius above reference. A sensor satisfies $|x-y|\le0.2$. Assess readings $y=4.7$ and $y=4.9$. Derive the complete interval of readings this rule can accept, and explain whether rejecting a reading proves physical failure.
Show hint
Write the possible true-temperature interval and require both its endpoints to satisfy the specification.
Show worked solution
At $4.7$, possible values are $[4.5,4.9]$, all acceptable. At $4.9$, the interval is $[4.7,5.1]$, so acceptance is not certified. The second interval includes both passing and failing temperatures.
For a general reading, containment requires $y-0.2\ge0$ and $y+0.2\le5$, giving $y\in[0.2,4.8]$. This interval is closed because the specification allows its endpoints. A rejected reading indicates insufficient evidence under this rule; it does not identify the actual temperature. The conclusion also relies on the sensor error bound holding for the reading in question.
Exercise 0.B2 — Medium: Keep the decision ahead of the unknown warming
Use $x^+=1.1x+u+w$, $u\in[-1,0]$, $w\in[0,0.4]$, and $C=[0,5]$. At $x=4.8$, find every robustly allowed command and verify $u=-0.8$. A colleague chooses $u=-0.28-w$. Explain why that calculation uses different information, even if its numerical values lie in the actuator interval.
Show hint
First fix one u and range over w. Then ask when the colleague learns w.
Show worked solution
The successor interval for fixed $u$ is $[5.28+u,5.68+u]$. Containment requires $u\ge-5.28$ and $u\le-0.68$; intersecting with the actuator interval gives $[-1,-0.68]$. At $u=-0.8$ the successor interval is $[4.48,4.88]$, so every allowed disturbance passes.
The colleague's command gives $x^+=5$ for each disturbance, and ranges from $-0.68$ to $-0.28$. But it requires knowing $w$ before commanding: it witnesses $\forall w\ \exists u$, whereas the device requires $\exists u\ \forall w$. A command issued after measuring the disturbance would be a different timing model. The robust interval above supplies the required single command.
Exercise 0.B3 — Medium: Recognize an attainable tolerance
An iterative predictor satisfies $e_0=0.70$ and $e_{k+1}\le0.5e_k+0.03$, in degrees Celsius. Derive a bound for every $k$. Can it certify $e_k\le0.04$? Find the smallest iteration budget certified for $e_k\le0.07$ and explain how the answer changes for the strict requirement $e_k\lt0.07$.
Show hint
The steady value of the equality recurrence solves b=0.5b+0.03. Subtract it before taking powers.
Show worked solution
The steady value is $b=0.06$. Subtracting it gives $e_{k+1}-0.06\le0.5(e_k-0.06)$; induction yields $e_k\le0.06+0.64(0.5)^k$. The requested $0.04$ is below the limiting bound and cannot be certified by this information.
For $0.07$, require $0.64/2^k\le0.01$, or $2^k\ge64$. The smallest integer is $k=6$, where the bound equals $0.07$; at $k=5$ it is $0.08$. Strict inequality needs $k=7$, giving $0.065$. Because equality at every step is an allowed error sequence, the failed smaller budgets really cannot provide the corresponding universal guarantee.
Exercise 0.B4 — Hard: Find exactly how much disturbance the actuator can cover
Replace the warming bound by $w\in[0,d]$, with $d\ge0$, in the chamber model. For which $d$ does $\forall x\in[0,5]\ \exists u\in[-1,0]\ \forall w\in[0,d]:x^+\in[0,5]$ hold? Prove necessity with a boundary state and sufficiency with an explicit feedback. Then state the all-time consequence and its initial-state assumption.
Show hint
At x=5 test the largest warming and strongest available cooling. For sufficiency try u=-0.2x.
Show worked solution
At $x=5,w=d$, even maximum cooling gives $x^+=5.5-1+d=4.5+d$. If $d\gt0.5$, this exceeds five, so no command can satisfy the claim. Thus $d\le0.5$ is necessary.
For any $0\le d\le0.5$, choose $u=-0.2x$, which lies in $[-1,0]$. Then $x^+=0.9x+w$ is nonnegative and at most $4.5+d\le5$. This proves sufficiency for the entire interval, including its boundary, and establishes the exact parameter range $[0,0.5]$.
If $x_0\in[0,5]$, applying this feedback repeatedly keeps every subsequent state in that interval by induction, for arbitrary permitted disturbance sequences. Starting outside the interval is not covered. Notice that the feedback used earlier is a valid choice for $d=0.4$, while this new feedback also handles the limiting case $d=0.5$.
Reconstruct the argument before moving on
Close the examples and reconstruct the chain in your own words: specification, information set, command timing, one-step containment, induction, and computation budget. At each link, name a hypothesis that could break its application. Explain why a failed sufficient test differs from a counterexample, and why a limiting value differs from a finite stopping guarantee. These distinctions let you read later safety statements without silently strengthening what they prove.
For recall, write the negation of the robust chamber claim; identify which variable may depend on which earlier variables; and explain where the initial condition enters the induction. Then derive the error floor for a general recurrence $e_{k+1}\le ae_k+b$ with $0\le a\lt1$ and $b\ge0$. The answer $b/(1-a)$ should follow from the same finite geometric sum, rather than from memory alone.
The next bridge is geometric. Primer A's vectors and norms describe information sets when several temperatures or positions are uncertain together. Primer B's constrained optimization selects a good command from the admissible set. The logic here continues to determine what either calculation is allowed to conclude.
Exercises
For gradual practice on the opening material, use the graded sets on sets & logic, functions & fixed points, and proofs. The exercises below bring together ideas from across the primer.
Ready to move on?
You are ready for Primer A when you can read and negate a quantified statement, compose two functions, and explain the difference between a bound and an attained optimum. Check these without opening a solution:
- Redo negating quantifiers, composition, and induction.
- Redo a discounted tail and supremum versus maximum.
- Explain why the grid margin is needed, then turn the explicit error bound into a budget.
If one task stalls, revisit its review link and attempt the local Easy exercise again. You can continue once Easy and Medium work is independent; the Hard exercises are useful return visits as later modules give the ideas context. Next: Primer A: vectors and matrix tools.
Further Reading
| Resource | Edition | Covers | Why read it |
|---|---|---|---|
| Book of Proof (R. Hammack) | 3rd ed. 2018, free | Sets, logic, proof techniques, induction, functions | The gentlest complete route through Sections 1–3. |
| How to Prove It: A Structured Approach (D. J. Velleman) | 3rd ed., CUP 2019 | Quantifiers, proof strategies, induction | How the logical form of a statement dictates its proof. |
| Mathematics for Computer Science (E. Lehman, F. T. Leighton, A. R. Meyer) | MIT 6.042J, 2015, free | Logic, induction and state-machine invariants, sums, asymptotic notation | Invariants are induction over time steps; its "Sums and Asymptotics" matches Sections 4 and 7. |
| Understanding Analysis (S. Abbott) | 2nd ed., Springer 2015 | Suprema, sequences, series, compactness, continuity | The most readable treatment of Sections 4–6. |
| Basic Analysis I (J. Lebl) | v6.3, 2026, free | limsup, series, extreme values, uniform continuity, metric spaces | Free and complete; Section 7.6 proves the contraction fixed-point theorem. |
| Convex Optimization, App. A (S. Boyd, L. Vandenberghe) | CUP 2004, free PDF | Norms, open and closed sets, sup and inf | A compact reference in the optimization modules' conventions. |
| Computational Complexity: A Modern Approach (S. Arora, B. Barak) | CUP 2009, free draft | P, NP, reductions (Chapter 2) | The precise meaning of "NP-hard" in Modules 12 and 15. |
| Reinforcement Learning: An Introduction (R. S. Sutton, A. G. Barto) | 2nd ed., MIT Press 2018, free | Discounted returns, value iteration | Where the geometric series and fixed points meet RL. |