8.6 Checking Proofs, and What Is Not Allowed

A reader working alone must judge proofs, including their own, and is the person least able to do it. The remedy is procedural. This section gives two questions to ask of every line and a catalogue of the errors that recur, each tied to the rule of Chapters 1–7 that it breaks, and then checks four short proofs line by line.

8.6.1. Two questions for every line

A proof is correct when every line is licensed: by Definition 1.4.2, each line is a premise (a hypothesis, a proved result or a true school fact), an assumption, or one rule applied to available lines. So checking a proof means asking two questions of every line, with the answers in two columns.

Is it true? Is the line correct whenever the hypotheses and the assumptions of the open boxes are true?
Does it follow, and by which rule? From which available lines, and by which rule?

The first column finds where to look; the second decides.

The two questions are different. A line can be true and not follow: a correct fact the proof has not earned. This is the dangerous case, because nothing about the line looks wrong.

	It follows	It does not follow
It is true	the normal case: “ $n = 2k$ , so $n^2 = 2(2k^2)$ ”, in a proof that $n^2$ is even when $n$ is	the dangerous case: Proof B’s last line, “if $n^2$ is even, then $n$ is even”, true and not earned
It is false	the fault is higher up: from the false line “every real $x$ has $x \ge 1$ or $x \le 0$ ”, $\mathrm{\forall E}$ at $\tfrac12$ gives “ $\tfrac12 \ge 1$ or $\tfrac12 \le 0$ ”, which follows and is false	“ $x < 1$ , so $x^2 < 1$ ”: false at $x = -2$

“False” means false in some situation where the hypotheses and the open assumptions are true. When a line follows and is false, some line it rests on, neither a hypothesis nor an open assumption, is false there too, because the rules never lead from true lines to a false one (Theorem 4.7.2); follow it back until the second column fails.

The two columns, as a procedure for one line:

$Diagram. Labels: the next line of the proof, first column: is it true wherever\the hypotheses and the open\assumptions are true?, second column: which rule, or\which chain of rules and silent\steps , from which available lines?, no such chain: the proof fails\here ; name its entry, (N1)--(N14), the line is licensed at its level;\go on to the next one$

A “no” in the first column marks a line to look at first; only the second column decides. The silent steps are those of Definition 8.3.2.

Second readingTwo notes on the two columns

The same holds for derivations with quantifiers and equality, by the soundness statement for predicate logic in Section 7.2 (“From counter-models to non-derivability”).

(Proof C’s “ $1$ is even” is true given its box’s assumption.)

Quick check. A proof that $n^2 \ge n$ for every integer $n$ opens with the line “ $n^2 - n = n(n - 1) \ge 0$ ”. Is the line true? Does it follow? Would the answers change if $n$ ranged over the reals?

Solution. For an integer $n$ the line is true: no integer lies strictly between $0$ and $1$ , so $n \le 0$ (both factors $\le 0$ ) or $n \ge 1$ (both $\ge 0$ ). But as written it follows from nothing: it is the goal rearranged, without the case split that makes it true. For real $n$ it is false at $n = 1/2$ , where $n(n - 1) = -1/4$ . The first column depends on the situation; the second fails in both.

8.6.2. The catalogue

Most wrong proofs fail in one of a few ways, each breaking a particular rule. The entries fall into seven families.

Family	Entries	Slogan
“For all” errors	(N1), (N2), (N3)	A “for all” needs one argument about a name that is new and arbitrary.
Naming errors	(N4), (N12)	A new choice gets a new name, and two names may name one thing.
Implication errors	(N5), (N6)	The box of $P \to Q$ opens with $P$ ; $Q$ alone gives no $P$ .
Case errors	(N7), (N8)	Every case, from a disjunction that covers everything.
Scope and citation errors	(N9), (N10)	Cite only what is proved, given, or open around you.
Negation errors	(N11)	Negate exactly: an $\mathrm{RAA}$ box opens with the negation of the goal; negate the quantifier, not the bound; $\varphi \wedge \neg\psi$ , not an implication.
Iteration and existence errors	(N13), (N14)	An “and so on” needs its step; a “the” needs its object.

Example (What is not allowed)

Each entry names the error, the rule it breaks and where that rule lives, and a failing instance whose conclusion is marked true or false: a wrong argument can reach either.

Second readingTrue conclusions behind an ‘and so on’ and a ‘the’

Both new kinds of error can reach a true conclusion. The words of (N13)’s instance, said of a non-empty set of natural numbers, reach a true conclusion, but they leave out why the process ends: a strictly decreasing list of natural numbers that starts at $a_1$ has at most $a_1 + 1$ terms, which needs an induction. “Let $m$ be the least positive integer with $m^2 > 50$ ; since $7^2 = 49$ and $8^2 = 64$ , $m = 8$ ” reaches a true conclusion too, but the existence of a least such integer is a premise the proof must state: it is (N14). The barber who shaves exactly the villagers who do not shave themselves is (N14) as well; Section 5.6 shows that no such barber can exist (Theorem 5.6.3).

An entry diagnoses a step, not the conclusion: a false instance shows the step leading from true premises to a false conclusion, and a true one that a correct conclusion does not excuse it. Some entries name errors met before: (N1) is the first error of Section 5.4’s list, and parts (b) and (c) of (N11) are warnings of Section 6.2.

