8.2 The Quantifier Rules in Prose

Section 8.1 read the connective rules in the sentences of written proofs. The statements of analysis, though, are made of “for every” and “there exists”, and most of the words in an analysis proof carry a quantifier rule: “let”, “fix”, “choose”, “take”, “will do”. This section completes the dictionary with the rows for the quantifiers, equality and unique existence, for definitions, “the” and double inclusion, and for the patterns that are not single rules but are written as if they were: the lemma (“it suffices to show”) and its two “stronger” cases, induction, and symmetry (“without loss of generality”). It also makes exact one habit of analysis prose, the parenthesis “(depending on $\varepsilon$ )”.

8.2.1. Three sentences, three rules

Section 6.1 derived “if $a_n \to L$ , then $2a_n \to 2L$ ” in sixteen lines. Written the way a mathematician writes it, the same argument takes three sentences:

Let $\varepsilon > 0$ . Since $a_n \to L$ and $\varepsilon/2 > 0$ , we may choose $N \in \mathbb{N}$ (depending on $\varepsilon$ ) such that $\left| a_n - L \right| < \varepsilon/2$ for every $n \ge N$ . Then for every $n \ge N$ , $\left| 2a_n - 2L \right| = 2\left| a_n - L \right| < \varepsilon$ .

Here is the derivation of Section 6.1 again, with the same line numbers. To keep its lines short, write $A(n, \varepsilon)$ for $\left| a_n - L \right| < \varepsilon$ and $B(n, \varepsilon)$ for $\left| 2a_n - 2L \right| < \varepsilon$ .

\forall \varepsilon > 0 \; \exists N \in \mathbb{N} \; \forall n \in \mathbb{N} \; (n \ge N \to A(n, \varepsilon))

\varepsilon_0

\varepsilon_0 > 0

asm, for

\mathrm{{\forall}I}

\varepsilon_0 / 2 > 0

arith 2

\exists N \in \mathbb{N} \; \forall n \in \mathbb{N} \; (n \ge N \to A(n, \varepsilon_0 / 2))

\mathrm{{\forall}E}

1, 3

N_0

N_0 \in \mathbb{N}

asm, for

\mathrm{{\exists}E}

\forall n \in \mathbb{N} \; (n \ge N_0 \to A(n, \varepsilon_0 / 2))

asm, for

\mathrm{{\exists}E}

n_0

n_0 \in \mathbb{N}

asm, for

\mathrm{{\forall}I}

n_0 \ge N_0 \to A(n_0, \varepsilon_0 / 2)

\mathrm{{\forall}E}

6, 7

n_0 \ge N_0

asm, for

\mathrm{{{\to}}I}

A(n_0, \varepsilon_0 / 2)

\mathrm{{{\to}}E}

8, 9

B(n_0, \varepsilon_0)

arith 10

n_0 \ge N_0 \to B(n_0, \varepsilon_0)

\mathrm{{{\to}}I}

9–11

\forall n \in \mathbb{N} \; (n \ge N_0 \to B(n, \varepsilon_0))

\mathrm{{\forall}I}

7–12

\exists N \in \mathbb{N} \; \forall n \in \mathbb{N} \; (n \ge N \to B(n, \varepsilon_0))

\mathrm{{\exists}I}

5, 13

\exists N \in \mathbb{N} \; \forall n \in \mathbb{N} \; (n \ge N \to B(n, \varepsilon_0))

\mathrm{{\exists}E}

4, 5–14

\forall \varepsilon > 0 \; \exists N \in \mathbb{N} \; \forall n \in \mathbb{N} \; (n \ge N \to B(n, \varepsilon))

\mathrm{{\forall}I}

2–15

Sentence	Lines
“Let $\varepsilon > 0$ .”	opens the box 2–15; its closing line 16 is not written
“Since $a_n \to L$ and $\varepsilon/2 > 0$ , we may choose $N$ …”	3 and 4, then opens the box 5–14
“Then for every $n \ge N$ , $\left\| 2a_n - 2L \right\| = 2\left\| a_n - L \right\| < \varepsilon$ .”	7–13
(the paragraph ends)	14, 15, 16

Each sentence opens a box, and the boxes are nested in the order of the sentences.

“Let $\varepsilon > 0$ ” opens the bounded $\mathrm{\forall I}$ box of lines 2–15 in the derivation above, with the fresh name $\varepsilon_0$ . Its closing line, line 16, is not written: the paragraph simply ends, and a reader who heard “let” knows that the box closes there.
“Choose $N$ …” is two rules. The words “since $a_n \to L$ and $\varepsilon/2 > 0$ ” are the $\mathrm{\forall E}$ of line 4, at the term $\varepsilon_0/2$ , with its bound from line 3. The word “choose” opens the $\mathrm{\exists E}$ box of lines 5–14, with the fresh name $N_0$ .
“Then for every $n \ge N$ ” opens the $\mathrm{\forall I}$ box of $n_0$ and the $\mathrm{{\to}I}$ box of $n_0 \ge N_0$ (lines 7 and 9), and the computation is lines 8, 10 and 11. The words “for every $n \ge N$ ” also announce the lines that close these two boxes, 12 and 13.
The $\mathrm{\exists I}$ of line 14, which writes “some $N$ works” from “this $N$ works”, and the closing line 15 of the $\mathrm{\exists E}$ box, are silent. They are the end of the paragraph.

The one word in the paragraph that no rule asks for is the parenthesis “(depending on $\varepsilon$ )”. It is the subject of a subsection below. First, the rows.

8.2.2. The quantifier rows

Rule	Phrases	Silent in plain prose?
$\mathrm{\forall I}$	“let $x \in A$ ”; “fix $\varepsilon > 0$ ”; “let $\varepsilon > 0$ be given”; “since $x$ was arbitrary”	never the introduction; “since $x$ was arbitrary” may be silent
$\mathrm{\forall E}$	“in particular, for $x = \dots$ ”; “applying … with $\varepsilon/2$ in place of $\varepsilon$ ”	the instance must be named when it is not the obvious one
$\mathrm{\exists I}$	“take $N = \dots$ ”; “let $\delta \mathrel{:=} \dots$ ; then …”; “… will do”	never; its dependencies are stated
$\mathrm{\exists E}$	“choose $N$ such that”; “by hypothesis there is $k$ with $n = 2k$ ”; “let $x_0$ be such a point”	never; the name must be fresh

The phrases in the table are mostly the bounded forms of the rules (Proposition 6.1.1): “let $x \in A$ ” opens a $\mathrm{\forall I}$ box whose assumption is $x \in A$ , and “choose $N \in \mathbb{N}$ such that …” opens an $\mathrm{\exists E}$ box with the two assumptions $N \in \mathbb{N}$ and “…”. A bound is part of the phrase: “let $\varepsilon > 0$ ” is one step, not “let $\varepsilon$ ” followed by “suppose $\varepsilon > 0$ ”.

In analysis, $\mathrm{\forall I}$ is the first sentence of every limit proof: “Let $\varepsilon > 0$ .” $\mathrm{\forall E}$ is “apply the definition of $a_n \to L$ with $\varepsilon/2$ ”: the instance $\varepsilon/2$ is not the obvious one, so it is named. $\mathrm{\exists I}$ is the line that places a constant, “let $\delta \mathrel{:=} \min\{1, \varepsilon/10\}$ ”, written before the computation that shows it works. $\mathrm{\exists E}$ is “choose $N$ (depending on $\varepsilon$ ) such that …”, in which the name $N$ has not been used before in the proof.

