Quantifiers and the Shape of a Proof

The last chapter was written in sentences like "for every $\varepsilon > 0$ there is an $N$ such that for all $n, m \geq N$, $|a_n - a_m| \leq \varepsilon$". From here to the end of the route, almost every definition and theorem has that shape. It is a chain of "for every" and "there is", in a particular order, and the order carries the meaning. Perelman's papers are dense mostly because they stack these quantifiers four and five deep.

This chapter is about reading, writing and negating such sentences without hesitation, and about the small set of proof patterns used with them. It sits here, just before sequences, because the next chapter is the first where it becomes impossible to get by without it.

By the end of this chapter you will be able to:

• translate a mathematical sentence into quantifier form and back;
• explain why the order of quantifiers matters, and what "depends on" means;
• negate any sentence mechanically, however many quantifiers it has;
• read a definition as a game between you and an adversary;
• recognise and use the standard proof patterns, including the ε/2 trick and proof by contradiction with a sequence of counterexamples.

5.1Statements and connectives

A statement is a sentence that is either true or false (2A.1 The Natural Numbers). Statements are combined with a few connectives, each with a precise meaning that sometimes differs from everyday English.

Connective	Written	True exactly when
not $P$	$\neg P$	$P$ is false
$P$ and $Q$	$P \wedge Q$	both are true
$P$ or $Q$	$P \vee Q$	at least one is true (inclusive "or")
if $P$ then $Q$	$P \implies Q$	$P$ is false, or $Q$ is true
$P$ if and only if $Q$	$P \iff Q$	both true or both false

Two of these deserve comment. Mathematical "or" is inclusive: "$n$ is even or $n$ is a multiple of $3$" is true for $n = 6$. And "if $P$ then $Q$" says nothing at all about what happens when $P$ is false (2A.1 The Natural Numbers). It is a promise that is broken only if $P$ holds and $Q$ fails.

From the table one can read off the identities used constantly:

The first two are De Morgan's laws, which you met for sets in 2A.2 Sets, Functions and Equivalence. The third says that the only way an implication fails is with a true hypothesis and a false conclusion. The fourth is the contrapositive.

5.2Quantifiers

A property $P(x)$ becomes a statement once $x$ is specified. There are two other ways to turn it into a statement:

• For all: $\forall x \in X,\ P(x)$, meaning $P(x)$ is true for every element $x$ of $X$.
• There exists: $\exists x \in X,\ P(x)$, meaning $P(x)$ is true for at least one element $x$ of $X$.

The variable $x$ in these statements is bound: it is a placeholder, and renaming it changes nothing. "$\forall x \in \mathbb{R},\ x^2 \geq 0$" and "$\forall t \in \mathbb{R},\ t^2 \geq 0$" are the same statement. Variables that aren't bound by a quantifier are free, and a sentence with a free variable is a property, not yet a statement.

Two conventions in the guidebook: the set a quantifier ranges over is always written ($\forall \varepsilon > 0$ means "for every real $\varepsilon > 0$"), and "there exists" means "at least one", not "exactly one". Uniqueness is stated separately, often as $\exists!$.

5.2.1Negation: swap and push inward

The negation of a quantified statement is obtained by a completely mechanical rule.

"Not everyone passed" means "someone didn't pass". "Nobody passed" means "everyone didn't pass". Applied repeatedly, the rule negates a sentence with any number of quantifiers: swap every $\forall$ with $\exists$ and vice versa, keep the order, and negate the final property.

Notice what the negation gives you: not a vague "the terms don't settle down", but a precise recipe for a counterexample. Fix one $\varepsilon$, then for every $N$ produce two terms beyond $N$. Negation is how you find out what you have to construct to disprove something.

5.3The order of quantifiers

When a sentence has several quantifiers of different kinds, their order changes its meaning completely. Compare:

• $\forall \text{ person } p\ \ \exists \text{ person } q:\ q \text{ is the mother of } p$. Everyone has a mother. True.
• $\exists \text{ person } q\ \ \forall \text{ person } p:\ q \text{ is the mother of } p$. Someone is the mother of everyone. False.

In the first sentence the mother $q$ is chosen after $p$, so it may depend on $p$. In the second, $q$ is chosen first and must work for every $p$ at once. Swapping the order of $\exists$ and $\forall$ turns a statement about each object separately into a statement that holds uniformly.

In general, $\exists y\ \forall x\ P(x, y)$ implies $\forall x\ \exists y\ P(x, y)$ (use the same $y$ for every $x$), but not conversely. The difference is precisely the difference between a pointwise and a uniform statement, and analysis is full of such pairs.