The catalogue lists steps that can lead from true lines to a false one. A step can also be valid but improper. “For all reals $a$ and $b$ , $a^2 + b^2 \ge 2ab$ ; so for all reals $b$ and $a$ , $a^2 + b^2 \ge 2ab$ ”, taken as one line, never leads from truth to falsehood, but no rule of the book writes it in one line, TAUT included (Section 8.3). That is a matter of level (Definition 8.3.1), not an error: at level 0 it is $\mathrm{\forall E}$ twice and $\mathrm{\forall I}$ twice, and in prose it needs no words.

Second readingThe errors under their traditional names

Older books name some of these errors as fallacies:

Traditional name	Entry
hasty generalization	(N1)
equivocation: one name for two things	(N4)
affirming the consequent; denying the antecedent	(N6)
false dichotomy	(N8)
begging the question	(N9)
a presupposition (“the …”)	(N14)

Affirming a disjunct is a common error of Section 1.6.

Quick check. Which family, and which entry, does this belong to: “Some integer $n$ has $n^2 = n + 6$ ; fix such an $n$ . Since $n$ was arbitrary, every integer $n$ satisfies $n^2 = n + 6$ ”?

Solution. A “for all” error, (N3): a name chosen by $\mathrm{\exists E}$ is not arbitrary. The premise holds at $n = 3$ ; the conclusion fails at $n = 0$ .

Quick check. Which entry does the sentence “choose $N$ larger than every $N_\varepsilon$ , one for each $\varepsilon > 0$ ” commit, and when is the same move not an error?

Solution. (N2). Each $N_\varepsilon$ comes from $\forall \varepsilon \, \exists N$ , inside the box of its own $\varepsilon$ ; one $N$ above all of them would be uniform, as if the hypothesis were $\exists N \, \forall \varepsilon$ , and usually none exists, since the $N_\varepsilon$ can grow without bound as $\varepsilon$ shrinks. The move is legitimate when $\varepsilon$ ranges over finitely many values $\varepsilon_1, \dots, \varepsilon_k$ : then $\max\{N_{\varepsilon_1}, \dots, N_{\varepsilon_k}\}$ exists, because a finite set of natural numbers has a maximum.

Warning. A true conclusion does not make a proof correct. “I know the result is true” answers the first column for the last line and nothing else. Argument B of Section 1.1 has a true conclusion and only true sentences, and it is wrong (Proof B below).

8.6.3. Four proofs, checked

Here are four short proofs as a student might write them; two are correct and two are not.

Example (Proof A)

Claim. For a real number $x$ , if $x^2 - 3x + 2 < 0$ , then $1 < x < 2$ .

Assume $x^2 - 3x + 2 < 0$ . (2) Then $(x - 1)(x - 2) < 0$ . (3) A product of two real numbers is negative only when one factor is positive and the other negative, so either $x - 1 > 0$ and $x - 2 < 0$ , or $x - 1 < 0$ and $x - 2 > 0$ . (4) In the first case, $1 < x < 2$ . (5) In the second case, $x < 1$ and $x > 2$ , which is impossible. (6) Hence $1 < x < 2$ .

Solution.

Line	True?	Follows? By which rule?
(1)	assumption	opens the $\mathrm{{\to}I}$ box
(2)	yes: $(x - 1)(x - 2) = x^2 - 3x + 2$	$\mathrm{{=}E}$ with the algebraic identity
(3)	yes	$\mathrm{{\to}E}$ with the stated fact about signs; a disjunction of two conjunctions
(4)	yes, in this case	$\mathrm{\vee E}$ , case 1: $\mathrm{\wedge E}$ gives $x > 1$ and $x < 2$
(5)	the case is impossible	$\mathrm{\vee E}$ , case 2: $x > 2$ and $x < 1$ give $2 < 1$ , which clashes with $\neg(2 < 1)$ ( $\mathrm{\neg E}$ ); the case reaches $1 < x < 2$ by $\mathrm{\bot E}$
(6)	yes	$\mathrm{\vee E}$ on (3), (4), (5); then $\mathrm{{\to}I}$ on (1)–(6)

Verdict: correct. The disjunction of line (3) is derived from a stated fact, so the cases exhaust and (N8) does not apply. Line (5) is the one to look at twice: “which is impossible” is $\mathrm{\bot E}$ , which lets a case that cannot occur reach the goal, so that $\mathrm{\vee E}$ can combine the cases. By Definition 8.3.2 it could be silent, since the clash is stated.

Example (Proof B)

Claim. For an integer $n$ , if $n^2$ is even, then $n$ is even.

Suppose $n$ is even. (2) Then $n = 2k$ for some integer $k$ . (3) So $n^2 = 4k^2 = 2(2k^2)$ . (4) Hence $n^2$ is even. (5) Therefore, if $n^2$ is even, then $n$ is even.

Solution.

Line	True?	Follows? By which rule?
(1)	assumption	opens a box, with “ $n$ is even”
(2)	yes, given (1)	the definition of “even”, then $\mathrm{\exists E}$ with a fresh $k$
(3)	yes	algebra
(4)	yes, given (1)	$\mathrm{\exists I}$ with the witness $2k^2$ : the definition of “even”
(5)	the statement is true, but …	does not follow: $\mathrm{{\to}I}$ on the box (1)–(4) gives “if $n$ is even, then $n^2$ is even”, not (5)