Example (A constant sequence)

Let $c$ be a real number and let $a_n \mathrel{:=} c$ for every $n \in \mathbb{N}$ . Prove that $a_n \to c$ , and annotate each phrase with its rule.

Solution. Let $\varepsilon > 0$ [ $\mathrm{\forall I}$ , opening]. Take $N \mathrel{:=} 0$ [ $\mathrm{\exists I}$ ]. Let $n \in \mathbb{N}$ with $n \ge N$ [ $\mathrm{\forall I}$ , $\mathrm{{\to}I}$ , opening]. Then $\left| a_n - c \right| = \left| c - c \right| = 0 < \varepsilon ,$ where the first equality substitutes $a_n = c$ [ $\mathrm{{=}E}$ ] and the last step uses $\varepsilon > 0$ , the assumption of the first box. This proves $a_n \to c$ .

The last sentence stands for three closing lines, all silent: the $\mathrm{{\to}I}$ and $\mathrm{\forall I}$ for $n$ (“for every $n \ge N$ ”), and the $\mathrm{\forall I}$ for $\varepsilon$ (“since $\varepsilon$ was arbitrary”). The witness “take $N \mathrel{:=} 0$ ” is placed before the work that justifies it.

Two things here are degenerate, and both are worth seeing once. The witness $N$ depends on nothing: any $N \in \mathbb{N}$ works. And the assumption $n \ge N$ is never used. The box is still opened, because the goal $\forall n \in \mathbb{N}\; (n \ge N \to \dots)$ asks for it; without “let $n \ge N$ ”, the line “ $\left| a_n - c \right| = 0$ ” would not say which $n$ it is about.

8.2.3. The dependency parenthesis

In the paragraph that opened this section, $N$ was chosen “(depending on $\varepsilon$ )”. Section 6.4 read off a derivation the rule behind the parenthesis:

A constant chosen in a box may depend on the names of the boxes open around that box, and it does depend only on the names in the line it comes from.

In the derivation of Section 6.1, the witness $N_0$ is obtained at line 5 from line 4, which mentions $\varepsilon_0$ , inside the box of $\varepsilon_0$ only. So $N_0$ may depend on $\varepsilon_0$ , and it does. In the derivation of Example (Uniformly continuous implies continuous), the witness $\delta_0$ is obtained inside the boxes of $x_0$ and $\varepsilon_0$ , so it may depend on both; but it comes from a line that mentions $\varepsilon_0$ alone, so it does depend only on $\varepsilon_0$ , and that is uniformity.

$Diagram. Labels: may, but does not, (a) continuity at every point, let x in A, let varepsilon > 0, choose delta, the line delta comes from:\mentions x and varepsilon, (b) uniform continuity, the line delta comes from:\mentions varepsilon only$

A chosen constant may depend on the names of the boxes it sits in, and does depend only on the names in the line it comes from (the solid arrows).

Numbers show why the arrows matter. Take $f(x) = x^2$ and $\varepsilon = 1$ . At the point $a \ge 0$ , the largest $\delta$ with $\left| x^2 - a^2 \right| < 1$ for every $x$ with $\left| x - a \right| < \delta$ is $\sqrt{a^2 + 1} - a$ : about $0.41$ at $a = 1$ , and about $0.005$ at $a = 100$ . No single $\delta$ serves every point, so $\delta$ must depend on the point as well as on $\varepsilon$ : panel (a). For $f(x) = 3x + 1$ , $\left| f(x) - f(a) \right| = 3\left| x - a \right|$ , so $\delta = \varepsilon/3$ works at every point at once: $\delta$ depends on $\varepsilon$ only, panel (b).

The parenthesis is the prose record of this. “Choose $N$ (depending on $\varepsilon$ )” says: the boxes open here are those of $\varepsilon$ (besides the data of the theorem, such as the sequence), and the line from which $N$ comes mentions $\varepsilon$ . “Choose $\delta$ (depending on $\varepsilon$ and on $x$ )” says that $\delta$ came from a line mentioning both, inside both boxes. A witness that came from a line mentioning neither is a constant, and the proof may say “(depending on neither)” or simply “a fixed $\delta$ ”. This is why proofs in analysis say what each chosen constant depends on. A missing parenthesis is not a wrong step, but it hides the one fact a reader most needs in order to check the quantifier order, and many false proofs in analysis go wrong exactly there.

Quick check. For $f(x) = x^2$ and $\varepsilon = 1$ , does $\delta = 0.1$ work at the point $a = 2$ ? At $a = 10$ ?

Solution. At $a = 2$ , yes, since $0.1 < \sqrt 5 - 2 \approx 0.236$ . At $a = 10$ , no: $x = 10.06$ has $\left| x - 10 \right| = 0.06 < 0.1$ and $x^2 - 100 = 1.2036 \ge 1$ .

Example (The reciprocals tend to zero)

Prove that $1/n \to 0$ , for the sequence $(1/n)_{n \ge 1}$ . Annotate each phrase with its rule, and state what the chosen constant depends on.

Solution. The sequence starts at $n = 1$ , so in the definition of Section 6.1 the numbers $N$ and $n$ range over the positive integers $\mathbb{Z}_{>0}$ . We use one school fact about the real numbers: for every real number $u$ there is an integer greater than $u$ . (It follows from the axioms for the real numbers; here we take it as known.)

Let $\varepsilon > 0$ [ $\mathrm{\forall I}$ , opening]. It suffices to find $N \in \mathbb{Z}_{>0}$ with $\frac{1}{N} < \varepsilon , \tag{$\ast$}$ since then every $n \in \mathbb{Z}_{>0}$ with $n \ge N$ has $0 < 1/n \le 1/N < \varepsilon$ , so $\left| 1/n - 0 \right| < \varepsilon$ [it suffices: the claim ( $\ast$ ) displayed, then used].

By the school fact, applied to $u = 1/\varepsilon$ [ $\mathrm{\forall E}$ ], there is an integer greater than $1/\varepsilon$ ; choose such an integer $N$ [ $\mathrm{\exists E}$ ], which depends on $\varepsilon$ . Since $\varepsilon > 0$ , we have $1/\varepsilon > 0$ , so $N > 0$ and $N \in \mathbb{Z}_{>0}$ . From $N > 1/\varepsilon > 0$ , taking reciprocals reverses the inequality: $1/N < \varepsilon$ , which is ( $\ast$ ). So this $N$ will do [ $\mathrm{\exists I}$ ], and $1/n \to 0$ .

Read the proof as a skeleton. The first sentence opens the box of $\varepsilon$ . The second is an “it suffices to show”, in the sense of the row below: it states a simpler claim ( $\ast$ ), shows on the spot that ( $\ast$ ) is enough, and leaves ( $\ast$ ) to be proved. The next paragraph proves ( $\ast$ ). It contains two different quantifier steps that both concern $N$ : “choose” is the $\mathrm{\exists E}$ on the school fact, which hands over some integer beyond $1/\varepsilon$ and calls it $N$ ; “will do” is the $\mathrm{\exists I}$ that offers this $N$ as the witness the definition asks for. Between them, the clause “so $N > 0$ and $N \in \mathbb{Z}_{>0}$ ” checks the bound $N \in \mathbb{Z}_{>0}$ of the witness, which the bounded $\mathrm{\exists I}$ needs as a line.