Dependence. Variables introduced by $\exists$ may depend on every variable introduced before them, and on nothing introduced after. Writers often record this explicitly: $N = N(\varepsilon)$, $\delta = \delta(\varepsilon, x)$. When reading a long statement, it pays to write out what each $\exists$-variable may depend on. In Ricci flow papers this is often the hardest part. A constant "depending only on the dimension and $\kappa$" is a precise claim that it does not depend on the particular flow, the point or the time.

5.4Definitions as games

A useful way to read a quantified statement is as a two-player game. An adversary makes the $\forall$ moves and tries to make the final property fail; you make the $\exists$ moves and try to make it hold. Moves are made in order, left to right, and each player sees all earlier moves. The statement is true exactly when you have a winning strategy: a rule for your moves, in terms of the moves made so far, that always wins.

Take the statement that the decimal truncations of $\sqrt2$ form a Cauchy sequence (2A.4 The Real Numbers):

1. The adversary names a tolerance: $\varepsilon = 0.001$, say.
2. You name a starting point: $N = 3$, because truncations agreeing to 3 decimal places differ by at most $10^{-3}$.
3. The adversary names any $n, m \geq 3$.
4. You win if $|a_n - a_m| \leq 0.001$, and with $N = 3$ you always do.

Your strategy is "$N(\varepsilon) =$ the least $N$ with $10^{-N} \leq \varepsilon$". It answers every possible move of the adversary, so the statement is true.

Negation, in this picture, swaps the roles of the players. That is why negating swaps $\forall$ and $\exists$.

5.5The shape of a proof

A small number of proof patterns account for nearly everything in analysis. Recognising them makes long proofs readable: each paragraph is usually one of these moves.

To prove $\forall x \in X,\ P(x)$: say "Let $x \in X$ be arbitrary", and prove $P(x)$ using only that $x \in X$. Nothing about $x$ may be assumed beyond that.

To prove $\exists x \in X,\ P(x)$: exhibit a specific $x$ (a witness) and check $P(x)$. Or, sometimes, show that assuming no such $x$ exists leads to a contradiction. That gives existence without telling you what $x$ is. The least upper bound theorem (2A.4 The Real Numbers) produces suprema that way: by construction, but as a limit nobody can write down in closed form.

To use a hypothesis $\forall x,\ P(x)$: apply it to whichever $x$ is useful (specialise). Specialising to a cleverly chosen value is often the whole proof.

To use a hypothesis $\exists x,\ P(x)$: give the object a name ("let $x_0$ be such that $P(x_0)$") and work with it. You may not choose which such $x$ it is.

To prove $P \implies Q$: assume $P$ and derive $Q$ (direct proof); or assume $\neg Q$ and derive $\neg P$ (contrapositive); or assume $P$ and $\neg Q$ and derive a contradiction.

To prove $P \iff Q$: prove both directions separately.

To prove uniqueness: suppose $x$ and $x'$ both have the property and show $x = x'$.

Without loss of generality. When cases are symmetric (say, $a \leq b$ or $b \leq a$, with the roles of $a$ and $b$ interchangeable), it is enough to treat one of them. Say why the other case is the same.

5.5.1The ε/2 trick and its relatives

Many statements in analysis say that some quantity can be made smaller than any $\varepsilon > 0$. When the quantity is a sum of two pieces, you make each piece smaller than $\varepsilon/2$:

You have already seen this proving that equivalence of Cauchy sequences is transitive (2A.4 The Real Numbers). With three pieces it becomes the "$\varepsilon/3$ argument", used for example to show that a uniform limit of continuous functions is continuous (2B.5 Uniform Convergence and Arzelà–Ascoli). The precise fractions are unimportant. Any argument that ends with "$< C\varepsilon$" for a constant $C$ not depending on $\varepsilon$ proves the same thing, because $\varepsilon$ was arbitrary. Writers say "$\lesssim \varepsilon$" or "$O(\varepsilon)$" and move on.

This tiny proposition is how most equalities in analysis are proved: to show two quantities are equal, show their difference is at most $\varepsilon$ for every $\varepsilon > 0$. It is also the reason for the "let $\varepsilon > 0$ be arbitrary" that opens so many proofs.

5.6Contradiction with a sequence of counterexamples

One proof pattern deserves a name of its own, because it runs through this guidebook from the next chapter to Perelman's canonical neighbourhood theorem. Call it the contradiction–compactness template.

Many theorems assert a uniform bound: "there is a constant $C$ such that, for every object in some class, a certain quantity is at most $C$". Often the most natural proof is by contradiction:

1. Suppose not. By Theorem 5.1, for every $C$ there is an object in the class whose quantity exceeds $C$. Taking $C = 1, 2, 3, \dots$ gives a sequence of counterexamples, each worse than the last.
2. Normalise. Rescale or recentre each counterexample so that they are comparable, for example so that the quantity of interest equals $1$.
3. Extract a limit. Use a compactness theorem to pass to a subsequence that converges to some limiting object.
4. Examine the limit. Show that the limit has a property no object can have, or one that contradicts the normalisation.
5. Conclude. The assumption was false, so the uniform bound holds.