Verdict: wrong; line (5) fails; entry (N5). Every line is true, and lines (1)–(4) prove the converse. $\mathrm{{\to}I}$ turns a box from $P$ to $Q$ into $P \to Q$ , with the box’s assumption on the left; writing the claim instead is the step from $P \to Q$ to $Q \to P$ . That step has a refuting row, $P$ false and $Q$ true, so no derivation makes it (Corollary 4.7.3); and it fails in practice: “if $x > 1$ , then $x^2 > 1$ ” is true, its converse false at $x = -2$ . This is Argument B of Section 1.1, diagnosed in Section 1.4. The claim is true: Theorem 2.1.3 proves it in a box that opens with “ $n^2$ is even”.

Example (Proof C)

Claim. For an integer $n$ , the number $n^2 - 2$ is not divisible by $4$ .

Suppose $n^2 - 2$ is divisible by $4$ , say $n^2 - 2 = 4k$ with $k$ an integer. (2) Then $n^2 = 4k + 2 = 2(2k + 1)$ , so $n^2$ is even. (3) By Theorem 2.1.3, $n$ is even, say $n = 2m$ with $m$ an integer. (4) Then $n^2 = 4m^2$ , so $4m^2 = 4k + 2$ , and hence $1 = 2(m^2 - k)$ . (5) So $1$ is even. (6) But $1$ is odd, and no integer is both even and odd; this is a contradiction. (7) Hence $n^2 - 2$ is not divisible by $4$ .

Solution.

Line	True?	Follows? By which rule?
(1)	assumption	opens the $\mathrm{\neg I}$ box, with “ $4$ divides $n^2 - 2$ ”; then $\mathrm{\exists E}$ with a fresh $k$
(2)	yes, given (1)	algebra, then $\mathrm{\exists I}$ with witness $2k + 1$
(3)	yes, given (2)	$\mathrm{{\to}E}$ with Theorem 2.1.3 and (2); then $\mathrm{\exists E}$ with a fresh $m$
(4)	yes, given (1) and (3)	algebra: subtract $4k$ , divide by $2$
(5)	yes, given (4)	$\mathrm{\exists I}$ with witness $m^2 - k$ , an integer
(6)	yes	$\mathrm{\wedge I}$ of (5) and “ $1$ is odd”, then $\mathrm{\neg E}$ against “no integer is both even and odd”
(7)	yes	$\mathrm{\neg I}$ on the box (1)–(6)

Verdict: correct. The goal is a negation, and the $\mathrm{\neg I}$ box opens with the positive statement: a proof “by contradiction” of face (i) of Section 8.1, with no $\mathrm{RAA}$ . The witness names $k$ and $m$ differ, as (N4) requires.

Example (Proof D)

Claim. For a real number $x$ : if $x > 1$ , then $x^2 > x$ ; and $x^2 + 1 > x$ .

Suppose $x > 1$ . (2) Multiplying both sides by $x$ , which is positive, gives $x^2 > x$ . (3) Hence if $x > 1$ , then $x^2 > x$ . (4) For the second part, $x^2 + 1 > x^2$ , and $x^2 > x$ by (2), so $x^2 + 1 > x$ .

Solution.

Line	True?	Follows? By which rule?
(1)	assumption	opens the $\mathrm{{\to}I}$ box for the first conjunct
(2)	yes, given (1)	$\mathrm{{\to}E}$ with “multiplying by a positive number keeps $>$ ”; $x > 0$ since $x > 1 > 0$
(3)	yes	$\mathrm{{\to}I}$ on the box (1)–(2)
(4)	“ $x^2 > x$ ” is false for $x = 1/2$	does not follow: it cites (2), which lies inside the box closed at (3)

Verdict: wrong; line (4) fails; entry (N10). The claim is a conjunction, so the skeleton is $\mathrm{\wedge I}$ with two separate proofs. The second cites line (2), derived inside the box that assumed $x > 1$ and closed at line (3), so line (2) is not available. The first column confirms it: at $x = 1/2$ , $x^2 = 1/4 < 1/2 = x$ , a counterexample to the illegal step, though not to the claim.

The claim is true. For every real $x$ , $x^2 - x + 1 = \Bigl( x - \frac12 \Bigr)^2 + \frac34 > 0,$ since a square is non-negative; so $x^2 + 1 > x$ , with nothing from the closed box.

In Proofs B and D every sentence sounds right, and in Proof B every sentence is true. The errors are in the connections, which the rules govern: “which rule, from which available lines?” catches both.

Remark (Looking ahead). From Sets, Relations, and Cardinality, Chapter 1 on, a warning about one of these errors cites its entry by number, as in “(N3) of the catalogue”.

8.6.4. Exercises

A. Check your understanding

Exercise (A1)

Each line below comes from a proof. Name the catalogue entry of Example (What is not allowed) that it commits, and the rule it breaks.

(a) “We checked $3^n > n^2$ for $n = 0, 1, 2, 3, 4$ , so it holds for every $n \in \mathbb{N}$ .”
(b) “By hypothesis some $x \in A$ has $f(x) = 0$ ; fix such an $x$ . Since $x$ was arbitrary, $f(x) = 0$ for every $x \in A$ .”
(c) “To prove that $f(x_1) = f(x_2)$ implies $x_1 = x_2$ , suppose $x_1 = x_2$ ; then $f(x_1) = f(x_2)$ .”
(d) “To prove $x > 0$ , suppose, for a contradiction, that $x < 0$ .”
(e) “If $n$ is divisible by $6$ , then $n$ is even. Since $n$ is even, $n$ is divisible by $6$ .”
(f) “Every real $x$ satisfies $x > 0$ or $x < 0$ ; we consider the two cases.”