The constant $N$ depends on $\varepsilon$ only: it came from the school fact at $1/\varepsilon$ , inside the box of $\varepsilon$ . For instance, $\varepsilon = 0.03$ has $1/\varepsilon = 33.3\ldots$ , and $N = 34$ is a choice that works; so is any larger integer.

Quick check. “For every $\varepsilon > 0$ , $\left| a_n - L \right| < \varepsilon$ for all large $n$ .” Where is the hidden $\exists N$ , and between which two quantifiers does it stand?

Solution. “For all large $n$ ” is “there is an $N$ such that for every $n \ge N$ ” (Section 6.1): the hidden $\exists N$ stands after $\forall \varepsilon > 0$ and before $\forall n \ge N$ . Written out, the sentence is $\forall \varepsilon > 0 \; \exists N \in \mathbb{N} \; \forall n \in \mathbb{N} \; (n \ge N \to \left| a_n - L \right| < \varepsilon)$ , the definition of $a_n \to L$ . Since $\exists N$ comes after $\forall \varepsilon$ , the $N$ may depend on $\varepsilon$ .

8.2.4. Equality and unique existence

Rule	Phrases	Silent in plain prose?
$\mathrm{{=}I}$ , $\mathrm{{=}E}$	“substituting”; chains “ $\dots = \dots = \dots$ ”; “by (1)”	yes, inside chains
$\exists!$	“there is exactly one”; “existence … uniqueness …”; “suppose $y$ also …”	never either half

In analysis, $\mathrm{{=}E}$ is at work in every chain of equalities and inequalities, such as $\left| x^2 - 4 \right| = \left| x - 2 \right|\, \left| x + 2 \right| \le 5 \left| x - 2 \right| \quad \text{for } \left| x - 2 \right| < 1 ,$ where each $=$ link substitutes equals for equals and each inequality link applies one fact about order (Section 5.7). (Here $\left| x - 2 \right| < 1$ gives $1 < x < 3$ , so $3 < x + 2 < 5$ .) The $\mathrm{{=}I}$ lines $t = t$ that such chains rest on are never written. Unique existence (Definition 5.8.1) has two halves, which Proposition 5.8.1 separates: “ $2x + 3 = 7$ has exactly one real solution: $x = 2$ is one, and if $2y + 3 = 7$ , then $y = 2$ ”. The first clause is existence, by $\mathrm{\exists I}$ ; the second is uniqueness, a $\mathrm{\forall I}$ and $\mathrm{{\to}I}$ box on a second candidate. Neither half implies the other, so neither may be silent.

The uniqueness half often stands alone, when existence is not claimed or is proved elsewhere. Uniqueness of limits is a case of this kind.

Example (A sequence has at most one limit)

Let $(a_n)$ be a sequence of real numbers with $a_n \to L$ and $a_n \to M$ . Prove that $L = M$ , and annotate each phrase with its rule.

Solution. Let $\varepsilon > 0$ [ $\mathrm{\forall I}$ , opening]. Then $\varepsilon/2 > 0$ , so, applying the definition of $a_n \to L$ with $\varepsilon/2$ in place of $\varepsilon$ [ $\mathrm{\forall E}$ ], we may choose $N_1 \in \mathbb{N}$ (depending on $\varepsilon$ ) such that $\left| a_n - L \right| < \varepsilon/2$ for every $n \ge N_1$ [ $\mathrm{\exists E}$ , fresh name $N_1$ ]. Likewise, from $a_n \to M$ , choose $N_2 \in \mathbb{N}$ (depending on $\varepsilon$ ) such that $\left| a_n - M \right| < \varepsilon/2$ for every $n \ge N_2$ [ $\mathrm{\forall E}$ , $\mathrm{\exists E}$ , fresh name $N_2$ ]. Let $n \mathrel{:=} \max\{N_1, N_2\}$ . Then $n \in \mathbb{N}$ , $n \ge N_1$ and $n \ge N_2$ , so both bounds apply at $n$ [ $\mathrm{\forall E}$ at $n$ , twice, with $\mathrm{{\to}E}$ ], and $\begin{aligned} \left| L - M \right| &= \left| (L - a_n) + (a_n - M) \right| \\ &\le \left| a_n - L \right| + \left| a_n - M \right| < \frac{\varepsilon}{2} + \frac{\varepsilon}{2} = \varepsilon , \end{aligned}$ where the inequality is the triangle inequality of Example (The triangle inequality by cases), with $\left| L - a_n \right| = \left| a_n - L \right|$ . Since $\varepsilon > 0$ was arbitrary, $\left| L - M \right| < \varepsilon$ for every $\varepsilon > 0$ [ $\mathrm{\forall I}$ , closing], and Proposition 6.2.5 gives $L = M$ [ $\mathrm{{\to}E}$ , citing it].

Four things in this proof are never silent, and each is visible. The instance $\varepsilon/2$ is named twice, because it is not the obvious instance. The two witnesses get two names, $N_1$ and $N_2$ : the hypotheses promise a threshold for $L$ and a threshold for $M$ , and nothing says they are the same number, so calling both $N$ would assert an equality nobody proved (Section 8.6 catalogues the error). The point $n = \max\{N_1, N_2\}$ is named, since the bounds are applied at it. And the closing result is cited by name.

Second readingThe bookkeeping of the two choices

What is silent is the bookkeeping of the two $\mathrm{\exists E}$ boxes. The line $\left| L - M \right| < \varepsilon$ mentions neither $N_1$ , $N_2$ nor $n$ , so the side condition of $\mathrm{\exists E}$ lets it leave both boxes, and then the box of $\varepsilon$ closes on it. The calculation chain hides its $\mathrm{{=}E}$ steps, as the row allows. The proof shows that a sequence has at most one limit: the uniqueness half of $\exists!$ . Whether a given sequence has a limit at all is a separate question, which this proof does not touch.

8.2.5. Definitions, descriptions and sets

Three more phrases do logical work in almost every chapter of analysis: “we define”, “the”, and “the two sets are equal”.

Pattern	Phrases	Silent in plain prose?
a definition (a definitional extension, Proposition 5.8.2)	“we define $f(x) \mathrel{:=} \dots$ ”; “call $n$ perfect if …”; “write $d$ for …”	never the definition; its uses ( $\mathrm{{\leftrightarrow}E}$ or $\mathrm{{=}E}$ with it) yes
“the” (a definite description, Definition 5.8.3)	“let $L$ be the limit of $(a_n)$ ”; “the least element of $A$ ”; “ $\lim a_n$ ”	never the existence and uniqueness behind “the”: proved or cited before the name is used
double inclusion	“we show $A \subseteq B$ and $B \subseteq A$ ”; element chasing: “let $x \in A$ ; … so $x \in B$ ”; “so $A = B$ ”	never either inclusion, nor the opening “let $x \in \dots$ ” of each, nor the appeal to extensionality that turns “the same elements” into $A = B$

