8.5  Writing a Proof

Solution. Step 3. Unwound in step 2, the goal begins $\mathrm{\forall }\epsilon >0$, so its skeleton is a bounded $\mathrm{\forall }\mathrm{I}$ box whose assumption is ${\epsilon }_0>0$; “Let $\epsilon >0$” is the first line of that box. Step 6 keeps it, because the opening of a $\mathrm{\forall }\mathrm{I}$ box is never silent (Definition 8.3.2). The closing “since $\epsilon$ was arbitrary” may be silent.

Solution. Steps 1 and 2: the goal in symbols, unwound. Over the domain $\mathbb{R}$, “$B$ is bounded above” is $\mathrm{\exists }M\mathrm{\forall }b\in B(b\le M)$ (Section 6.1), and $A\subseteq B$ is $\mathrm{\forall }x\in A(x\in B)$. The statement is an implication, so the derivation below is the inside of a $\to \mathrm{I}$ box: its assumption is the first formula (line 2), the hypothesis is the second, and its goal is $\mathrm{\exists }M\mathrm{\forall }a\in A(a\le M)$.

Givens	Goal
$A\subseteq B$; $B$ bounded above	$A$ bounded above
$\mathrm{\forall }x\in A(x\in B)$; $\mathrm{\exists }M\mathrm{\forall }b\in B(b\le M)$	$\mathrm{\exists }M\mathrm{\forall }a\in A(a\le M)$
$\mathrm{\forall }x\in A(x\in B)$; $\mathrm{\forall }b\in B(b\le M_0)$ ($\mathrm{\exists }\mathrm{E}$, $M_0$ fresh)	$\mathrm{\exists }M\mathrm{\forall }a\in A(a\le M)$
the same	$\mathrm{\forall }a\in A(a\le M_0)$ (try the witness $M_0$)
the same, and $a_0\in A$ ($\mathrm{\forall }\mathrm{I}$, $a_0$ fresh)	$a_0\le M_0$
the same, and $a_0\in B$ ($\mathrm{\forall }\mathrm{E}$ at $a_0$)	$a_0\le M_0$ ✓ ($\mathrm{\forall }\mathrm{E}$ at $a_0$)

The second row is step 2; each later row is one move of steps 3 and 4; the table’s last row is where the search ends.

Step 3: the skeleton. The goal is an existential, so it is postponed: no witness is in sight yet. The assumption “$B$ is bounded above” (line 2) is an existential, so its $\mathrm{\exists }\mathrm{E}$ box opens at once, with a fresh name $M_0$ and the assumption $\mathrm{\forall }b\in B(b\le M_0)$; the box’s last line is the goal.

Step 4: filling the box. Backwards: the goal needs a witness $M$ and a proof of $\mathrm{\forall }a\in A(a\le M)$. The only bound in sight is $M_0$, so try it. Then the new goal is a bounded universal: a box “let $a_0\in A$” whose last line is $a_0\le M_0$. That line comes from the bound on $B$, instantiated at $a_0$, which needs $a_0\in B$; and $a_0\in B$ comes from $A\subseteq B$ instantiated at $a_0$. Forwards, the same lines in the order of the list are the derivation below (with the bounded rules of Proposition 6.1.1; each bounded $\mathrm{\forall }\mathrm{E}$ abbreviates a $\mathrm{\forall }\mathrm{E}$ and a $\to \mathrm{E}$, and the bounded $\mathrm{\forall }\mathrm{I}$ box a $\mathrm{\forall }\mathrm{I}$ box with a $\to \mathrm{I}$ box inside).

The side conditions hold: $a_0$ appears in neither line 1 nor line 2, not in line 7 and not in the open assumption on line 3; $M_0$ appears in none of lines 1, 2 and 9.