Solution. (a) (N1): $\mathrm{\forall I}$ needs one proof about a fresh name, not five instances.

(b) (N3): $x$ was chosen by $\mathrm{\exists E}$ and appears in the open assumption $f(x) = 0$ , so $\mathrm{\forall I}$ on it breaks the side condition. For $A = \{0, 1\}$ and $f(x) = x$ the conclusion fails.

(c) (N5): the $\mathrm{{\to}I}$ box opens with the conclusion, so it proves the converse, which every function satisfies.

(d) (N11) (part (a)): the negation of $x > 0$ is $x \le 0$ , not $x < 0$ , so $\mathrm{RAA}$ cannot close this box with $x > 0$ ; the case $x = 0$ is never examined, and $\mathrm{\neg I}$ on the box gives only $x \ge 0$ .

(e) (N6), affirming the consequent. No rule licenses it, so it breaks Definition 1.4.2: $P \to Q$ with $Q$ gives no $P$ . Here $n = 4$ is even and not divisible by $6$ .

(f) (N8): the disjunction is not derived, and it is false at $x = 0$ , so $\mathrm{\vee E}$ has no valid first input.

Exercise (A2: Drill)

Name the entry of Example (What is not allowed) that each line commits, if any, and say whether its conclusion is true.

(a) “We checked that $n^2 + n$ is even for $n = 1, \dots, 6$ , so it is even for every $n$ .”
(b) “Let $\varepsilon > 0$ and choose $N$ with $\left| a_n - L \right| < \varepsilon$ for $n \ge N$ ; since $\varepsilon$ was arbitrary, this one $N$ works for every $\varepsilon$ .”
(c) “ $x$ and $y$ are odd, so $x = 2k + 1$ and $y = 2k + 1$ .”
(d) “If $n$ is divisible by $4$ , then $n$ is even; $n$ is not divisible by $4$ , so $n$ is not even.”
(e) “ $n^3 - n$ is even for every integer $n$ : if $n$ is even, say $n = 2k$ , then $n^3 - n = 2(4k^3 - k)$ ; so $n^3 - n$ is even.”
(f) “Suppose $x > 0$ ; then $x^2 > 0$ . Hence if $x > 0$ , then $x^2 > 0$ . Since $x^2 > 0$ , …”
(g) “The negation of ‘for every $\varepsilon > 0$ , $\left| x \right| < \varepsilon$ ’ is ‘for some $\varepsilon \le 0$ , $\left| x \right| \ge \varepsilon$ ’.”
(h) “To prove ‘if $n^2$ is odd, then $n$ is odd’: suppose $n$ is odd; then $n^2$ is odd.”
(i) “Let $x$ and $y$ be solutions of $x^2 = 9$ . Then $x^2 - y^2 = 0$ , so $(x - y)(x + y) = 0$ , and since $x \ne y$ , $x + y = 0$ .”
(j) “ $a_1 = 2$ and $a_{n+1} = a_n^2 - 2$ . Then $a_2 = 2$ , $a_3 = 2$ , and so on, so $a_n = 2$ for every $n \ge 1$ .”
(k) “Let $n$ be the positive integer with $n^2 = 2$ . Then $1 < n^2 < 4$ , so $1 < n < 2$ .”
(l) “From ‘ $x > 0$ ’ and ‘( $x > 0$ implies $y > 0$ ) and ( $y > 0$ implies $z > 0$ )’, conclude ‘ $z > 0$ ’ in one line.”

Solution.

(a) (N1); true ( $n^2 + n = n(n + 1)$ ), still not a proof.
(b) (N2); in general false.
(c) (N4); false ( $x = 1$ , $y = 3$ ).
(d) (N6), denying the antecedent; false ( $n = 2$ ).
(e) (N7), a missing case: the odd case is never written. The conclusion is true ( $n^3 - n = (n - 1)n(n + 1)$ , and of $n - 1$ , $n$ one is even), still not a proof.
(f) (N10); “ $x^2 > 0$ ” is false at $x = 0$ .
(g) (N11), part (b); false. The stated “negation” holds for every $x$ (take $\varepsilon = -1$ ), also at $x = 0$ , where the original holds too, so it is not the negation; the negation is “for some $\varepsilon > 0$ , $\left| x \right| \ge \varepsilon$ ”.
(h) (N5); the claim is true, but the proof proves the converse.
(i) (N12) (the “since” also cites the unavailable line $x \ne y$ , an (N9) step); false: $x = y = 3$ gives $x + y = 6$ .
(j) (N13); true. The step “if $a_n = 2$ , then $a_{n+1} = 4 - 2 = 2$ ” is one line, and the proof must write it, as the step of an induction.
(k) (N14). The presupposed premise, that such an integer exists, is false, and so is the conclusion that an integer lies strictly between $1$ and $2$ .
(l) No entry. No primitive rule writes the step in one line: at level 0 it is $\mathrm{\wedge E}$ twice and $\mathrm{{\to}E}$ twice. From Section 6.3 on, a single TAUT line on the propositional skeleton (Proposition 6.3.1), citing both premises, also writes it (Section 8.3). Either way it is a matter of level, not an error.

B. Practice

Exercise (B1: Two proofs in two columns)

Check each proof in two columns. For a wrong proof, name the first line that fails and its catalogue entry, and say whether the claim is true.