“The”, as in “the limit”, names an object. It may be used only once there is exactly one such object (Section 5.8): for a limit, existence is the hypothesis that $(a_n)$ converges, and uniqueness is Example (A sequence has at most one limit). Chapter 5 read $A \subseteq B$ as $\forall x\, (x \in A \to x \in B)$ . Two inclusions give $\forall x\, (x \in A \leftrightarrow x \in B)$ , by $\mathrm{{\leftrightarrow}I}$ inside $\mathrm{\forall I}$ : the two sets have the same elements. Each inclusion is an element chase: “let $x \in A$ ” opens a bounded $\mathrm{\forall I}$ box whose last line is $x \in B$ . The last step, from “the same elements” to $A = B$ , is not logic. Logic gives only the converse, that equal sets have the same elements (Example (Equal Sets Have the Same Elements)). The step itself is the axiom of extensionality, an axiom about sets (Section 5.7), and a proof cites it, as a premise or with the words “by extensionality”; it is never silent.

Second readingWhat a definition adds

A definition adds a word and proves nothing new about the old words (Proposition 5.8.2, Section 5.8). So “we define” writes an abbreviation, and every later use of it is $\mathrm{{\leftrightarrow}E}$ or $\mathrm{{=}E}$ with the definition.

Example (Two inclusions)

Let $A \mathrel{:=} \{ x \in \mathbb{R} : x^2 \le 2x \}$ and $B \mathrel{:=} \{ x \in \mathbb{R} : 0 \le x \le 2 \}$ . Prove that $A = B$ , and tag the steps that carry the logic.

Solution.

$(\subseteq)$ Let $x \in A$ [assumption for $\mathrm{\forall I}$ ]; so $x^2 \le 2x$ , that is, $x(x - 2) \le 0$ .
- If $x < 0$ , then $x - 2 < 0$ too, and a product of two negative numbers is positive: $x(x - 2) > 0$ . This clashes with $x(x - 2) \le 0$ [ $\mathrm{\neg E}$ ], so $x < 0$ is impossible [ $\mathrm{\neg I}$ ], and $x \ge 0$ by trichotomy.
- If $x > 2$ , then both factors are positive and the same clash follows. So $x \le 2$ .
- Hence $0 \le x \le 2$ [ $\mathrm{\wedge I}$ ], and $x \in B$ .
$(\supseteq)$ Let $x \in B$ [assumption for $\mathrm{\forall I}$ ]; so $x \ge 0$ and $x - 2 \le 0$ [ $\mathrm{\wedge E}$ ]. A product of a non-negative and a non-positive number is at most $0$ , so $x(x - 2) \le 0$ , that is, $x^2 \le 2x$ , and $x \in A$ .
So $A \subseteq B$ and $B \subseteq A$ : every real $x$ has $x \in A \leftrightarrow x \in B$ [ $\mathrm{{\leftrightarrow}I}$ inside $\mathrm{\forall I}$ ]. By extensionality, $A = B$ [ $\mathrm{\forall E}$ , $\mathrm{{\to}E}$ with the axiom].

The words “that is” unwind the two sets’ definitions ( $\mathrm{{\leftrightarrow}E}$ , silent at level 3).

Quick check. To prove $\{ n \in \mathbb{Z} : n^2 \text{ is even} \} = \{ n \in \mathbb{Z} : n \text{ is even} \}$ by double inclusion, which inclusion is a theorem of Chapter 2, and which takes one line?

Solution. $\subseteq$ is Theorem 2.1.3. $\supseteq$ is one line: $n = 2k$ gives $n^2 = 2(2k^2)$ .

8.2.6. Induction, lemmas and symmetry

The rows of this table are not rules of the calculus. Each is a pattern of rules that proofs announce with a phrase of its own.

Pattern	Phrases	Silent in plain prose?
it suffices to show; a lemma (a cut, Lemma 2.3.3)	“we first show (Claim)”; “it suffices to show”; “we claim”	never the claim itself; “it suffices” may be dropped if the claim is displayed and then used
it suffices to prove something stronger	“it suffices to prove the stronger …”; “in fact more is true: …”	never the stronger claim; the step from it to the goal may be silent when it is one $\mathrm{\wedge E}$ , $\mathrm{\vee I}$ or chain link
a stronger hypothesis gives a weaker theorem	“in particular, for $x \in (0, 1)$ ”; “since every such $x$ has $\left\| x \right\| < 1$ , the result applies”	the narrowing of the hypothesis, never
induction (Axiom 4.2.1, Theorem 4.2.2)	“we argue by induction on $n$ ”; “base case”; “suppose the claim holds for $n$ ”	never either the base case or the step; the induction hypothesis is stated
symmetry	“without loss of generality”; “similarly”; “by symmetry”	allowed only when the swap turns the statement and the hypotheses into themselves, up to identities such as $\left\| b - a \right\| = \left\| a - b \right\|$

It suffices to show

“It suffices to show $\varphi$ ” does two things. It shows on the spot that $\varphi$ gives the goal, and it leaves $\varphi$ to be proved: the goal is replaced by $\varphi$ . As Section 1.3 observed, to show $\psi$ it suffices to show $\varphi$ when $\varphi \to \psi$ is in hand. A lemma is the same move in the other order: prove $\varphi$ first, then use it as if it were a premise. (Logicians call both a cut; Lemma 2.3.3 (b) is the precise statement.) In analysis, “it suffices to show $\left| a_n - L \right| < \varepsilon$ for $n \ge N$ ” reduces a limit to one estimate; Example (The reciprocals tend to zero) made one with the claim ( $\ast$ ).

Diagram. Labels: shown at once, proved next, the goal, the claim varphi, the hypotheses

“It suffices to show $\varphi$ ”: the solid step is written on the spot, the dashed one is the rest of the proof.

Quick check. In Example (The reciprocals tend to zero), which sentence is the “it suffices” step, and what does it leave to prove?

Solution. “It suffices to find $N \in \mathbb{Z}_{>0}$ with $1/N < \varepsilon$ , since then …”. It leaves ( $\ast$ ), which the next paragraph proves.

Two cases of the move have names of their own. To prove $\psi$ it suffices to prove a stronger $\varphi$ from which $\psi$ follows at once: to show $x^2 < 1$ for $0 < x < 1$ , show $x^2 < x$ , and then $x^2 < x < 1$ . And a theorem stays true when its hypothesis is narrowed: from “if $\left| x \right| < 1$ , then $x^2 < 1$ ” and “every $x \in (0, 1)$ has $\left| x \right| < 1$ ”, the chain of Proposition 1.4.1 gives “if $x \in (0, 1)$ , then $x^2 < 1$ ”: a stronger hypothesis, a weaker theorem.

Second readingStronger and weaker, in general

Both moves are instances of one fact about where a part sits in a formula. Weakening a part in a positive place, such as the conclusion of an implication, weakens the whole; weakening a part in a negative place, such as the hypothesis, strengthens the whole. The second-pass Section 4.9 states and proves this as Theorem 4.9.5; nothing on the main line uses it.

Induction

An induction is $\mathrm{{\to}E}$ applied to Axiom 4.2.1, whose hypothesis is a conjunction: the base case $P(0)$ , and the step “for every $n \in \mathbb{N}$ , if $P(n)$ then $P(n + 1)$ ”. So the step is a $\mathrm{\forall I}$ box with a $\mathrm{{\to}I}$ box inside it, and the phrase “suppose the claim holds for $n$ ” opens the inner box; its assumption is the induction hypothesis, and it must be stated, because the step uses it.

$Diagram. Labels: toE on the induction axiom, base case:\P (0), step: let n in nN ;\suppose P(n); dots ; P(n + 1), forall n in nN \; P(n)$