Step 5: the constant. The witness for the goal is the bound $M_0$. The search could choose it only once the $\mathrm{\exists }\mathrm{E}$ box supplied $M_0$, and confirm it only at line 6; the page writes it first, in the sentence that chooses it. It depends on $B$ only: its box is opened before the box of $a_0$, so it cannot depend on $a_0$, and it must not, because a single bound has to serve every element of $A$.

Step 6: level 3.

Suppose $B$ is bounded above, and choose an upper bound $M$ of $B$ (depending on $B$ only). Let $a\in A$. Since $A\subseteq B$, we have $a\in B$, and so $a\le M$. Hence $M$ is an upper bound of $A$, and $A$ is bounded above.

The two instances of $\mathrm{\forall }\mathrm{E}$ (lines 5 and 6) are at the obvious term $a$, and each appears only as the citation that licenses it (“since $A\subseteq B$”, “so”, which cites the choice of $M$). The closing of the $\mathrm{\forall }\mathrm{I}$ box, “since $a$ was arbitrary”, is silent. Two steps that are never silent are on the page: the $\mathrm{\exists }\mathrm{E}$ with its fresh name (“choose an upper bound $M$”), and the $\mathrm{\exists }\mathrm{I}$ with its witness and dependence (“$M$ is an upper bound of $A$”; “depending on $B$ only”). “Suppose $B$ is bounded above” opens the $\to \mathrm{I}$ box; its closing is silent.

Step 7: reread. The order of the first two sentences matters. With “let $a\in A$” first and $M$ chosen inside, the $\mathrm{\exists }\mathrm{I}$ would fall inside the box of $a_0$, giving only $\mathrm{\forall }a\in A\mathrm{\exists }M(a\le M)$, which says nothing.

Solution. “Hence $M$ is an upper bound of $A$” offers $M$ as the witness; it was chosen in sentence 1. Chosen after “Let $a\in A$”, $M$ would sit inside the box of $a$, and the proof would give only $\mathrm{\forall }a\in A\mathrm{\exists }M(a\le M)$, which says nothing (step 7 of the example).

Solution. “Let $\epsilon >0$, and let $\delta :=\epsilon /3$, which is positive and depends on $\epsilon$ only. Let $x$ be a real number with $|x-2|<\delta$.”

Solution.

Sentence	What it does	Rule
(1)	opens a box with the hypothesis	assumption for $\to \mathrm{I}$
(2)	states the disjunction the split needs	a fact about real numbers
(3)	opens the first case	assumption for $\vee \mathrm{E}$
(4)		algebra
(5)	opens the second case	assumption for $\vee \mathrm{E}$
(6)		algebra
(7)	uses the assumption of (1), whose box is still open	algebra
(8)	combines the cases, then closes the outer box	$\vee \mathrm{E}$ on (2), (3)–(4), (5)–(7); then $\to \mathrm{I}$

Sentence (7) uses the assumption made in (1), and it may: that box is still open.

Measured against Definition 8.3.2, nothing that must be written is missing: the split is on the page with a disjunction that covers every real $x$, each case opens with its assumption, and what is left out may be silent. Labeling also shows where the work is: the case split exists only because $|\cdot |$ is defined by cases, and the school fact $-\left|u\right|\le u$, used with $u=x-1$, gives $-1<x-1$ in one step, with no $\vee \mathrm{E}$ at all.

Solution.

Every integer is even or odd, so we consider two cases. If $n$ is even, then $n(n+1)$ has an even factor, and so it is even. If $n$ is odd, then $n+1$ is even, since an odd number plus one is even; so again $n(n+1)$ has an even factor and is even. In either case $n(n+1)$ is even.

Compare the two. The paragraph keeps one sentence for each box and each rule that matters: line 1 becomes “we consider two cases”, with its reason; the two boxes become the two “if” sentences; line 10 becomes “in either case”. It drops the line numbers and the rule names, and it merges the two $\to \mathrm{E}$ steps of lines 8 and 9 into one sentence joined by “so”. It never skips a box: the reader still sees both cases and sees them combined.