(i) Claim. For integers $m$ and $n$ , if $m$ and $n$ are odd, then $m + n$ is even. (1) Assume $m$ and $n$ are odd. (2) Choose integers $k$ and $l$ with $m = 2k + 1$ and $n = 2l + 1$ . (3) Then $m + n = 2k + 2l + 2 = 2(k + l + 1)$ . (4) Since $k + l + 1$ is an integer, $m + n$ is even.
(ii) Claim. For a real number $x$ , if $x^2 < 1$ , then $x < 1$ . (1) Assume $x^2 < 1$ . (2) Suppose, for a contradiction, that $x > 1$ . (3) Then $x > 0$ , so $x^2 = x \cdot x > x > 1$ . (4) This contradicts $x^2 < 1$ . (5) Hence $x < 1$ .

Solution. (i)

Line	True?	Follows? By which rule?
(1)	assumption	opens the $\mathrm{{\to}I}$ box
(2)	yes, given (1)	$\mathrm{\wedge E}$ , the definition of “odd”, and two $\mathrm{\exists E}$ ’s with the different fresh names $k$ and $l$
(3)	yes	algebra, $\mathrm{{=}E}$ in a chain
(4)	yes	$\mathrm{\exists I}$ with the witness $k + l + 1$ ; then the boxes close, and $\mathrm{{\to}I}$

Verdict: correct. In (2) the second witness has a new name, as (N4) of Example (What is not allowed) requires.

(ii)

Line	True?	Follows? By which rule?
(1)	assumption	opens the $\mathrm{{\to}I}$ box
(2)	assumption	opens a box with “ $x > 1$ ”, announced as $\mathrm{RAA}$
(3)	yes, given (2)	$\mathrm{{\to}E}$ with order facts
(4)	yes	(3) gives $\neg(x^2 < 1)$ by order facts; $\mathrm{\neg E}$ on (1) and that line
(5)	true, given (1), but …	does not follow: the box assumed $x > 1$ , which is not the negation of $x < 1$ ; $\mathrm{\neg I}$ on it gives only $\neg(x > 1)$ , that is, $x \le 1$

Verdict: wrong; line (5) fails, because the box of line (2) opened with the wrong statement; entry (N11). The negation of $x < 1$ is $x \ge 1$ , and the case $x = 1$ is never examined: $x = 1$ has $\neg(x > 1)$ and not $x < 1$ , a counterexample to the step. The claim is true. Repair: suppose, for a contradiction, that $x \ge 1$ ; then $x^2 = x \cdot x \ge x \ge 1$ , which contradicts $x^2 < 1$ ; hence $x < 1$ .

Exercise (B2: Find the error)

Find the error in the following proof, name its catalogue entry, and decide whether the claim is true.

Claim. For all real numbers $x$ and $y$ , $\left| x \right| + \left| y \right| = \left| x + y \right|$ .

Let $x$ and $y$ be real numbers. (2) Either $x$ and $y$ are both $\ge 0$ , or they are both $< 0$ . (3) If both are $\ge 0$ , then $x + y \ge 0$ , so $\left| x \right| + \left| y \right| = x + y = \left| x + y \right|$ . (4) If both are $< 0$ , then $x + y < 0$ , so $\left| x \right| + \left| y \right| = -x - y = -(x + y) = \left| x + y \right|$ . (5) In either case $\left| x \right| + \left| y \right| = \left| x + y \right|$ .

Solution. Line (2) fails. Its disjunction is not derived, and it is false when $x$ and $y$ have opposite signs, so line (5) combines cases that do not exhaust: entry (N8) of Example (What is not allowed). Lines (3) and (4) are correct in their cases.

Exercise (B3: Correct, or which entry?)

Each proof below is correct, or commits one of (N12), (N13), (N14); you are not told how many of each. For a correct proof, name its most delicate step. For a wrong one, name the entry, say whether the claim is true, and give a counterexample to the claim or a repair of the proof.

(i) Claim: for all integers $m$ , $n$ , if $m$ and $n$ are odd, then $mn$ is odd. Proof: write $m = 2k + 1$ and $n = 2l + 1$ with integers $k$ , $l$ ; then $mn = 4kl + 2k + 2l + 1 = 2(2kl + k + l) + 1$ .
(ii) Claim: for all real $a$ , $b$ , if $a^2 = b^2$ , then $a = b$ or $a = -b$ . Proof: $(a - b)(a + b) = a^2 - b^2 = 0$ , and a product of real numbers is $0$ only if a factor is.
(iii) Claim: for all integers $m$ , $n$ , $m^2 + n^2 \ge 1$ . Proof: two different integers are not both $0$ , so one of $m^2$ , $n^2$ is at least $1$ .
(iv) Claim: every integer $n \ge 2$ is a product of primes. Proof: if $n$ is prime, it is a product of one prime. If not, $n = ab$ with $1 < a, b < n$ ; split $a$ and $b$ in the same way, and so on, until only primes remain.
(v) Claim: $1$ is a solution of $x^2 + x + 1 = 0$ . Proof: let $x$ be the real solution. Then $x^3 - 1 = (x - 1)(x^2 + x + 1) = 0$ , so $x^3 = 1$ , and since $x$ is real, $x = 1$ .

Solution. (i) Correct. The delicate step is the second $\mathrm{\exists E}$ , which uses a second name $l$ . The case $m = n$ is covered, since nothing stops $k = l$ : the names are distinct, the objects need not be.