An induction: two inputs to one implication, the induction axiom (Axiom 4.2.1). The step is two boxes, the box of $n$ and, inside it, the box of the induction hypothesis $P(n)$ .

Without loss of generality

Symmetry is a case split $\mathrm{\vee E}$ whose second box is the first with two letters exchanged. “Without loss of generality $x \le y$ ” writes the first box and leaves the second to the reader, who must be able to get it by swapping the letters; that works when the statement and the hypotheses come back unchanged under the swap, up to identities such as $\left| b - a \right| = \left| a - b \right|$ .

$Diagram. Labels: swap a leftrightarrow b, case a le b:\\dots \ Longrightarrow claim, case b le a: the same lines\with a, b swapped Longrightarrow claim, veeE on ``a le b or b le a''$

“Without loss of generality $a \le b$ ”: the solid case is written, the dashed one is left to the reader, who gets it by the swap.

Quick check. May a proof that $x^2 + y^2 \ge 2xy$ for all real $x$ , $y$ begin “Without loss of generality $x \le y$ ”?

Solution. Yes: swapping $x$ and $y$ leaves the statement unchanged, and there are no hypotheses. The case split is legitimate, though not needed, since $x^2 + y^2 - 2xy = (x - y)^2 \ge 0$ .

Example (An induction, and a legitimate symmetry)

(a) Let $a$ be a real number with $0 < a \le 1$ . Prove that $0 < a^n \le 1$ for every $n \in \mathbb{N}$ , and annotate each phrase with its rule.
(b) Let $a$ and $b$ be real numbers. Prove that $\left| a - b \right| = \max\{a, b\} - \min\{a, b\}$ , with a “without loss of generality”, and write out the case split it abbreviates.

Solution. (a) For $n \in \mathbb{N}$ , let $P(n)$ be the statement “ $0 < a^n$ and $a^n \le 1$ ”. We argue by induction on $n$ , using Axiom 4.2.1.

Base case. $a^0 = 1$ , and $0 < 1$ and $1 \le 1$ , so $P(0)$ holds [ $\mathrm{\wedge I}$ ].

Step. Let $n \in \mathbb{N}$ [ $\mathrm{\forall I}$ , opening], and suppose $P(n)$ holds, that is, $0 < a^n$ and $a^n \le 1$ [ $\mathrm{{\to}I}$ , opening: the induction hypothesis]. Then $a^{n+1} = a^n a$ . Since $a^n > 0$ [ $\mathrm{\wedge E}$ ] and $a > 0$ , the product $a^n a$ is positive, so $0 < a^{n+1}$ . Since $a \le 1$ and $a^n > 0$ , multiplying gives $a^n a \le a^n$ , and $a^n \le 1$ [ $\mathrm{\wedge E}$ ], so $a^{n+1} \le 1$ . Hence $P(n + 1)$ holds [ $\mathrm{\wedge I}$ ].

By induction, $P(n)$ holds for every $n \in \mathbb{N}$ Axiom 4.2.1.

The base case is the first hypothesis of Axiom 4.2.1, written as its own paragraph. The step is the second: “let $n \in \mathbb{N}$ ” and “suppose $P(n)$ holds” open its two boxes, and “hence $P(n + 1)$ ” is the last line of the inner one; the closing lines “so $P(n) \to P(n + 1)$ , for every $n$ ” are silent. The induction hypothesis is stated in full, and each of its halves is taken out by $\mathrm{\wedge E}$ and used: $a^n > 0$ twice (for the sign of $a^{n+1}$ , and to multiply $a \le 1$ by $a^n$ without reversing it), and $a^n \le 1$ once, at the end. The statement was chosen with care: the tempting “ $a^n \le a$ ” fails at $n = 0$ whenever $a < 1$ , since $a^0 = 1$ , and an induction for it would have to start at $n = 1$ .

(b) Without loss of generality, $a \le b$ . Then $\max\{a, b\} = b$ and $\min\{a, b\} = a$ , and since $b - a \ge 0$ , $\left| a - b \right| = \left| b - a \right| = b - a = \max\{a, b\} - \min\{a, b\} .$

The phrase abbreviates a $\mathrm{\vee E}$ on “ $a \le b$ or $b \le a$ ”, which holds for all real $a, b$ by trichotomy. The first box is the paragraph above. The second box, on $b \le a$ , reads: then $\max\{a, b\} = a$ and $\min\{a, b\} = b$ , and since $a - b \ge 0$ , $\left| a - b \right| = a - b = \max\{a, b\} - \min\{a, b\}$ . That is the first box with $a$ and $b$ exchanged throughout, read through three identities: $\left| b - a \right| = \left| a - b \right|$ , $\max\{b, a\} = \max\{a, b\}$ , and $\min\{b, a\} = \min\{a, b\}$ . These say that the statement is unchanged when $a$ and $b$ are exchanged, and there are no hypotheses to check. This is what makes the swap exact, and so what licenses “without loss of generality”.

Warning. “Without loss of generality” needs a statement and hypotheses that are unchanged by the swap. Here is a false “proof” that $\max\{a, b\} = b$ for all real $a, b$ : “Without loss of generality $a \le b$ ; then $\max\{a, b\} = b$ .” Exchanging $a$ and $b$ turns the claim into $\max\{b, a\} = a$ , which is a different claim, so the second case is not the first one in disguise; and indeed $a = 2$ , $b = 1$ gives $\max\{a, b\} = 2 \ne 1$ . Before writing “without loss of generality”, swap the letters in the statement and the hypotheses, and check that each comes back unchanged, up to identities such as $\left| b - a \right| = \left| a - b \right|$ .

8.2.7. What the sentence does not say

Some quantifiers in mathematical English are not written at all, and some are written where they do not apply. Four habits of mathematical English cover most of them.

The hidden universal closure. A theorem stated as “if $n$ is even, then $n^2$ is even” means “for every integer $n$ , if $n$ is even, then $n^2$ is even”. Section 5.1 introduced this convention: a letter that is not introduced anywhere, in the statement of a theorem, is read with a “for every” in front of the whole statement. It applies to the statement of a theorem, lemma or exercise, not to a line inside a proof: inside a proof every letter has been introduced by a “let” or a “choose”, and its box tells the reader which. The proof of such a theorem begins by opening the hidden box: “let $n$ be an integer”.

“For all large $n$ ” hides an $\exists N$ and a bound, as the Quick check above found. “Eventually” means the same. The negation of “ $P(n)$ for all large $n$ ” is “for every $N$ there is an $n \ge N$ for which $P(n)$ fails”, usually said “ $P(n)$ fails for infinitely many $n$ ”.

“Any” can mean “every” or “some”, and only the rest of the sentence decides (Section 5.1). “Any $x \in A$ is positive” means every element of $A$ is positive. “If any $x \in A$ is positive, then $A$ is non-empty” means: if some element of $A$ is positive. When “any” appears, rewrite the sentence once with “every” and once with “some”, and keep the one that was meant.