The first instance comes in 2A.9 Continuous Functions: a continuous function on a closed interval $[a, b]$ is bounded. Suppose not; then for each $n$ there is a point $x_n$ with $|f(x_n)| > n$. By Bolzano–Weierstrass (2A.6 Sequences) some subsequence converges to a point $x$ of $[a, b]$. By continuity, $f$ at nearby points is close to $f(x)$, yet $|f(x_{n_k})| \to \infty$. Contradiction. The pattern is visible even in this small case: counterexamples, a limit, a contradiction at the limit.

5.7Equality and substitution

One last piece of logic is used so constantly it is easy to overlook. Equality is an equivalence relation (reflexive, symmetric, transitive), and equal things can be substituted for each other in any statement: if $x = y$ then $P(x) \iff P(y)$, and $f(x) = f(y)$ for any function $f$. That is what makes a chain of equalities a proof.

The second half, $x = y \implies f(x) = f(y)$, is not automatic when objects are defined as equivalence classes. It is exactly the well-definedness that had to be checked for every operation on integers, rationals and reals (2A.3 Integers and Rationals, 2A.4 The Real Numbers). A "function" that fails it isn't a function. So the logic of equality and the construction of quotients are two sides of the same requirement.

5.8Exercises

Solution

(a) $\exists M\ \forall n: |a_n| \leq M$. Negation: $\forall M\ \exists n: |a_n| > M$ ("for every bound, some term exceeds it"). (b) $\exists N\ \forall n \geq N: a_n = a_N$. Negation: $\forall N\ \exists n \geq N: a_n \neq a_N$. (c) $\forall \varepsilon > 0\ \exists \delta > 0\ \forall x: |x| < \delta \implies |f(x) - f(0)| < \varepsilon$. Negation: $\exists \varepsilon > 0\ \forall \delta > 0\ \exists x: |x| < \delta$ and $|f(x) - f(0)| \geq \varepsilon$ ("there are points arbitrarily close to $0$ where $f$ is at least $\varepsilon$ away from $f(0)$"). (d) As in Example 5.3 with $X = \mathbb{R}$. Negation: $\exists \varepsilon > 0\ \forall \delta > 0\ \exists x, y: |x - y| < \delta$ and $|f(x) - f(y)| \geq \varepsilon$. (e) $\forall S \subseteq \mathbb{N}: S \neq \varnothing \implies \exists m \in S\ \forall s \in S: m \leq s$. Negation: $\exists S \subseteq \mathbb{N}: S \neq \varnothing$ and $\forall m \in S\ \exists s \in S: s < m$.

Solution

(a) The first is true and the second false: there is no largest real. (b) The first is true (take $y = x$), the second false: it would need a single $y$ with $y^2 = x^2$ for every $x$. (c) Both are true: $x = 0$ works for every $y$ in the first, and then the second follows, since $\exists\forall$ always implies $\forall\exists$.

Hint

$x^3 - 8 = (x - 2)(x^2 + 2x + 4)$. If $|x - 2| < 1$ then $1 < x < 3$, so $x^2 + 2x + 4 < 19$.

Solution

First statement: given $\varepsilon$, choose $N$ with $N \geq 1/\varepsilon$; then for $n \geq N$, $1 - \tfrac{n}{n+1} = \tfrac{1}{n+1} < \tfrac1N \leq \varepsilon$. Second: whatever $N$ you choose, the adversary picks $n = N$ and $\varepsilon = \tfrac{1}{2(N+1)}$; then $\tfrac{N}{N+1} = 1 - \tfrac{1}{N+1} < 1 - \varepsilon$.

Solution

(a) $\exists \kappa > 0\ \forall g\ \forall (x, t)\ \forall r < \rho$: $\big(|\mathrm{Rm}| \leq r^{-2}$ on $B(x, r)\big) \implies \operatorname{vol} B(x, r) \geq \kappa r^3$. (b) $\forall \kappa > 0\ \exists g\ \exists (x, t)\ \exists r < \rho$: $|\mathrm{Rm}| \leq r^{-2}$ on $B(x, r)$ and $\operatorname{vol} B(x, r) < \kappa r^3$. (c) Taking $\kappa = 1/k$ gives, for each $k$, a flow and a ball of radius $r_k$ on which curvature is controlled at the scale $r_k$, but whose volume is less than $r_k^3/k$: balls that are more and more "collapsed" relative to their size. (Perelman's actual proof of this theorem doesn't use compactness. It uses a monotone quantity, the $\mathcal{W}$-entropy, which you'll meet in 12A.3 The 𝓦-Entropy.)