By Definition 8.3.2, the closing “in either case …” could be dropped at level 3; the split of line 1, with the reason it covers every integer, could not. The paragraph leaves the premises unproved. Premises 2–4 are one line of algebra each (for instance, $n=2k$ gives $n(n+1)=2(k(n+1))$), and a careful write-up includes them; premise 1, that every integer is even or odd, is the fact (E1) that this volume takes as known.

Solution. (P1) does not generalize: it uses a fact about $18$ alone. (P2) does, once its one particular fact, $17=3\cdot 5+2$, is replaced by what every integer has: $n=3k$, $n=3k+1$ or $n=3k+2$ for an integer $k$, a school fact.

Let $n$ be an integer [assumption for $\mathrm{\forall }\mathrm{I}$]. Dividing by $3$, there is an integer $k$ with $n=3k$, $n=3k+1$ or $n=3k+2$; choose such a $k$ [$\mathrm{\exists }\mathrm{E}$]. If $n=3k$, $n$ is a multiple of $3$. If $n=3k+1$, then $n+2=3(k+1)$. If $n=3k+2$, then $n+1=3(k+1)$. In every case one of the three is a multiple of $3$ [$\vee \mathrm{E}$]. Since $n$ was arbitrary, this holds for every integer [$\mathrm{\forall }\mathrm{I}$].

(P2) was the third case, with $k=5$.

The test: after renaming, can every line still be justified from what the box of $n$ assumes? A line that computes with the particular number fails the test.

Solution. No: it computes with $7$. A general proof writes $n=2k+1$, so $n^2-1=4k(k+1)$, and shows that $k(k+1)$ is even, since one of $k$, $k+1$ is even. That is the proof of Exercise (B2: Back from prose to a skeleton, with blanks).

Solution. (a)

Sentence	Rule
(1)	assumption, opening the $\to \mathrm{I}$ box
(2)	assumption $\mathrm{\neg }(x>1\vee y>1)$, opening an $\mathrm{RAA}$ box
(3)	Proposition 2.5.5 (a), $\mathrm{\neg }(P\vee Q)⊢\mathrm{\neg }P\wedge \mathrm{\neg }Q$, applied to (2)
(4)	$\wedge \mathrm{E}$ on (3), twice; $\to \mathrm{E}$ with the order fact “$\mathrm{\neg }(a>1)$ implies $a\le 1$”, twice; then $\wedge \mathrm{I}$
(5)	$\wedge \mathrm{E}$ on (4), then $\to \mathrm{E}$ with “$a\le 1$ and $b\le 1$ imply $a+b\le 2$”
(6)	$\to \mathrm{E}$ with the order fact “$a\le 2$ implies $\mathrm{\neg }(a>2)$” on (5), then $\mathrm{\neg }\mathrm{E}$ on (1) and the result
(7)	$\mathrm{RAA}$ on the box (2)–(6); then $\to \mathrm{I}$ on (1)–(7)

(b) Sentence (7) closes the $\mathrm{RAA}$ box: the box opened with the negation of the goal $x>1\vee y>1$ and closes with the goal itself. Sentence (3) uses De Morgan’s law (a), a direction derived without $\mathrm{RAA}$.

(c) It wears face (iii), genuine $\mathrm{RAA}$, but it is a contrapositive in costume, as in Example (A contrapositive in costume): the hypothesis (1) is used only at the clash, and everything else derives $x+y\le 2$ from $x\le 1$ and $y\le 1$. The rewrite opens: “We prove the contrapositive: if $x\le 1$ and $y\le 1$, then $x+y\le 2$.” The rewrite is clearer, but it does not remove the classical step: passing from the contrapositive back to the claim is Proposition 2.5.2, which uses $\mathrm{RAA}$.

(d) The closing of the $\to \mathrm{I}$ box (“so if $x+y>2$, then …”) may be silent. The conclusion of the $\mathrm{RAA}$ box, “hence $x>1$ or $y>1$”, may not.