(ii) Correct. The delicate step is the product fact. It gives “ $a - b = 0$ or $a + b = 0$ ” ( $\mathrm{{\to}E}$ , citing it), which is the claim, and no distinctness is assumed.

(iii) (N12); the claim is false: $m = n = 0$ gives $0$ . The proof took $m$ and $n$ to be different integers.

(iv) (N13); the claim is true. The “and so on” hides why the splitting ends: each factor is at least $2$ and smaller than the number split. Repair by strong induction (Theorem 4.2.2): if every $k$ with $2 \le k < n$ is a product of primes, so is $n$ , being prime or $ab$ with $a$ , $b$ in that range.

(v) (N14); the claim is false: $1 + 1 + 1 = 3 \ne 0$ . The presupposed premise “ $x^2 + x + 1 = 0$ has a real solution” is false, since $x^2 + x + 1 = (x + \tfrac12)^2 + \tfrac34 > 0$ .

Look-alikes: (i) and (iii) both use two letters; only (iii) assumes the letters differ.

Marking scheme. (10 points: 2 per part) - 1: the verdict. - 1: for a correct proof, the delicate step named; for a wrong one, the entry with a counterexample (iii, v) or a repair (iv). Fatal errors (0 for that part): calling (i) an instance of (N12) because $k$ and $l$ might be equal; calling (iv) correct.

C. Going deeper

Exercise (C1: The second half)

Let $f \colon \mathbb{R} \to \mathbb{R}$ be continuous at $a$ , as the quantifier pattern of Section 6.1: for every $\varepsilon > 0$ there is $\delta > 0$ such that $\left| f(x) - f(a) \right| < \varepsilon$ for every real $x$ with $\left| x - a \right| < \delta$ . Suppose $f(a) > 0$ . Here is a level-1 skeleton for the statement “there is $\delta > 0$ such that $f(x) > 0$ for every $x$ with $\left| x - a \right| < \delta$ ”:

\forall \varepsilon > 0 \; \exists \delta > 0 \; \forall x \; (\left| x - a \right| < \delta \to \left| f(x) - f(a) \right| < \varepsilon)

f(a) > 0

f(a)/2 > 0

arith 2

\exists \delta > 0 \; \forall x \; (\left| x - a \right| < \delta \to \left| f(x) - f(a) \right| < f(a)/2)

\mathrm{{\forall}E}

1, 3

\delta_0

\delta_0 > 0

asm, for

\mathrm{{\exists}E}

\forall x \; (\left| x - a \right| < \delta_0 \to \left| f(x) - f(a) \right| < f(a)/2)

asm, for

\mathrm{{\exists}E}

x_0

\left| x_0 - a \right| < \delta_0

asm, for

\mathrm{{{\to}}I}

\left| x_0 - a \right| < \delta_0 \to \left| f(x_0) - f(a) \right| < f(a)/2

\mathrm{{\forall}E}

\left| f(x_0) - f(a) \right| < f(a)/2

\mathrm{{{\to}}E}

8, 7

f(x_0) > 0

arith 2, 9

\left| x_0 - a \right| < \delta_0 \to f(x_0) > 0

\mathrm{{{\to}}I}

7–10

\forall x \; (\left| x - a \right| < \delta_0 \to f(x) > 0)

\mathrm{{\forall}I}

7–11

\exists \delta > 0 \; \forall x \; (\left| x - a \right| < \delta \to f(x) > 0)

\mathrm{{\exists}I}

5, 12

\exists \delta > 0 \; \forall x \; (\left| x - a \right| < \delta \to f(x) > 0)

\mathrm{{\exists}E}

4, 5–13

Its level-3 prose begins:

Since $f(a) > 0$ , the number $f(a)/2$ is positive. By the continuity of $f$ at $a$ , applied with $\varepsilon = f(a)/2$ , choose $\delta > 0$ such that $\left| f(x) - f(a) \right| < f(a)/2$ for every real $x$ with $\left| x - a \right| < \delta$ .

The rest is blank. Name the move, then complete it. Say which skeleton lines your sentences carry, and what $\delta$ depends on.

Solution (Hint 1). What is left is the box of $x_0$ and the witness.

Solution (Hint 2). “Let $x$ be a real number with $\left| x - a \right| < \delta$ . Then …”

Solution. The move: skeleton first: the goal fixes the $\mathrm{\exists I}$ of line 13 and the box of $x_0$ . Filling it: $\mathrm{\forall E}$ at the non-obvious instance $\varepsilon = f(a)/2$ (line 4), $\mathrm{\exists E}$ on its $\delta$ (line 5), and that $\delta$ as the witness.

Completion.

Let $x$ be a real number with $\left| x - a \right| < \delta$ . Then $\left| f(x) - f(a) \right| < f(a)/2$ , so, as $-\left| u \right| \le u$ , $f(x) - f(a) > -f(a)/2$ , that is, $f(x) > f(a)/2 > 0$ . So this $\delta$ , which depends only on $a$ , is as required.

“Let $x$ … with $\left| x - a \right| < \delta$ ” opens the two boxes at line 7; “then $\left| f(x) - f(a) \right| < f(a)/2$ ” is lines 8–9, the $\mathrm{\forall E}$ at the obvious term $x$ silent; “so … $f(x) > f(a)/2 > 0$ ” is line 10, which uses line 2. Lines 11 and 12 are silent closings, and the last sentence is lines 13–14, with the $\delta$ already chosen as witness. It depends on $a$ (through $f(a)$ and the continuity at $a$ ) and on no $x$ : the box of $\delta_0$ encloses the box of $x_0$ .