Quantifiers at the end of a sentence. English lets a writer put “for some $x$ ” or “for all $y$ ” after the formula they govern, and then the order of two such phrases is unclear. “ $x^2 > y$ for some $x$ for all $y$ ”, over $\mathbb{R}$ , has two readings: $\forall y\, \exists x\; (x^2 > y) \qquad \text{and} \qquad \exists x\, \forall y\; (x^2 > y) .$ The first is true (for $y \ge 0$ take $x = y + 1$ , since $(y + 1)^2 = y^2 + 2y + 1 > y$ ; for $y < 0$ take $x = 0$ ). The second is false (whatever $x$ is proposed, $y = x^2$ refutes it). The remedy is to write the quantifiers of such a statement in front, in the order in which they apply. A trailing phrase such as “for every $n \ge N$ ” is safe only when it is the last quantifier of the sentence, as in the definition of $a_n \to L$ .

Warning. Moving “for all $x$ ” to the end of a sentence can change continuity into uniform continuity. “ $\left| f(x) - f(y) \right| < \varepsilon$ whenever $\left| x - y \right| < \delta$ , for all $x$ ”, written after “for every $\varepsilon > 0$ there is $\delta > 0$ such that”, does not say whether $\forall x$ comes before $\exists \delta$ (continuity at every point) or after it (uniform continuity). The two formulas of Section 6.4 differ exactly there, and Example (The square function on the real line) shows that the difference is real: $f(x) = x^2$ on $\mathbb{R}$ satisfies the first and not the second. Write the quantifiers in front.

Warning (Not allowed: quantifier steps in prose). Each sentence below might appear in a proof, and each is wrong. The tag names the entry of the catalogue in Section 8.6, or the item of the convention on silent steps in Section 8.3, that it breaks.

“Let $\varepsilon > 0$ and choose $N$ with $\left| a_n - L \right| < \varepsilon$ for every $n \ge N$ . This $N$ works for every $\varepsilon > 0$ .” The $N$ was chosen inside the box of one $\varepsilon$ : (N2).
“Some $x \in A$ has $f(x) > 0$ . Let $x \in A$ ; then $f(x) > 0$ .” The witness of an existential is chosen (“choose $x \in A$ with $f(x) > 0$ ”, $\mathrm{\exists E}$ with a fresh name). Written with “let”, the second sentence claims $f(x) > 0$ for every $x \in A$ : (N3).
“Choose $N$ with $\left| a_n - L \right| < \varepsilon/2$ for $n \ge N$ , and $N$ with $\left| b_n - M \right| < \varepsilon/2$ for $n \ge N$ .” One name for two witnesses: (N4).
“Let $L$ be the limit of $(a_n)$ ”, in a proof that has not shown that $(a_n)$ converges: (N14).
“Let $\varepsilon > 0$ . Then $\left| a_n - L \right| < \varepsilon$ for every $n \ge N$ , as required”, where no sentence says what $N$ is. The witness of $\mathrm{\exists I}$ , with what it depends on, is never silent (Definition 8.3.2, Section 8.3).

8.2.8. Exercises

A. Check your understanding

Exercise (A1)

Let $(a_n)$ be a sequence of real numbers and $L$ a real number. Here is a proof that if $a_n \to L$ and $L > 0$ , then $a_n > 0$ for all large $n$ . Its sentences are numbered.

Suppose $a_n \to L$ and $L > 0$ . (2) Then $L/2 > 0$ . (3) Choose $N \in \mathbb{N}$ such that $\left| a_n - L \right| < L/2$ for every $n \ge N$ . (4) Let $n \in \mathbb{N}$ with $n \ge N$ . (5) Then $L - a_n \le \left| a_n - L \right| < L/2$ , so $a_n > L/2 > 0$ . (6) Hence $a_n > 0$ for every $n \ge N$ , that is, $a_n > 0$ for all large $n$ .

(a) Name the rule or rules carried by each sentence.
(b) Sentence (3) has no dependency parenthesis. What should it say, and why does $N$ not depend on $n$ ?
(c) Which instance of $\mathrm{\forall E}$ in the proof is not the obvious one?
(d) Which closing lines are silent?

Solution. (a) (1) $\mathrm{{\to}I}$ , opening: the hypothesis of the theorem is assumed (its two conjuncts are then available by $\mathrm{\wedge E}$ ). (2) An arithmetic step from $L > 0$ . (3) $\mathrm{\forall E}$ on the definition of $a_n \to L$ at $L/2$ , with its bound from (2), then $\mathrm{\exists E}$ , opening a box with the fresh name $N$ . (4) $\mathrm{\forall I}$ and $\mathrm{{\to}I}$ , opening the boxes of $n$ and of $n \ge N$ . (5) $\mathrm{\forall E}$ at $n$ and $\mathrm{{\to}E}$ on the line from (3), giving $\left| a_n - L \right| < L/2$ ; then the school fact $-u \le \left| u \right|$ with $u = a_n - L$ , and arithmetic. (6) $\mathrm{{\to}I}$ and $\mathrm{\forall I}$ , closing (“for every $n \ge N$ ”), then $\mathrm{\exists I}$ with the witness $N$ (“for all large $n$ ” is $\exists N\, \forall n \ge N$ ), and the $\mathrm{\exists E}$ box of (3) closes, since the conclusion does not mention $N$ .

(b) “Choose $N \in \mathbb{N}$ (depending on $L$ ) such that …”. $N$ is obtained at line (3), from the definition instantiated at $L/2$ , a term that mentions $L$ (and the sequence, which is data). The box of $n$ is opened only at (4), after $N$ is chosen, so $N$ cannot depend on $n$ .

(c) The instance $\varepsilon = L/2$ in (3). It is the instance the proof is built around: any $\varepsilon$ with $0 < \varepsilon \le L$ would do, and $L/2$ leaves the margin $a_n > L/2$ .

(d) The closing lines of the $\mathrm{\exists E}$ box (3) and of the $\mathrm{{\to}I}$ box (1), “hence, if $a_n \to L$ and $L > 0$ , then …”. Sentence (6) writes the closings of the boxes of (4) in words, and the $\mathrm{\exists I}$ through “that is”.

Exercise (A2: Drill)

Each part takes a line or two. Most parts ask which rule a phrase carries, whether it may be silent, or for a judgment or a sentence.

(a) “Fix $\varepsilon > 0$ .” Which rule, and may it be silent?
(b) “Applying the hypothesis with $\varepsilon/3$ in place of $\varepsilon$ .” Which rule, and may the term go unnamed?
(c) “Take $\delta \mathrel{:=} \varepsilon/5$ .” Which rule, may it be silent, and what does $\delta$ depend on?
(d) “By hypothesis there is $k$ with $m = 2k + 1$ ; choose such a $k$ .” Which rule, and what does it require of the name?
(e) In “Let $\varepsilon > 0$ . Choose $N$ such that … . Let $n \ge N$ .”, may $N$ depend on $n$ ?
(f) In “Let $x \in A$ . Let $\varepsilon > 0$ . Choose $\delta > 0$ such that …”, may $\delta$ depend on $x$ ?
(g) Write “ $x^2 > 0$ for all $x \ne 0$ ” with the quantifier in front.
(h) Negate “ $a_n > 0$ for all large $n$ ” with no $\neg$ in front of a quantifier.
(i) A proof of “ $\max\{a, b\} \ge a$ ” begins “Without loss of generality $a \le b$ .” Is that legitimate?
(j) In an induction, which sentence opens the box of the induction hypothesis?
(k) To prove $A = B$ , a proof shows $A \subseteq B$ and $B \subseteq A$ . Which rules does that pattern use, and how does each inclusion open?
(l) A proof begins “Let $m$ be the least element of $A$ ”. What must already be on the page?