Solution.

Solution. (a) Let $n$ be an integer, and suppose $n$ is odd. Choose an integer $k$ with $n=2k+1$. Then $$3n+5=6k+3+5=2(3k+4),$$ and $3k+4$ is an integer, so $3n+5$ is even.

“Choose an integer $k$” is the $\mathrm{\exists }\mathrm{E}$ box, with a fresh name; the witness $3k+4$ of line 4 is on the page, and it depends on $k$, hence on $n$. Lines 5, 6 and 7 close boxes and are silent.

(b) Suppose, to the contrary, that some real $x$ satisfies $x^2+1=2x-1$, and fix such an $x$. Rearranging, $x^2-2x+2=0$, that is, $(x-1{)}^2+1=0$. But $(x-1{)}^2\ge 0$, since a square is non-negative, so $1\le 0$, which is false. Hence no real $x$ satisfies the equation.

“Suppose, to the contrary” opens the $\mathrm{\neg }\mathrm{I}$ box of line 1 (the goal is a negation, so no classical rule is used), and “fix such an $x$” the $\mathrm{\exists }\mathrm{E}$ box. The clash of lines 5–7 is named, and the conclusion of the $\mathrm{\neg }\mathrm{I}$ box is written; line 8 is silent.

(c) Let $x$ be real.

$(\Rightarrow )$ Suppose $x^3=x$. Then $(x+1)x(x-1)=x^3-x=0$. A product of real numbers is zero only if a factor is zero, so $x+1=0$, $x=0$ or $x-1=0$; that is, $x=-1$, $x=0$ or $x=1$.

$(\Leftarrow )$ Suppose $x=-1$, $x=0$ or $x=1$. In the three cases, $x^3=-1=x$, $x^3=0=x$ and $x^3=1=x$.

This proves the equivalence.

Both directions are written, and the citation in line 3 is visible. The two splits of $(\Leftarrow )$ are merged into “in the three cases”; the disjunction split is the hypothesis itself, and the closing lines 12 and 13 are silent.

Solution. An admissible order: (v), (x), (ii), (viii), (i), (iv), (ix), (vi).

The only other admissible order swaps (x) and (ii), which use only $\epsilon$ and one hypothesis each. Nothing else moves: (viii) uses $N_1$ and $N_2$; (i) uses $N$; (iv) uses $n\ge N$ and the definition of $N$; (ix) uses (iv), (x) and (ii) at this $n$, and the triangle inequality (Example (The triangle inequality by cases)); (vi) closes the boxes of $n$ and $\epsilon$, with the $\mathrm{\exists }\mathrm{I}$ of the witness $N$ inside “$a_n+b_n\to L+M$”. The maximum exists because there are finitely many numbers.

Distractor (iii) claims that $N_1$ and $N_2$ serve every $\epsilon$ at once. They were chosen from $\mathrm{\forall }\epsilon \mathrm{\exists }N$, inside the box of $\epsilon$, so they depend on $\epsilon$ and serve only the $\epsilon$ they were chosen for; a uniform $N$ would need $\mathrm{\exists }N\mathrm{\forall }\epsilon$, which the hypothesis does not give. This is the error that Section 8.6 catalogues as (N2). For $a_n=1/(n+1)$, $L=0$, no single $N_1$ serves every $\epsilon >0$: at $\epsilon =1/(N_1+2)$ the term $a_{N_1}=1/(N_1+1)$ is too far from $0$.

Distractor (vii) applies the hypothesis at $\epsilon$ instead of $\epsilon /2$. It is a legal step, but with it in place of (x), the bound in (ix) becomes $|(a_n+b_n)-(L+M)|<\epsilon +\epsilon /2$, not $<\epsilon$, so (ix) would no longer follow. It is an $\epsilon$ of the wrong kind for the goal.