Marking scheme. (10 points) - 2: names the move (skeleton first; a hypothesis applied at a chosen $\varepsilon$ , then its $\delta$ reused as the witness), or the rules $\mathrm{\forall E}$ , $\mathrm{\exists E}$ , $\mathrm{\exists I}$ . - 3: for an arbitrary $x$ with $\left| x - a \right| < \delta$ , derives $f(x) > f(a)/2$ , with the step from $\left| u \right| < r$ to $u > -r$ justified. - 2: concludes $f(x) > 0$ using $f(a) > 0$ , and states the conclusion with $\delta$ before $x$ . - 2: matches the sentences to the skeleton’s lines. - 1: says $\delta$ depends on $a$ and not on $x$ . Second route: refuting $f(x) \le 0$ by $\left| f(x) - f(a) \right| \ge f(a) - f(x) \ge f(a) > f(a)/2$ earns the second line and the $f(x) > 0$ part of the third. Fatal errors (0 for the step): choosing $\delta$ after $x$ ; applying continuity at an $\varepsilon$ not shown to be positive.

Exercise (C2: A true conclusion)

Here is a proof that $\sqrt 2 + \sqrt 3$ is irrational, a true conclusion. Find the line that fails and its catalogue entry, give a counterexample to the illegal step, and write a correct proof.

Suppose $\sqrt 2 + \sqrt 3 = r$ for some rational number $r$ . (2) Squaring, $r^2 = 2 + 2\sqrt 6 + 3 = 5 + 2\sqrt 6$ . (3) Hence $\sqrt 6 = (r^2 - 5)/2$ , which is rational, since $r$ is. (4) But $\sqrt 6 = \sqrt 2 \cdot \sqrt 3$ is irrational, being a product of two irrational numbers. (5) This contradiction shows that $\sqrt 2 + \sqrt 3$ is irrational.

Solution (Hint 1). Run the second column on every line.

Solution (Hint 2). For a correct proof, isolate $\sqrt 3 = r - \sqrt 2$ before squaring.

Solution. The failing line is (4). Its first half is true, $\sqrt 6 = \sqrt 2 \cdot \sqrt 3$ , but its reason is not available. “A product of two irrational numbers is irrational” is neither proved nor a school fact: it is false, since $\sqrt 2$ is irrational (Theorem 2.2.1), and $\sqrt 2 \cdot \sqrt 2 = 2$ is rational. So the line cites nothing: entry (N9) of Example (What is not allowed). The product $\sqrt 2 \cdot \sqrt 2 = 2$ is a counterexample to the illegal step; there is none to the conclusion, which is true. Lines (1)–(3) and (5), and the $\mathrm{\neg I}$ skeleton, are correct.

A correct proof. Suppose $\sqrt 2 + \sqrt 3 = r$ with $r$ rational. Then $r > 0$ , since both square roots are positive. Isolating, $\sqrt 3 = r - \sqrt 2$ , and squaring, $3 = r^2 - 2r\sqrt 2 + 2, \qquad\text{so}\qquad \sqrt 2 = \frac{r^2 - 1}{2r},$ where dividing by $2r$ is legitimate because $r > 0$ . The right-hand side is rational, which contradicts Theorem 2.2.1. Hence $\sqrt 2 + \sqrt 3$ is irrational.

Marking scheme. (10 points) - 3: names line (4) as the failing line, and the illegal step as the unproved general “fact”, entry (N9). - 2: a counterexample to that step ( $\sqrt 2 \cdot \sqrt 2 = 2$ , or another product of two irrationals that is rational). - 1: says the conclusion is true, so no counterexample to it exists. - 4: a correct proof: the $\mathrm{\neg I}$ box on “ $r$ rational”, the algebra, the division justified by $r \ne 0$ , and the clash with Theorem 2.2.1 (or with $\sqrt 3$ or $\sqrt 6$ , its irrationality proved). Fatal errors (0 for the step): “correcting” line (4) by another unproved fact; dividing by $r$ without $r \ne 0$ .

Exercise (C3: Exit check: four student proofs)

Judge each proof. If it is wrong, give the line that fails, its entry in Example (What is not allowed), and a counterexample to the illegal step. If it is correct, name the rule of its most delicate step and check that step.

(1) Claim. For every integer $n$ , if $n$ is a multiple of $4$ or a multiple of $6$ , then $n$ is even. (1) Let $n$ be an integer that is a multiple of $4$ or of $6$ . (2) Case 1: $n$ is a multiple of $4$ . Choose an integer $k$ with $n = 4k$ ; then $n = 2(2k)$ , so $n$ is even. (3) Case 2: $n$ is a multiple of $6$ . Choose an integer $k$ with $n = 6k$ ; then $n = 2(3k)$ , so $n$ is even. (4) In either case, $n$ is even.
(2) Claim. For integers $m$ and $n$ , if $m$ and $n$ are even, then $mn$ is divisible by $4$ . (1) Assume $m$ and $n$ are even. (2) Then $m = 2k$ and $n = 2k$ for an integer $k$ . (3) So $mn = 4k^2$ , which is divisible by $4$ .
(3) Claim. For every real $x$ , $\left| x - 1 \right| \le \left| x \right| + 1$ . (1) Either $x \ge 1$ or $x \le 0$ . (2) If $x \ge 1$ , then $\left| x - 1 \right| = x - 1 \le x + 1 = \left| x \right| + 1$ . (3) If $x \le 0$ , then $\left| x - 1 \right| = 1 - x = 1 + \left| x \right|$ . (4) In either case, $\left| x - 1 \right| \le \left| x \right| + 1$ .
(4) Claim. For every real $x$ , if $x^2 = 2x$ , then $x = 2$ . (1) Assume $x^2 = 2x$ . (2) Canceling $x$ from both sides, $x = 2$ . (3) Hence if $x^2 = 2x$ , then $x = 2$ .