Solution.

(a) Bounded $\mathrm{\forall I}$ , opening; never silent.
(b) $\mathrm{\forall E}$ at a term that is not the obvious one; the term must be named.
(c) $\mathrm{\exists I}$ ’s witness, written before the work; never silent; it depends on $\varepsilon$ .
(d) $\mathrm{\exists E}$ , with a fresh name.
(e) No: the box of $n$ opens after $N$ is chosen.
(f) It may, since both boxes are open; whether it does depends on the line it comes from.
(g) $\forall x\, (x \ne 0 \to x^2 > 0)$ .
(h) For every $N$ there is $n \ge N$ with $a_n \le 0$ .
(i) No: the swap turns the claim into $\max\{b, a\} \ge b$ , a different claim; each case needs its own line (both are one line long).
(j) “Suppose $P(n)$ holds”, inside “Let $n \in \mathbb{N}$ ”.
(k) $\mathrm{{\leftrightarrow}I}$ inside $\mathrm{\forall I}$ , for $\forall x\, (x \in A \leftrightarrow x \in B)$ ; then $A = B$ by $\mathrm{\forall E}$ and $\mathrm{{\to}E}$ with the axiom of extensionality, cited. Each inclusion is a bounded $\mathrm{\forall I}$ that opens with “let $x \in A$ ” (or “let $x \in B$ ”).
(l) That such an element exists and that there is only one ( $\exists!$ , a definite description). Uniqueness is one line, since two least elements are each at most the other; existence is the part that needs a reason.

B. Practice

Exercise (B1: Ambiguous English)

Each sentence has a quantifier phrase at its end. Write both readings in symbols, with the quantifiers in front, and decide whether each reading is true for the function given.

(a) “ $f(x) \le M$ for every real $x$ , for some real $M$ ”, for $f(x) = x$ .
(b) “ $x + y = 0$ for some real $y$ , for every real $x$ .”
(c) “ $\left| x - y \right| < \delta$ implies $\left| f(x) - f(y) \right| < 1$ for all real $x, y$ , for some $\delta > 0$ ”, for $f(x) = x^2$ .

Solution. (a) $\exists M\, \forall x\; (f(x) \le M)$ , “ $f$ is bounded above”, and $\forall x\, \exists M\; (f(x) \le M)$ . For $f(x) = x$ the first is false: whatever $M$ is proposed, $x = M + 1$ has $f(x) = M + 1 > M$ . The second is true for every function: given $x$ , take $M = f(x)$ .

(b) $\forall x\, \exists y\; (x + y = 0)$ and $\exists y\, \forall x\; (x + y = 0)$ . The first is true: given $x$ , take $y = -x$ . The second is false: for any $y$ , the two values $x = -y$ and $x = 1 - y$ give $x + y = 0$ and $x + y = 1$ , so not every $x$ works.

(c) $\exists \delta > 0\; \forall x\, \forall y\; (\left| x - y \right| < \delta \to \left| f(x) - f(y) \right| < 1)$ and $\forall x\, \forall y\; \exists \delta > 0\; (\left| x - y \right| < \delta \to \left| f(x) - f(y) \right| < 1)$ . For $f(x) = x^2$ the first is false: it is the uniform continuity condition at $\varepsilon = 1$ , and Example (The square function on the real line) refutes it with $x = 1/\delta$ , $y = 1/\delta + \delta/2$ , for which $\left| x - y \right| < \delta$ and $\left| x^2 - y^2 \right| = 1 + \delta^2/4 \ge 1$ . The second is true for every function: given $x$ and $y$ , if $x = y$ then $\left| f(x) - f(y) \right| = 0 < 1$ for any $\delta$ , say $\delta = 1$ ; if $x \ne y$ , take $\delta = \left| x - y \right|$ , so that $\left| x - y \right| < \delta$ is false and the implication holds vacuously.

In (a) and (c), the reading with $\exists$ in front is the one a writer means; the other is true of every function, so it says nothing about $f$ . In (b), the intended reading is $\forall x\, \exists y$ . Written with the quantifiers in front, the sentences say what they mean: “there is $M$ such that $f(x) \le M$ for every $x$ ”, “for every $x$ there is $y$ with $x + y = 0$ ”, “there is $\delta > 0$ such that for all $x, y$ , …”.

Exercise (B2: An induction, annotated)

Prove that $5^n - 1$ is divisible by $4$ for every $n \in \mathbb{N}$ . Annotate each phrase of your proof with its rule, and say which hypothesis of Axiom 4.2.1 each part of the proof establishes.

Solution. For $n \in \mathbb{N}$ , let $P(n)$ be “ $4 \mid 5^n - 1$ ”, that is, “there is an integer $k$ with $5^n - 1 = 4k$ ”. We argue by induction on $n$ .

Base case. $5^0 - 1 = 0 = 4 \cdot 0$ , so $P(0)$ holds, with the witness $k = 0$ [ $\mathrm{\exists I}$ ]. This is hypothesis (i) of Axiom 4.2.1.

Step. Let $n \in \mathbb{N}$ [ $\mathrm{\forall I}$ , opening], and suppose $P(n)$ holds [ $\mathrm{{\to}I}$ , opening: the induction hypothesis]. By the induction hypothesis there is an integer $k$ with $5^n - 1 = 4k$ ; choose such a $k$ (depending on $n$ ) [ $\mathrm{\exists E}$ , fresh name $k$ ]. Then $5^{n+1} - 1 = 5 \cdot 5^n - 1 = 5(5^n - 1) + 4 = 5 \cdot 4k + 4 = 4(5k + 1) ,$ where the third equality substitutes $5^n - 1 = 4k$ [ $\mathrm{{=}E}$ ]. Since $5k + 1$ is an integer, $P(n + 1)$ holds, with the witness $5k + 1$ [ $\mathrm{\exists I}$ ]. The step is hypothesis (ii) of Axiom 4.2.1: the $\mathrm{\forall I}$ on $n$ and the $\mathrm{{\to}I}$ on $P(n)$ .

By induction, $4 \mid 5^n - 1$ for every $n \in \mathbb{N}$ Axiom 4.2.1.

The $\mathrm{\exists E}$ box of $k$ closes on “ $P(n + 1)$ ”, which does not mention $k$ , as its side condition requires; its closing line, and those of the two boxes of the step, are silent.

Exercise (B3: Six, two and three, used later)

Let $A \mathrel{:=} \{ n \in \mathbb{Z} : 6 \mid n \}$ and $B \mathrel{:=} \{ n \in \mathbb{Z} : 2 \mid n \text{ and } 3 \mid n \}$ . Prove $A = B$ by double inclusion. Name each “let”, each “choose” with its fresh name, and each witness.

Solution.