Solution. The move is skeleton first: the blank is line 8, the line written after the $\mathrm{\neg }\mathrm{I}$ box of lines 4–7 closes, a line the skeleton fixes before any arithmetic. That box assumed “$x+y$ is rational” and reached $\mathrm{\perp }$ at line 7, so line 8 concludes its negation. It is the first face of “by contradiction” (Section 8.1), proof of a negative statement, and uses no classical rule: “irrational” means “not rational”, so the goal of the outer box, line 8, is a negation, and the inner box is opened on $x+y\in \mathbb{Q}$ with goal $\mathrm{\perp }$.

Completion. “Hence $x+y$ is not rational, that is, $x+y$ is irrational.”

The conclusion of a $\mathrm{\neg }\mathrm{I}$ box is never silent (Definition 8.3.2), so this sentence must be written even though the reader can guess it. Line 9, the closing of the $\to \mathrm{I}$ box, may stay silent. The sentence before the blank, “this contradicts the irrationality of $y$”, is line 7, the clash of $\mathrm{\neg }\mathrm{E}$, which names both lines it cites.

Solution. (a) (P2) generalizes; (P1) computes with $7$ and says nothing about another $n$.

(b) Let $n$ be an integer. Then $n^3-n=(n-1)n(n+1)$, a product of three consecutive integers. By Example (One of three, generalized), applied to $n-1$, one of $n-1$, $n$, $n+1$ is a multiple of $3$, so $3\mid n^3-n$ (a product with a factor divisible by $d$ is divisible by $d$: if $a=dc$, then $ab=d(cb)$). By (E1), $n$ is even or odd: if $n$ is even, the factor $n$ is even; if odd, $n-1$ is even. So one factor is even, and $2\mid n^3-n$. Since $2$ and $3$ divide it, so does $6$ (by Exercise (B3: Six, two and three, used later), the inclusion $\supseteq$: if $m=2a=3b$, then $b=2(a-b)$ and $m=6(a-b)$).

(c) “If $2\mid m$ and $3\mid m$, then $6\mid m$”, the fact of Exercise (B3: Six, two and three, used later).

Marking scheme. (10 points) - 2: (a) (P2), with the reason (P1) fails. - 2: (b) the factorization and the fresh name. - 2: (b) a multiple of $3$ among the factors, cited or proved. - 2: (b) an even factor, from (E1). - 1: (b) the step from $2$ and $3$ to $6$, proved or cited. - 1: (c) the fact named. Fatal errors (0 for the step): a proof that checks finitely many $n$ (N1); “$2\mid m$ and $3\mid m$, so $6\mid m$” with neither proof nor citation (N9).

Solution (Hint 1). Compute $|f(x)-f(a)|$ in terms of $|x-a|$ before choosing anything.

Solution (Hint 2). The Proof begins: “Let $\epsilon >0$, and let $\delta :=$ …”.

Solution. Idea. We want $|f(x)-f(a)|<\epsilon$. Compute: $f(x)-f(a)=(2x+3)-(2a+3)=2(x-a)$, so $|f(x)-f(a)|=2|x-a|$. This is below $\epsilon$ exactly when $|x-a|<\epsilon /2$. So $\delta =\epsilon /2$ should work, and it does not involve $x$ or $a$.

Proof. Let $\epsilon >0$, and let $\delta :=\epsilon /2$, which is positive and depends on $\epsilon$ only. Let $x$ be a real number with $|x-a|<\delta$. Then $$|f(x)-f(a)|=|2(x-a)|=2|x-a|<2\delta =\epsilon .$$ Since $x$ was arbitrary, $\delta$ works for $\epsilon$; since $\epsilon >0$ was arbitrary, this proves the claim.

The Idea reads the computation from the goal back to $|x-a|$; the Proof places $\delta$ right after $\epsilon$, before any $x$ appears, and justifies it by the final display. Because $\delta$ does not depend on $a$ either, the same proof shows that one $\delta$ serves every point: $f$ is uniformly continuous on $\mathbb{R}$, in the sense of Section 6.4.