Solution (Hint 1). Run the two-column check on every line, and keep the two questions apart: a true claim can have a wrong proof.

Solution (Hint 2). In (1), ask which boxes are open when the second $k$ is chosen. In (3), ask what $\mathrm{\vee E}$ needs from line (1).

Solution. (1) Correct. The skeleton is $\mathrm{\forall I}$ and $\mathrm{{\to}I}$ , then $\mathrm{\vee E}$ on the hypothesis itself, so the cases exhaust. The delicate step is the second “choose an integer $k$ ”, an $\mathrm{\exists E}$ reusing a name. It is legal: the first box of $k$ lies inside Case 1, which closed before Case 2 opened, so $k$ appears in no open assumption, not in the existential and not in the conclusion. Sibling boxes may share a name (Section 5.6); (N4) forbids only a name still in use.

(2) Wrong; line (2) fails; entry (N4) of Example (What is not allowed). The second witness is named $k$ while the box of $m = 2k$ is open. Counterexample to the step: $m = 2$ , $n = 4$ ; no integer $k$ has $2 = 2k$ and $4 = 2k$ . The conclusion is true: with $m = 2k$ and $n = 2l$ , $mn = 4kl$ .

(3) Wrong; line (1) fails; entry (N8). “Either $x \ge 1$ or $x \le 0$ ” is not derived, and is false at $x = 1/2$ , a counterexample to the step. The conclusion is true; the missing case repairs the proof: if $0 < x < 1$ , then $\left| x - 1 \right| = 1 - x < 1 < \left| x \right| + 1$ .

(4) Wrong; line (2) fails; entry (N9); the claim is false. Canceling uses the “fact” “if $ax = bx$ , then $a = b$ ”, which is neither proved nor a school fact, and is false: $a = 1$ , $b = 2$ , $x = 0$ . It needs $x \ne 0$ , which no line provides. The claim fails at $x = 0$ ; what is true is “ $x = 0$ or $x = 2$ ”, from $x(x - 2) = 0$ .

Marking scheme. (10 points: 2.5 per proof) - For each of (2), (3), (4): the verdict “wrong” (1); the failing line and its entry, (N4), (N8), (N9) (1); a counterexample to the illegal step (0.5). - For (1): the verdict “correct” (1); the delicate step named as an $\mathrm{\exists E}$ reusing a name in a sibling box (or as the $\mathrm{\vee E}$ on the hypothesis) (1); that step checked against the side condition (0.5). For (4), “ $\mathrm{{\to}E}$ without its antecedent $x \ne 0$ ” is also accepted. Fatal errors (0 for that proof): calling proof (1) wrong as an instance of (N4) because the name $k$ recurs; judging (2) or (3) correct because its conclusion is true.

R. Review

Exercise (R1: A dialogue)

Two students discuss a claim.

Ana: For every integer $n$ , $n^2 + n$ is even.

Ben: Why?

Ana: Take $n = 3$ : $9 + 3 = 12$ . Take $n = 4$ : $16 + 4 = 20$ . It always works.

Ben: That is two numbers.

Ana: All right. $n^2 + n = n(n + 1)$ . If $n$ is even, the product has an even factor. If $n$ is odd, $n + 1$ is even, so again it has an even factor. Either way $n^2 + n$ is even.

Ben: You only did positive numbers.

Ana: I never used that $n$ is positive.

(a) Which entry of Example (What is not allowed) does Ana’s first argument commit?
(b) Write her second argument as a level-3 proof, and name the rule each sentence carries.
(c) Is Ben’s last objection right?
(d) On which fact does the case split rest, and where was it stated?

Solution. (a) (N1) of Example (What is not allowed): two instances, then “always”.

(b) “Let $n$ be an integer [ $\mathrm{\forall I}$ ]. Then $n^2 + n = n(n + 1)$ [algebra]. By (E1), $n$ is even or odd [ $\mathrm{\vee E}$ , with the reason the cases exhaust]. If $n$ is even, say $n = 2k$ [ $\mathrm{\exists E}$ ], then $n(n + 1) = 2\bigl(k(n + 1)\bigr)$ is even [ $\mathrm{\exists I}$ , witness $k(n + 1)$ ]. If $n$ is odd, say $n = 2k + 1$ , then $n + 1 = 2(k + 1)$ , and $n(n + 1) = 2\bigl(n(k + 1)\bigr)$ is even [ $\mathrm{\exists E}$ , $\mathrm{\exists I}$ ]. In either case $n^2 + n$ is even [ $\mathrm{\vee E}$ , closing; silent at level 3].”

(c) No. The box of $n$ assumed only that $n$ is an integer, and no line used more, so $\mathrm{\forall I}$ (Definition 5.4.1, Section 5.4) gives the claim for every integer: $n$ is in no premise, and the conclusion is about the bound variable. A proof that used $n > 0$ would have had to assume it in the box.

(d) (E1), “every integer is even or odd”, stated in Section 2.1 as a school fact, before Theorem 2.1.3.