$(\subseteq)$ Let $n \in A$ [ $\mathrm{\forall I}$ ], and choose $k$ with $n = 6k$ [ $\mathrm{\exists E}$ , $k$ fresh]. Then $n = 2(3k)$ and $n = 3(2k)$ , so $2 \mid n$ and $3 \mid n$ , with the witnesses $3k$ and $2k$ [ $\mathrm{\exists I}$ twice, $\mathrm{\wedge I}$ ]; so $n \in B$ .
$(\supseteq)$ Let $n \in B$ [ $\mathrm{\forall I}$ ]. Choose $a$ with $n = 2a$ and $b$ with $n = 3b$ [ $\mathrm{\exists E}$ twice, two fresh names: one name for both would be (N4)]. Then $b = 3b - 2b = n - 2b = 2a - 2b = 2(a - b)$ , so $n = 3b = 6(a - b)$ , and $6 \mid n$ with the witness $a - b$ [ $\mathrm{\exists I}$ ]; so $n \in A$ .
So every integer $n$ has $n \in A \leftrightarrow n \in B$ [ $\mathrm{{\leftrightarrow}I}$ inside $\mathrm{\forall I}$ ], and by extensionality $A = B$ .

The two $\mathrm{\exists E}$ boxes of $(\supseteq)$ close on “ $n \in A$ ”, which mentions neither $a$ nor $b$ .

Marking scheme. (10 points) - 2: $(\subseteq)$ , with $k$ chosen and both witnesses written. - 4: $(\supseteq)$ : two choices with distinct names (1); the computation $b = 2(a - b)$ , or another valid route to an integer $c$ with $n = 6c$ (2); the witness named (1). - 2: the double-inclusion frame: both inclusions, each opened by “let $n \in \dots$ ”, and the conclusion $A = B$ by extensionality, cited. - 2: the tags: $\mathrm{\forall I}$ , $\mathrm{\exists E}$ with fresh names, $\mathrm{\exists I}$ .

Fatal errors (0 for the step): one name for both witnesses; “ $2 \mid n$ and $3 \mid n$ , so $6 \mid n$ ” asserted without an argument (N9).

C. Going deeper

Exercise (C1: When “similarly” is honest)

(a) Prove that $\max\{x, y\} + \min\{x, y\} = x + y$ for all real $x$ and $y$ , with a “without loss of generality”. Then write out the $\mathrm{\vee E}$ it abbreviates, and check that its second box is the first with the letters exchanged.
(b) Let $x \ge 0$ and $y$ be real numbers. A student proves $x \max\{x, y\} \ge xy$ as follows: “Without loss of generality $x \le y$ . Then $\max\{x, y\} = y$ , and $xy \ge xy$ .” Explain why “without loss of generality” is not legitimate here, prove the case the student skipped, and show by an example that the hypothesis $x \ge 0$ cannot be dropped from the statement.

Solution (Hint 1). In (b), exchange $x$ and $y$ in the statement and in the hypothesis, and compare with the original.

Solution (Hint 2). In the case $y \le x$ , $\max\{x, y\} = x$ , and the claim becomes $x^2 \ge xy$ .

Solution. (a) Without loss of generality $x \le y$ . Then $\max\{x, y\} = y$ and $\min\{x, y\} = x$ , so $\max\{x, y\} + \min\{x, y\} = y + x = x + y$ .

The phrase abbreviates $\mathrm{\vee E}$ on “ $x \le y$ or $y \le x$ ”, true for all real $x, y$ by trichotomy. Box 1, on $x \le y$ , is the paragraph above. Box 2, on $y \le x$ : then $\max\{x, y\} = x$ and $\min\{x, y\} = y$ , so $\max\{x, y\} + \min\{x, y\} = x + y$ . Exchanging $x$ and $y$ in box 1 gives “ $y \le x$ ; $\max\{y, x\} = x$ , $\min\{y, x\} = y$ ; $\max\{y, x\} + \min\{y, x\} = x + y = y + x$ ”, which is box 2 read through $\max\{y, x\} = \max\{x, y\}$ , $\min\{y, x\} = \min\{x, y\}$ and $y + x = x + y$ . These identities say that the statement is unchanged by the exchange, and there are no hypotheses, so the swap is exact.

(b) Exchanging $x$ and $y$ changes both the hypothesis and the claim: it gives “ $y \ge 0$ , and $y \max\{y, x\} \ge yx$ ”, which is not the original statement. So the case $y \le x$ is not the case $x \le y$ in disguise, and it needs its own argument.

Case $y \le x$ . Then $\max\{x, y\} = x$ , and multiplying $x \ge y$ by $x \ge 0$ gives $x \max\{x, y\} = x^2 \ge xy$ .

With the student’s case ( $x \le y$ : $x \max\{x, y\} = xy \ge xy$ ), this proves the claim in either case. The hypothesis $x \ge 0$ is used only in the skipped case. It cannot be dropped: $x = -1$ , $y = -2$ has $\max\{x, y\} = -1$ , so $x \max\{x, y\} = 1$ , while $xy = 2$ , and $1 \ge 2$ is false.

Marking scheme. (10 points) - 2: (a) a correct computation in the case $x \le y$ . - 3: (a) the $\mathrm{\vee E}$ written out, with its disjunction justified, and the exchange checked against the statement. - 2: (b) the reason: the exchange changes the hypothesis and the claim. - 2: (b) the case $y \le x$ proved, using $x \ge 0$ . - 1: (b) a counterexample without $x \ge 0$ , checked. Fatal errors (0 for the step): in (b), “the other case is similar” without computing it; a counterexample that satisfies $x \ge 0$ .

Exercise (C2: Moving a quantifier changes the meaning)

Give an example of a sentence of analysis, in English, that begins “for every $x$ …”, whose meaning changes when the phrase “for every $x$ ” is moved to the end of the sentence. Write both readings in symbols and show that one is true and the other false.

Solution. An example. “For every real $x > 0$ , there is $n \in \mathbb{Z}_{>0}$ with $1/n < x$ .” Moved: “There is $n \in \mathbb{Z}_{>0}$ with $1/n < x$ , for every real $x > 0$ .” The readings are $\forall x > 0\; \exists n \in \mathbb{Z}_{>0}\; (1/n < x) \qquad \text{and} \qquad \exists n \in \mathbb{Z}_{>0}\; \forall x > 0\; (1/n < x) .$ The first is true: given $x > 0$ , there is an integer $n > 1/x$ (the school fact of Example (The reciprocals tend to zero)), and $n > 1/x > 0$ gives $n \in \mathbb{Z}_{>0}$ and $1/n < x$ . The second is false: whatever $n \in \mathbb{Z}_{>0}$ is proposed, $x = 1/n$ is positive and $1/n < x$ fails. (It is natural to read the moved sentence as the second formula, since its “for every $x$ ” now comes after “there is $n$ ”; whichever reading a reader picks, the sentence no longer says one thing.)

What a different answer must have, so that it can be checked against this one: - the sentence contains “for every $x$ ” and at least one existential quantifier (“there is”, “for some”) whose scope contains a formula mentioning $x$ ; - moved to the end, “for every $x$ ” can be read as coming after the existential quantifier, so that the witness may no longer depend on $x$ ; - both readings are written in symbols with all quantifiers in front, and there is a specific interpretation (here $\mathbb{R}$ with its usual order) in which one reading is true and the other false, each claim checked; - the false reading is refuted by naming, for each candidate witness, a value of $x$ that defeats it. Another correct answer, for $f(x) = x^2$ on $\mathbb{R}$ , is “for every $x$ , for every $\varepsilon > 0$ there is $\delta > 0$ such that $\left| f(x) - f(y) \right| < \varepsilon$ whenever $\left| x - y \right| < \delta$ ” (continuity, true); with “for every $x$ ” moved to the end, it becomes the sentence of the warning, whose uniform-continuity reading Example (The square function on the real line) refutes.