Marking scheme. (10 points) - 2: an Idea that computes $|f(x)-f(a)|=2|x-a|$ and reads off $\delta$ from the goal. - 2: the Proof opens with $\epsilon >0$ arbitrary and introduces $\delta$ before any $x$, with $\delta >0$ checked. - 2: says what $\delta$ depends on ($\epsilon$ only, or $\epsilon$ and $a$ if the choice involves $a$). - 3: for arbitrary $x$ with $|x-a|<\delta$, the forward chain to $|f(x)-f(a)|<\epsilon$, each step justified. - 1: a closing sentence with the quantifiers in the order $\epsilon$, $\delta$, $x$. Any $\delta$ with $0<\delta \le \epsilon /2$ earns full marks. Fatal errors (0 for the step): $\delta$ depending on $x$; a Proof that runs backwards (“this holds if …”).

Solution (Hint 1). Which objects does the text use without introducing them, and what does each depend on?

Solution (Hint 2). The rewrite begins: “Apply the definition of $a_n\to L$ with $\epsilon =1$, and choose $N\in \mathbb{N}$ such that …”.

Solution. (a) (i) It writes the search: “we want some $M$” and “if we use $1$ for $\epsilon$” describe what is being looked for, not lines that follow. (ii) It uses objects without introducing them: “big $n$” hides an $N$, obtained from the hypothesis at $\epsilon =1$ by $\mathrm{\forall }\mathrm{E}$ and $\mathrm{\exists }\mathrm{E}$, which is never named; “the biggest” does not say of which numbers. (iii) It never says what $M$ is or what it depends on: $M$ is built from the finitely many terms before $N$, so it depends on $N$. (Also acceptable: the split into small and big $n$ has no stated reason; the last sentence does not say what was shown.)

(b) Apply the definition of $a_n\to L$ with $\epsilon =1$, and choose $N\in \mathbb{N}$ such that $|a_n-L|<1$ for every $n\ge N$. Let $$M:=max\{\left|a_0\right|,\left|a_1\right|,\dots ,\left|a_{N-1}\right|,\left|L\right|+1\},$$ the largest of finitely many numbers, so it exists; it depends on $N$ (when $N=0$ the list is just $\left|L\right|+1$). Let $n\in \mathbb{N}$. Either $n<N$ or $n\ge N$, since every natural number is one or the other. If $n<N$, then $\left|a_n\right|$ is in the list, so $\left|a_n\right|\le M$. If $n\ge N$, then by the triangle inequality (Example (The triangle inequality by cases)) $$\left|a_n\right|=|(a_n-L)+L|\le |a_n-L|+\left|L\right|<1+\left|L\right|\le M.$$ In either case $\left|a_n\right|\le M$. Hence $(a_n)$ is bounded.

The $\mathrm{\forall }\mathrm{E}$ instance $\epsilon =1$ is named, because it is not the obvious one; the witness $M$ of the final $\mathrm{\exists }\mathrm{I}$ is defined before it is used, with its dependence; the split on $n<N$ or $n\ge N$ carries its reason (every natural number is one or the other).

Marking scheme. (10 points) - 3: (a) three genuine faults, each tied to a convention or an unwritten step (1 each). - 2: (b) applies the hypothesis at a named positive $\epsilon$ and chooses $N$ from it. - 2: defines $M$ before using it, with its dependence on $N$, bounding the early terms and $\left|L\right|+\epsilon$ (a maximum or a sum). - 2: the two cases $n<N$ and $n\ge N$, the second by the triangle inequality (cited) or an equivalent estimate from $|a_n-L|<\epsilon$, such as $L-\epsilon <a_n<L+\epsilon$ and a split on the sign of $a_n$. - 1: ends with what was shown. Fatal errors (0 for the step): $M$ chosen before $N$ or as a maximum or sum of infinitely many numbers; the early terms omitted.