8.1 The Connective Rules in Prose

Chapters 1–7 built a calculus in which every step of a proof is one rule applied to lines that are available. Mathematicians do not write Fitch boxes; yet every proof they write is a derivation underneath, written in sentences. This section and the next compile the dictionary between the two: for each rule, the phrases that carry it, a sentence in which it does its work, and whether a writer may leave it unsaid. This section covers the connectives and the classical rules; Section 8.2 the quantifiers, equality and induction.

8.1.1. The rule card

Here is every primitive rule of the book, with the classical and derived rules most used in prose, on one card: its shape, the words that carry it in a written proof, and whether plain prose may leave it out. The last column is explained in the next subsection; Section 8.2 gives the quantifier rows their examples.

Rule	Shape	You write	Silent in plain prose?
$\mathrm{\wedge I}$	$\varphi$ , $\psi$ $\Longrightarrow$ $\varphi \wedge \psi$	“…, and …”; “both hold”	when both parts are displayed
$\mathrm{\wedge E}$	$\varphi \wedge \psi$ $\Longrightarrow$ $\varphi$ (or $\psi$ )	“in particular”	yes
$\mathrm{{\to}I}$	box $\varphi$ … $\psi$ $\Longrightarrow$ $\varphi \to \psi$	“Suppose $P$ . … So $Q$ .”	the opening never; the closing yes
$\mathrm{{\to}E}$	$\varphi \to \psi$ , $\varphi$ $\Longrightarrow$ $\psi$	“since …”; “by (the lemma), …”	yes when the implication is a line of the proof itself; never when it is a hypothesis or a cited result
$\mathrm{R}$	$\varphi$ (available) $\Longrightarrow$ $\varphi$ , copied	“recall that”	yes
$\mathrm{\vee I}$	$\varphi$ $\Longrightarrow$ $\varphi \vee \psi$ (or $\psi \vee \varphi$ )	“so certainly … or …”	yes
$\mathrm{\vee E}$	$\varphi \vee \psi$ , box $\varphi$ … $\chi$ , box $\psi$ … $\chi$ $\Longrightarrow$ $\chi$	“Case 1 … Case 2 … In either case”	the split and why it is exhaustive never; “in either case” yes
$\mathrm{\neg I}$	box $\varphi$ … $\bot$ $\Longrightarrow$ $\neg\varphi$	“Suppose $P$ . … a contradiction. Hence not $P$ .”	never
$\mathrm{\neg E}$	$\varphi$ , $\neg\varphi$ $\Longrightarrow$ $\bot$	“this contradicts …”	never: both lines of the clash are named
$\mathrm{\bot E}$	$\bot$ $\Longrightarrow$ $\varphi$	“this case cannot occur”	yes, once the clash or the empty case is stated
$\mathrm{{\leftrightarrow}I}$	box $\varphi$ … $\psi$ , box $\psi$ … $\varphi$ $\Longrightarrow$ $\varphi \leftrightarrow \psi$	“ $(\Rightarrow)$ … $(\Leftarrow)$ …”; “conversely”	never either direction
$\mathrm{{\leftrightarrow}E}$	$\varphi \leftrightarrow \psi$ , $\varphi$ $\Longrightarrow$ $\psi$	“that is”; “by definition”	yes, for a definition
$\mathrm{RAA}$	box $\neg\varphi$ … $\bot$ $\Longrightarrow$ $\varphi$	“suppose, for a contradiction, that not $P$ ”	never
$\mathrm{\neg\neg E}$ , $\mathrm{LEM}$	$\neg\neg\varphi$ $\Longrightarrow$ $\varphi$ ; $\Longrightarrow$ $\varphi \vee \neg\varphi$	“ $P$ must hold, since …”; “either $P$ or not”	never: written out
$\mathrm{MT}$ , $\mathrm{CP}$	$\varphi \to \psi$ , $\neg\psi$ $\Longrightarrow$ $\neg\varphi$ ; $\varphi \to \psi$ $\Longrightarrow$ $\neg\psi \to \neg\varphi$	“so $P$ cannot hold”; “we prove the contrapositive”	the announcement never
$\mathrm{DS}$	$\varphi \vee \psi$ , $\neg\varphi$ $\Longrightarrow$ $\psi$	“the first case is impossible, so …”	the name yes; the fact it uses never
$\mathrm{\forall I}$	box (fresh $a$ ) … $\varphi(a)$ $\Longrightarrow$ $\forall x\, \varphi(x)$	“let $x \in A$ ”; “fix $\varepsilon > 0$ ”	the opening never; “since $x$ was arbitrary” yes
$\mathrm{\forall E}$	$\forall x\, \varphi(x)$ $\Longrightarrow$ $\varphi(t)$	“in particular, for $x = \dots$ ”	at the obvious term yes; otherwise the term is named
$\mathrm{\exists I}$	$\varphi(t)$ $\Longrightarrow$ $\exists x\, \varphi(x)$	“take $N \mathrel{:=} \dots$ ”; “… will do”	never: the witness and what it depends on
$\mathrm{\exists E}$	$\exists x\, \varphi(x)$ , box (fresh $a$ ) $\varphi(a)$ … $\chi$ $\Longrightarrow$ $\chi$	“choose $N$ such that …”	the choice with its fresh name never; the closing yes
$\mathrm{{=}I}$ , $\mathrm{{=}E}$	$\Longrightarrow$ $t = t$ ; $s = t$ , $\varphi(s)$ $\Longrightarrow$ $\varphi(t)$	“… = … = …”; “substituting”	yes, inside chains

The exact conditions are those of Definition 8.3.2 in Section 8.3; the card abbreviates them.

Quick check. Which rule does each phrase carry: (i) “say $n = 2k$ ”, after “ $n$ is even”; (ii) “in either case”; (iii) “this contradicts $x^2 \ge 0$ ”?

Solution.

(i) $\mathrm{\exists E}$ , opening the box of $k$ (“ $n$ is even” unwound to $\exists k\, (n = 2k)$ ). (ii) $\mathrm{\vee E}$ , closing. (iii) $\mathrm{\neg E}$ , with both lines of the clash named.

The purpose of a box, spoken. Since Section 1.4 every derivation in this book has printed, beside an assumption, the rule that will close its box: “asm, for $\mathrm{{\to}I}$ ”, “asm, for $\mathrm{\neg I}$ ”, and so on. Prose says the same thing with the sentence that opens the box. “Suppose $P$ ” is asm, for $\mathrm{{\to}I}$ . “Suppose $P$ ; … this is impossible”, or “if $P$ were true”, is asm, for $\mathrm{\neg I}$ . “Suppose, for a contradiction, that not $P$ ” is asm, for $\mathrm{RAA}$ . “Case 1: $P$ ” is asm, for $\mathrm{\vee E}$ . “Choose $a$ such that $P(a)$ ” is asm, for $\mathrm{\exists E}$ . “ $(\Rightarrow)$ Suppose $P$ ” is asm, for $\mathrm{{\leftrightarrow}I}$ . “Let $x \in A$ ” is asm, for $\mathrm{\forall I}$ , its bounded form. A box whose purpose the reader cannot hear is a box the writer did not open in words.

8.1.2. Which steps may go unsaid

Plain prose leaves steps out. If it left out whatever a writer found obvious, a reader could never tell an omission from a gap, so the book fixes the omissions by one principle: a step may go unsaid when a reader who knows the rules can restore it uniquely from what is written. A step that creates something (a name, a witness, a case split), assumes something, or cites something cannot be restored that way, so it is always written.

Silent steps are the ones whose result is forced by the lines around them; every choice, assumption and citation is spoken.

The last column of the card is this principle applied rule by rule.

Quick check. In “Since $0 < x < 1$ , in particular $x > 0$ ”, may the words “in particular $x > 0$ ” be left out if the next sentence uses $x > 0$ ? May “choose $k$ with $n = 2k + 1$ ” be left out?

Solution. The first, yes: $\mathrm{\wedge E}$ has two possible results, and the next sentence shows which one was used, so the step is forced. The second, no: $\mathrm{\exists E}$ creates a name, and a name cannot be restored.

8.1.3. The same proof, twice

Section 2.3 proved Theorem 2.1.3 (“if $n^2$ is even, then $n$ is even”) a second way, in Example (Even square, even number, by contraposition), with the derived rules $\mathrm{CP}$ and $\mathrm{DS}$ . Here are four sentences for it, with the box of the second sentence spelled out:

Suppose $n^2$ is even. If $n^2$ were odd, it would be both even and odd, which (E2) forbids; so $n^2$ is not odd. By (E3), read contrapositively, $n$ is not odd. Since $n$ is even or odd, by (E1), $n$ is even.

Before reading on: where in the paragraph does a box open, and where does one close?

The paragraph accounts for every line of the derivation, though some lines have no words of their own.

Lines	Words that carry them	Rule
4	“Suppose $n^2$ is even.”	$\mathrm{{\to}I}$ , the box opens
5	“If $n^2$ were odd”	$\mathrm{\neg I}$ , the box opens
6	“it would be both even and odd”	$\mathrm{\wedge I}$
7	“which (E2) forbids”	$\mathrm{\neg E}$ , citing premise 2
8	“so $n^2$ is not odd”	$\mathrm{\neg I}$ , the box closes
9	“By (E3), read contrapositively”	$\mathrm{CP}$ , citing premise 3
10	“ $n$ is not odd”	$\mathrm{{\to}E}$
11–12	“Since $n$ is even or odd, by (E1), $n$ is even.”	$\mathrm{DS}$ , citing premise 1
13	nothing	$\mathrm{{\to}I}$ , the box closes

The derivation the table refers to is the one of Section 2.3, with the facts (E1)–(E3) of Section 2.1 (every integer is even or odd; no integer is both; the square of an odd integer is odd) as its premises, written here with its atoms in words:

\text{$n$ even} \vee \text{$n$ odd}

\neg (\text{$n^2$ even} \wedge \text{$n^2$ odd})

\text{$n$ odd} \to \text{$n^2$ odd}

\text{$n^2$ even}

asm, for

\mathrm{{{\to}}I}

\text{$n^2$ odd}

asm, for

\mathrm{{\neg}I}

\text{$n^2$ even} \wedge \text{$n^2$ odd}

\mathrm{{\wedge}I}

4, 5

\bot

\mathrm{{\neg}E}

6, 2

\neg \text{$n^2$ odd}

\mathrm{{\neg}I}

5–7

\neg \text{$n^2$ odd} \to \neg \text{$n$ odd}

\mathrm{CP}

\neg \text{$n$ odd}

\mathrm{{{\to}}E}

9, 8

\text{$n$ odd} \vee \text{$n$ even}

or commutes 1

\text{$n$ even}

\mathrm{DS}

11, 10

\text{$n^2$ even} \to \text{$n$ even}

\mathrm{{{\to}}I}

4–12

Three features of the table recur through the whole dictionary. The openings of boxes always have words, which name what is assumed: “suppose”, “if … were”. Some lines have no words: line 13 closes the box of line 4, and the paragraph simply stops; line 11 only reorders the disjuncts of (E1) for the schema of Proposition 2.3.4, and prose does not see the order of a disjunction (the principle above lets the exchange be silent: the order a schema wants is forced). And a premise is never a sentence of its own: it enters through its name, “(E2)” or “by (E1)”, at the step that uses it.

Quick check. Which word of the paragraph tells the reader that line 5 is an assumption and not a claim, and what would the sentence assert if that word were replaced by “is”?

Solution. The word “were” (with “if”): “if $n^2$ were odd” supposes something in order to refute it, which is the opening of a $\mathrm{\neg I}$ box. With “is”, the sentence “ $n^2$ is odd, so it is both even and odd” would assert “ $n^2$ is odd” as a claim rather than an assumption: it would sit, unjustified, directly in the box of line 4, where it is in fact false ( $n^2$ is even there), and the proof would be wrong.

8.1.4. How to read the dictionary

Each group of rows below repeats the card’s rows for one connective, with the phrases a reader must recognize, and then works one short proof annotated phrase by phrase. A tag such as [ $\mathrm{\wedge E}$ ] after a phrase says which rule it carries; any wording that does the same job is correct.

8.1.5. Conjunction

Rule	Phrases	Silent in plain prose?
$\mathrm{\wedge I}$	“…, and …”; “we show (a) … and (b) …”; “both … hold”	often, when both conjuncts are displayed
$\mathrm{\wedge E}$	“in particular”; “so $a > 0$ ”; using one clause of a hypothesis without comment	yes

In a proof, $\mathrm{\wedge I}$ is a claim with two parts, proved one after the other and then put together; often the parts are labeled (a) and (b), and the last sentence says nothing more. $\mathrm{\wedge E}$ is the step from a chain to one of its links: “since $x \in (0, 1)$ , in particular $x > 0$ ” takes the left conjunct of $0 < x \wedge x < 1$ .

Example (Two parts, and one part)

Let $x$ be a real number with $0 < x < 1$ . Prove that $x^2 < x$ and $x^2 > 0$ . Tag the steps that carry the logic.

Solution. The hypothesis $0 < x < 1$ is the conjunction “ $0 < x$ and $x < 1$ ”; so $x > 0$ [ $\mathrm{\wedge E}$ ] and $x < 1$ [ $\mathrm{\wedge E}$ ]. (a) Multiplying $x < 1$ by the positive number $x$ gives $x^2 < x$ [algebra]. (b) As $x > 0$ , $x^2 = x \cdot x > 0$ [algebra]. So $x^2 < x$ and $x^2 > 0$ [ $\mathrm{\wedge I}$ ].

Both $\mathrm{\wedge E}$ steps could be silent (“multiplying $x < 1$ by $x > 0$ gives …”), because the next sentence shows which part of the hypothesis is used. The final $\mathrm{\wedge I}$ may be silent too, since both parts are displayed: a proof of a two-part claim usually proves (a), proves (b), and stops.

8.1.6. Implication

Rule	Phrases	Silent in plain prose?
$\mathrm{{\to}I}$	“assume …; then …; hence if … then …”; “suppose …”; “if …, then …” as the frame of a whole proof	never the assumption; the closing “hence” may be silent
$\mathrm{{\to}E}$	“since …, …”; “by (hypothesis, lemma), …”; “hence”	the citation, never
$\mathrm{R}$	“recall that”; “as noted above”	yes
$\mathrm{MT}$ , $\mathrm{CP}$	“…; so $P$ cannot hold”; “we prove the contrapositive”; “equivalently, if not $Q$ then not $P$ ”	the announcement “we prove the contrapositive”, never

In analysis, $\mathrm{{\to}I}$ is a proof that begins “Suppose $\left| x - 1 \right| < 1$ ” and ends “so $x > 0$ ”; the example below writes it out. $\mathrm{{\to}E}$ is every citation of a theorem: “since $42$ is divisible by $2$ and by $3$ , it is divisible by $6$ ” applies the theorem used in Section 1.3 to two facts in hand, and the word “since” introduces those facts. For $\mathrm{CP}$ , Section 2.3’s Example (Even square, even number, by contraposition) is the model, as the opening of this section showed. (Theorem 2.1.3 itself is proved by cases, with no contraposition.)

Example (A hypothesis assumed, a lemma cited, a contrapositive announced)

Let $x$ be a real number. (a) Prove that if $\left| x - 1 \right| < 1$ , then $x > 0$ . (b) Deduce that if $x \le 0$ , then $\left| x - 1 \right| \ge 1$ . Tag each step with its rule.

Solution. We use the school fact that, for real $u$ and $r$ , $\left| u \right| < r$ holds exactly when $-r < u < r$ .

(a) Suppose $\left| x - 1 \right| < 1$ [assumption for $\mathrm{{\to}I}$ ]. By the school fact, $-1 < x - 1 < 1$ [ $\mathrm{{\leftrightarrow}E}$ ], in particular $-1 < x - 1$ [ $\mathrm{\wedge E}$ ], so $x > 0$ [arith].

(b) Suppose $x \le 0$ [assumption for $\mathrm{{\to}I}$ ]. Recall from (a) that $\left| x - 1 \right| < 1$ implies $x > 0$ [ $\mathrm{R}$ ]. Since $x \le 0$ , that is, $x > 0$ fails, $\left| x - 1 \right| < 1$ cannot hold [ $\mathrm{MT}$ ], so $\left| x - 1 \right| \ge 1$ .

Part (a) ends at “ $x > 0$ ”: the closing line of $\mathrm{{\to}I}$ , “hence, if $\left| x - 1 \right| < 1$ , then $x > 0$ ”, is silent. The assumption could not be: without “suppose”, the sentence “ $\left| x - 1 \right| < 1$ ” would be a claim about every real $x$ , and a false one.

In (b), “recall” is $\mathrm{R}$ , and it could be dropped. “Cannot hold” is $\mathrm{MT}$ , with $P$ the statement $\left| x - 1 \right| < 1$ and $Q$ the statement $x > 0$ ; the last step reads $\neg(\left| x - 1 \right| < 1)$ as $\left| x - 1 \right| \ge 1$ , by the order fact of Section 2.1. An equivalent (b) announces the derived rule instead: “This is the contrapositive of (a)”, which is $\mathrm{CP}$ applied to (a), followed by $\mathrm{{\to}E}$ . That announcement may never be silent: a reader who sees “suppose $x \le 0$ ” and then a citation of (a) must be told that (a) is being used backwards.

8.1.7. Disjunction and cases

Rule	Phrases	Silent in plain prose?
$\mathrm{\vee I}$	“…, so certainly $P$ or $Q$ ”; “in particular $x \ne 0$ or …”	yes
$\mathrm{\vee E}$	“we consider two cases”; “Case 1 … Case 2 …”; “in either case”; “otherwise”	never the split; the “in either case” may be silent
$\mathrm{DS}$	“since $x \ne 0$ , the first case is impossible, so …”	the rule’s name, yes; the fact $x \ne 0$ it uses, never
constructive dilemma (Example (Constructive dilemma); the derived rule $\mathrm{CD}$ of Section 2.3, Exercise (B4: Dilemmas as derived rules, used later))	“if $P$ then $R$ , and if $Q$ then $S$ ; since $P$ or $Q$ , we get $R$ or $S$ ”; “in the first case …, in the second …, so $R$ or $S$ ”	never the split or the two implications; the closing “so $R$ or $S$ ” yes
“or” and “and” commute (Example (First derivations with “or”), Proposition 1.2.1)	“ $P$ or $Q$ ” read as “ $Q$ or $P$ ”, with no words of its own	yes

In analysis, $\mathrm{\vee I}$ hides inside every weakening of a strict inequality: “ $x > 0$ , so $x \ge 0$ ”. $\mathrm{\vee E}$ is the proof of the triangle inequality in Section 1.6 (Example (The triangle inequality by cases)), which splits on the sign of $x + y$ and reaches $\left| x + y \right| \le \left| x \right| + \left| y \right|$ in both cases. $\mathrm{DS}$ is the step “ $x^2 = x$ , so $x = 0$ or $x = 1$ ; since $x \ne 0$ , $x = 1$ ”.

Example (Two cases, a weakening, a refuted disjunct)

Let $x$ be a real number. (a) Prove that $\left| x \right| + x \ge 0$ . (b) Prove that if $x^2 = x$ and $x \ne 0$ , then $x = 1$ . Tag each step with its rule.

Solution. (a) Every real number satisfies $x \ge 0$ or $x < 0$ , and we consider the two cases [ $\mathrm{\vee E}$ ].

Case $x \ge 0$ . Then $\left| x \right| = x$ , so $\left| x \right| + x = 2x \ge 0$ .

Case $x < 0$ . Then $\left| x \right| = -x$ , so $\left| x \right| + x = 0$ , and certainly $\left| x \right| + x \ge 0$ [ $\mathrm{\vee I}$ ].

So $\left| x \right| + x \ge 0$ in either case [ $\mathrm{\vee E}$ , closing].

(b) Suppose $x^2 = x$ and $x \ne 0$ [assumption for $\mathrm{{\to}I}$ ]. Then $x(x - 1) = x^2 - x = 0$ , and a product of two real numbers is $0$ only if one factor is, so $x = 0$ or $x - 1 = 0$ [ $\mathrm{{\to}E}$ ]. Since $x \ne 0$ , the first case is impossible, so $x - 1 = 0$ [ $\mathrm{DS}$ ], that is, $x = 1$ .

In (a), the split was announced with the disjunction that makes it exhaust; $\mathrm{\vee E}$ needs that disjunction on a line, and a split without it is the missing-case error that Section 8.6 catalogues. The second case weakened $\left| x \right| + x = 0$ to $\left| x \right| + x \ge 0$ , which is $\mathrm{\vee I}$ . The closing “in either case” could be silent. In (b), the words “the first case is impossible” carry the fact $x \ne 0$ that $\mathrm{DS}$ uses: the rule’s name is not needed, but that fact is.

Warning. “Clearly” often hides a case split. “Clearly $\max\{a, b\} \ge (a + b)/2$ ” is true for all real $a, b$ , but its proof is $\mathrm{\vee E}$ on “ $a \le b$ or $b \le a$ ”: if $a \le b$ , then $\max\{a, b\} = b = (b + b)/2 \ge (a + b)/2$ , and the other case is the same with the letters exchanged. The case split is never silent; write it, or write “by cases on whether $a \le b$ ” and the one computation.

8.1.8. Negation and contradiction

Rule	Phrases	Silent in plain prose?
$\mathrm{\neg I}$	“suppose $P$ ; … a contradiction; hence $\neg P$ ”; “ $P$ is impossible, since …”	never
$\mathrm{\neg E}$	“this contradicts …”; “which is impossible”; “but …”	never: the clashing pair is named
$\mathrm{\bot E}$	“this case cannot occur”; “vacuously”; “there is nothing to prove”	yes, once the contradiction or the empty case is stated
$\mathrm{DM}$ , quantifier negation	“not all … so some … fails”; “it is not the case that …, so …”	the negated form must be written

In analysis, $\mathrm{\neg I}$ is the proof of Theorem 2.2.1: “suppose some rational $r$ has $r^2 = 2$ ; …; this is a contradiction; hence no rational number has square $2$ ”. $\mathrm{\neg E}$ is a sentence such as “then $n \le 1/\varepsilon < n$ , a contradiction”: the chain gives $n < n$ , which clashes with the fact that no number is less than itself. One strict link is essential, since $n \le 1/\varepsilon \le n$ gives only $n \le n$ , which clashes with nothing. $\mathrm{\bot E}$ is “if $A = \emptyset$ , there is nothing to prove”, said of a claim about every element of $A$ : with no element to check, the claim is vacuously true (Section 5.4).

The last row needs more room. To negate “ $s$ is an upper bound of $A$ ”, that is, $\forall a \in A\; (a \le s)$ , a proof writes the negated form: some $a \in A$ has $a > s$ . Write the negated form out; do not leave the reader to push a “not” through a quantifier in their head.

Second readingFor the record: where the classical step sits

The passage uses Proposition 6.2.3 (a), derived with $\mathrm{RAA}$ , and the order fact that $\neg(a \le s)$ says $a > s$ . A proof that $\mathbb{N}$ is not bounded above is the instructive case. It opens “suppose, for contradiction, that $\mathbb{N}$ is bounded above” and closes with “therefore $\mathbb{N}$ is not bounded above”; that is $\mathrm{\neg I}$ , despite the phrase. Its one classical step comes after the box: from “not every $n \in \mathbb{N}$ has $n \le x$ ” it passes to “some $n \in \mathbb{N}$ has $n > x$ ”, by Proposition 6.2.3 (a), which Section 6.2 derives with $\mathrm{RAA}$ through Proposition 6.2.1 (a) and Proposition 6.2.2, and then by trichotomy for $\neg(n \le x)$ , giving $n > x$ . That step produces an $n$ without naming it, and the proof needs no name.

Example (A negative claim, its positive form, and an empty case)

(a) Prove that no real number is an upper bound of $\mathbb{R}$ . (b) Prove the positive form: for every real $s$ there is a real $x$ with $x > s$ . (c) Let $A$ be an empty set of real numbers. Prove that every real number is an upper bound of $A$ . Tag each step with its rule.

Solution. (a) Let $s$ be a real number [ $\mathrm{\forall I}$ ], and suppose $s$ is an upper bound of $\mathbb{R}$ [assumption for $\mathrm{\neg I}$ ]. Since $s + 1$ is a real number, $s + 1 \le s$ [ $\mathrm{\forall E}$ at $s + 1$ ], that is, $1 \le 0$ . This contradicts $0 < 1$ [ $\mathrm{\neg E}$ ]. Hence $s$ is not an upper bound of $\mathbb{R}$ [ $\mathrm{\neg I}$ ].

(b) Let $s$ be a real number [ $\mathrm{\forall I}$ ]. Take $x \mathrel{:=} s + 1$ [ $\mathrm{\exists I}$ ]; then $x - s = 1 > 0$ , so $x > s$ .

(c) Let $s$ be a real number and $a \in A$ [ $\mathrm{\forall I}$ , $\mathrm{{\to}I}$ ]. Since $A$ has no elements, $a \in A$ is impossible [ $\mathrm{\neg E}$ , against “ $a \notin A$ ”], so there is nothing to prove: $a \le s$ [ $\mathrm{\bot E}$ ]. Hence $s$ is an upper bound of $A$ .

Claim (a) is $\forall s\, \neg\forall x\; (x \le s)$ , and its proof writes the $\mathrm{\neg I}$ box in full: the assumption, the named clash, the conclusion. The positive form (b), $\forall s\, \exists x\; (x > s)$ , says more: it hands over the number that beats $s$ . Given (b) as a premise, (a) follows with no classical step: if $s$ were an upper bound of $\mathbb{R}$ , the $x$ that (b) provides for $s$ would satisfy $x > s$ and $x \le s$ . The general passage from the shape of (a) to the shape of (b), with no witness in hand, goes through Proposition 6.2.1 (a), derived with $\mathrm{RAA}$ , and trichotomy. So when both forms are within reach, prove the positive one. In (c), once the clash and the empty set are named, the $\mathrm{\bot E}$ line itself may be silent. Part (c) is the prose form of the derivation in Section 5.4 that concludes $\forall u\, \forall x\; (x \in A \to x \le u)$ from $\forall x\, \neg(x \in A)$ , with its vacuous step unpacked into the $\mathrm{\neg E}$ and $\mathrm{\bot E}$ lines.

8.1.9. Proof by contradiction

Why tell $\mathrm{RAA}$ from $\mathrm{\neg I}$ at all? Some mathematicians accept every rule of this book except $\mathrm{RAA}$ . For them a proof should hand over what it claims: a proof that something exists should say what exists, and a proof of “ $P$ or $Q$ ” should say which. $\mathrm{\neg I}$ keeps that promise; $\mathrm{RAA}$ can break it, and Section 8.7 shows a proof that two such numbers exist which never says which numbers they are. For now, learn to see which of the two a proof uses.

Rule	Phrases	Silent in plain prose?
$\mathrm{RAA}$	“suppose, for contradiction, that $\neg P$ ”; “suppose not”; “assume the contrary”	never
$\mathrm{\neg\neg E}$ , $\mathrm{LEM}$	“either $P$ or not”; “ $P$ must hold, since …”; “otherwise”	never: written as an explicit case split or an explicit removal of a double negation (“ $P$ must hold, since …”)

In analysis, $\mathrm{RAA}$ is the proof of Proposition 6.2.5: “suppose, for a contradiction, that $a \ne b$ ; then $\left| a - b \right| > 0$ , so the hypothesis gives $\left| a - b \right| < \left| a - b \right|$ , a contradiction; hence $a = b$ ”. The box assumes $\neg(a = b)$ and concludes $a = b$ , so it is genuine $\mathrm{RAA}$ ; $\mathrm{\neg I}$ would give only $\neg\neg(a = b)$ . $\mathrm{LEM}$ is a split such as “either the sequence has infinitely many terms in the left half of the interval, or it does not”, a step of the bisection proof of the Bolzano–Weierstrass theorem. That split is genuinely non-constructive: nobody can decide in general which case holds. Section 8.7 explains why that matters, and a proof that makes such a step says so in one clause. A split such as “ $x \ge 0$ or $x < 0$ ” is also excluded middle in logical form, but it is an instance of the trichotomy of the order of $\mathbb{R}$ , one of the axioms for the real numbers, and it is never flagged.

Example (One proof by contradiction, read two ways)

Let $a$ and $b$ be real numbers with $a \le b + \varepsilon$ for every $\varepsilon > 0$ . Prove that $a \le b$ , first by $\mathrm{RAA}$ ; then rewrite the proof as a case split.

Solution. By $\mathrm{RAA}$ . Suppose, for a contradiction, that $a > b$ [assumption for $\mathrm{RAA}$ ]. Then $\varepsilon \mathrel{:=} (a - b)/2$ is positive, so the hypothesis gives $a \le b + (a - b)/2$ [ $\mathrm{\forall E}$ at $(a - b)/2$ ], that is, $2a \le a + b$ , so $a \le b$ . This contradicts $a > b$ [ $\mathrm{\neg E}$ ]. Hence $a \le b$ [ $\mathrm{RAA}$ ].

The box assumes $a > b$ , which is $\neg(a \le b)$ by the order fact of Section 2.1, and the proof concludes $a \le b$ : a negation goes out.

By cases. By trichotomy, $a \le b$ or $a > b$ [ $\mathrm{\vee E}$ ]. In the first case we are done. In the second, the lines of the box above reach $a \le b$ against $a > b$ , so this case cannot occur, and in it $a \le b$ [ $\mathrm{\neg E}$ , $\mathrm{\bot E}$ ]. In either case $a \le b$ .

The two proofs share their mathematics, the instance $\varepsilon = (a - b)/2$ , and differ only in how the classical step is written: as $\mathrm{RAA}$ , or as a split on trichotomy, which over $\mathbb{R}$ is an axiom. Neither is flagged: $a > b$ is $\neg(a \le b)$ by trichotomy, so $\mathrm{RAA}$ adds nothing beyond that axiom. The fold below writes the same box closed by $\mathrm{\neg I}$ and followed by $\mathrm{\neg\neg E}$ .

Second readingThe same proof by ¬I and ¬¬E

By $\mathrm{\neg I}$ and $\mathrm{\neg\neg E}$ . Close the same box with “hence $a > b$ is impossible” [ $\mathrm{\neg I}$ ], the line $\neg(a > b)$ , which is $\neg\neg(a \le b)$ under the same reading of $a > b$ as $\neg(a \le b)$ ; then “so $a \le b$ must hold” [ $\mathrm{\neg\neg E}$ ]. The two steps do what $\mathrm{RAA}$ did in one, and show that the box itself uses no classical rule.

With this third version the proofs differ only in how the classical step is written: as $\mathrm{RAA}$ , as $\mathrm{\neg\neg E}$ , or as a case split. All three also read $a > b$ as $\neg(a \le b)$ by the order fact of Section 2.1, itself an instance of trichotomy; read the other way, that fact gives $a \le b$ from $\neg(a > b)$ directly, so the first two put an excluded-middle step on top of it. Over $\mathbb{R}$ trichotomy is an axiom, so no step here is flagged.

8.1.10. The biconditional

Rule	Phrases	Silent in plain prose?
$\mathrm{{\leftrightarrow}I}$	“ $(\Rightarrow)$ … $(\Leftarrow)$ …”; “conversely”; “we prove both directions”	never either direction
$\mathrm{{\leftrightarrow}E}$	“by definition”; “that is”; “i.e.”; “equivalently”	yes, for a definitional “if and only if”

In analysis, Theorem 2.4.5 of Section 2.4 (for $x, y \ge 0$ , $x \le y \iff x^2 \le y^2$ ) is the model of $\mathrm{{\leftrightarrow}I}$ : two labeled directions, each a $\mathrm{{\to}I}$ box. $\mathrm{{\leftrightarrow}E}$ is every unwinding of a definition: “ $f$ is strictly increasing, that is, $x < y$ implies $f(x) < f(y)$ ” (Example (A definition used in both directions)). A definition is an “if and only if” (Section 2.4), and the words “that is” use it in one direction or the other.

Example (Both directions, the second by cases)

Let $x$ be a real number with $x \ge 0$ . Prove that $x \le 1$ if and only if $x^2 \le x$ . Tag each step with its rule.

Solution. $(\Rightarrow)$ Suppose $x \le 1$ [assumption for $\mathrm{{\to}I}$ ]. Multiplying by $x \ge 0$ gives $x^2 \le x$ .

$(\Leftarrow)$ Conversely, suppose $x^2 \le x$ [assumption for $\mathrm{{\to}I}$ ]. Since $x \ge 0$ , either $x = 0$ or $x > 0$ [ $\mathrm{\vee E}$ ]. If $x = 0$ , then $x \le 1$ . If $x > 0$ , dividing $x^2 \le x$ by $x$ gives $x \le 1$ .

So $x \le 1$ if and only if $x^2 \le x$ [ $\mathrm{{\leftrightarrow}I}$ ].

The labels $(\Rightarrow)$ and $(\Leftarrow)$ are the two boxes of $\mathrm{{\leftrightarrow}I}$ , and “conversely” opens the second.

Second readingA nonnegativity hypothesis, direction by direction

The hypothesis $x \ge 0$ does a job in each: it keeps the inequality’s direction when we multiply, and it reduces the cases to $x = 0$ and $x > 0$ , by $\mathrm{{\leftrightarrow}E}$ on the definition of $\ge$ . Without it, $(\Leftarrow)$ still holds, since a negative $x$ has $x^2 \ge 0 > x$ , so $x^2 \le x$ forces $x \ge 0$ and the proof above applies; but $(\Rightarrow)$ fails: $x = -1$ has $x \le 1$ and $x^2 = 1 > x$ .

8.1.11. Equivalent conditions, by a cycle

Theorems often say that several conditions are equivalent (“the following are equivalent”, TFAE). Proving each pair both ways would take six implications for three conditions. A cycle takes three.

Pattern	Phrases	Silent in plain prose?
TFAE by a cycle (Proposition 2.4.6)	“the following are equivalent”; “we prove (i) $\Rightarrow$ (ii) $\Rightarrow$ (iii) $\Rightarrow$ (i)”	never any arrow of the cycle, the last one included

Second readingA cycle, worked

Example (Three conditions, one cycle)

Let $n$ be an integer. Prove that the following are equivalent: (i) $n$ is odd; (ii) $n^2$ is odd; (iii) $n^2 + 2n$ is odd. Tag the steps that carry the logic.

Solution. By Proposition 2.4.6 it suffices to prove (i) $\Rightarrow$ (ii), (ii) $\Rightarrow$ (iii) and (iii) $\Rightarrow$ (i).

- (i) $\Rightarrow$ (ii) is the direction $(\Rightarrow)$ of Theorem 2.4.4.
- (ii) $\Rightarrow$ (iii): Suppose $n^2$ is odd [assumption for $\mathrm{{\to}I}$ ], say $n^2 = 2a + 1$ [ $\mathrm{\exists E}$ ]. Then $n^2 + 2n = 2(a + n) + 1$ , which is odd [ $\mathrm{\exists I}$ , witness $a + n$ ].
- (iii) $\Rightarrow$ (i): Suppose $n^2 + 2n$ is odd. By (E1), $n$ is even or odd [ $\mathrm{\vee E}$ ].
- If $n$ is even, say $n = 2k$ [ $\mathrm{\exists E}$ ], then $n^2 + 2n = 2(2k^2 + 2k)$ is even. So $n^2 + 2n$ is even and odd, which (E2) forbids [ $\mathrm{\neg E}$ ]: this case cannot occur [ $\mathrm{\bot E}$ ].
- If $n$ is odd, there is nothing more to show.
- So $n$ is odd.

The cycle closes.

Three implications did the work of six. The last arrow, (iii) $\Rightarrow$ (i), is the one a hurried writer omits. Without it the proof shows only (i) $\Rightarrow$ (ii) $\Rightarrow$ (iii), and no condition later in the chain gives back an earlier one. The case split in (iii) $\Rightarrow$ (i) uses no $\mathrm{RAA}$ : the impossible case reaches the goal by $\mathrm{\bot E}$ , as in Example (One proof by contradiction, read two ways)’s case version.

Quick check. To prove four conditions (i)–(iv) equivalent, a writer proves (i) $\Rightarrow$ (ii), (ii) $\Rightarrow$ (iii), (iii) $\Rightarrow$ (iv) and (iv) $\Rightarrow$ (ii). Is that enough?

Solution. No. (ii), (iii) and (iv) are shown equivalent, but nothing leads back to (i): (ii) $\Rightarrow$ (i) is never shown. A fifth implication (ii) $\Rightarrow$ (i) would do, or (iv) $\Rightarrow$ (i) in place of (iv) $\Rightarrow$ (ii).

8.1.12. The three faces of “by contradiction”

“Proof by contradiction” is used in practice for three different arguments. Each opens a box and finds $\bot$ inside it; they differ in what the box assumes and what the proof concludes. Only face (i) is always free of a classical step.

Face	The box assumes	The proof concludes	Last step	A tiny example
(i) refuting	$P$	$\neg P$	$\mathrm{\neg I}$	“ $7$ is not even”
(ii) contrapositive	$\neg Q$ , inside “suppose $P$ ”	$P \to Q$ , from $\neg Q \to \neg P$	Proposition 2.5.2	“if $n^2$ is even, then $n$ is even”
(iii) genuine	$\neg P$	$P$	$\mathrm{RAA}$	“if $a \le b + \varepsilon$ for every $\varepsilon > 0$ , then $a \le b$ ”

(i) Refuting a statement. The claim is negative: irrational, “no largest”, $x \ne 5$ . The box assumes the positive statement, as the proof of Theorem 2.2.1 assumes $r^2 = 2$ , and no classical rule is used.

(ii) The contrapositive. The claim is $P \to Q$ , and the proof derives $\neg P$ from $\neg Q$ , with $P$ playing no part until the end. The passage back to $P \to Q$ is Proposition 2.5.2, which Section 2.5 derives with $\mathrm{RAA}$ . Written as “suppose $P$ ; suppose, for contradiction, $\neg Q$ ; … $\neg P$ , a contradiction”, it is that derivation done inline.

Second readingWhen the contrapositive needs no classical step

Face (ii) ends with Proposition 2.5.2, which Section 2.5 derives with $\mathrm{RAA}$ ; that $\mathrm{RAA}$ is avoidable when $Q$ is itself a negation, by the fold “RAA is never needed to finish a negation” of Section 2.5. So face (ii) uses $\mathrm{RAA}$ unless $Q$ is itself a negation.

(iii) Genuine reductio. The claim $P$ is positive, and $\neg P$ is used throughout the box, typically because it hands over an object: $a \ne b$ makes $\left| a - b \right|$ a positive number to feed to a hypothesis about every $\varepsilon > 0$ .

To tell them apart, read the first sentence of the box and the sentence after it: what does it assume, and what does the proof write after it closes? The words “for contradiction” do not decide it; a proof that $\mathbb{N}$ is not bounded above uses them for a face (i) proof: it supposes $\mathbb{N}$ bounded and concludes that it is not.

The style rule: use the weakest form that works, and say which one you use. A direct proof, when one exists, beats all three. A negative claim is proved by face (i). Face (ii) is announced as “we prove the contrapositive”, which tells the reader the goal $\neg Q \to \neg P$ at once. Face (iii) is for a positive claim that resists the other routes, with its classical step made visible as in Example (One proof by contradiction, read two ways).

Quick check. Which face? (i) “Suppose $\sqrt 3 = p/q$ with integers $p$ , $q$ . … a contradiction. Hence $\sqrt 3$ is irrational.” (ii) “Suppose $n^2$ is odd. Suppose, for a contradiction, that $n$ is not odd. Then $n$ is even, say $n = 2k$ , so $n^2 = 4k^2 = 2(2k^2)$ is even, hence not odd, which contradicts $n^2$ being odd. Hence $n$ is odd.”

Solution.

(i) Face (i): the box assumes the positive statement “ $\sqrt 3$ is rational” and concludes its negation, by $\mathrm{\neg I}$ . (ii) Face (ii): the box assumes $\neg Q$ , “ $n$ is not odd”, and derives “ $n^2$ is not odd” from it alone; the hypothesis “ $n^2$ is odd” enters only at the clash. That is a contrapositive in costume.

8.1.13. Costumes

A proof written as “suppose, for contradiction, …” sometimes uses its assumption for nothing except the final clash. It is then a direct proof or a contrapositive proof in costume, and it reads better with the costume off. Section 2.5 met the smallest case; here are the two costumes as they appear in prose, each with a test to run on a finished proof.

Example (A direct proof in costume)

Here is a proof that $x^2 - 2x > 3$ for every real $x > 3$ . Decide what it really uses, and rewrite it.

Let $x > 3$ . Suppose, for a contradiction, that $x^2 - 2x \le 3$ . Since $x > 3$ , both $x - 3$ and $x + 1$ are positive, so $(x - 3)(x + 1) > 0$ , that is, $x^2 - 2x - 3 > 0$ . So $x^2 - 2x > 3$ . This contradicts our assumption. Hence $x^2 - 2x > 3$ .

Solution. The assumption “ $x^2 - 2x \le 3$ ” is cited exactly once, in “This contradicts our assumption”. The sentences before it prove $x^2 - 2x > 3$ from $x > 3$ alone, so the $\mathrm{RAA}$ box contains a complete derivation of the goal. Deleting the box leaves a direct proof:

Let $x > 3$ . Then $x - 3 > 0$ and $x + 1 > 0$ , so $x^2 - 2x - 3 = (x - 3)(x + 1) > 0$ , that is, $x^2 - 2x > 3$ .

Nothing is lost, the $\mathrm{RAA}$ is gone, and the reader no longer holds a false assumption in mind for three sentences.

The test: if the assumption of the box is cited only in the line that produces $\bot$ , the box proved the goal without it. Delete the box.

Example (A contrapositive in costume)

Here is a proof that, for an integer $n$ , if $n^2$ is even then $n$ is even. Decide what it really uses, and rewrite it.

Suppose $n^2$ is even. Suppose, for a contradiction, that $n$ is not even. Then $n$ is odd, say $n = 2k + 1$ with $k$ an integer. Then $n^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$ is odd, so $n^2$ is not even. This contradicts the fact that $n^2$ is even. Hence $n$ is even.

Solution. Here the assumption of the box, “ $n$ is not even”, is used heavily; what is used only once is the hypothesis “ $n^2$ is even”, in “This contradicts …”. The sentences between derive “ $n^2$ is not even” from “ $n$ is not even” alone. So the real content is $\neg Q \to \neg P$ , with $P$ the statement “ $n^2$ is even” and $Q$ the statement “ $n$ is even”, and the frame around it is Proposition 2.5.2 done inline: face (ii). Written openly:

We prove the contrapositive: if $n$ is not even, then $n^2$ is not even. Suppose $n$ is not even. Then $n$ is odd, say $n = 2k + 1$ with $k$ an integer, and $n^2 = 2(2k^2 + 2k) + 1$ is odd, so it is not even.

The rewrite tells the reader at the start what will be shown, and the final clash disappears. The classical step has not: it is now inside the announcement, which uses Proposition 2.5.2. (The proof by cases of Theorem 2.1.3 in Section 2.1 needs no $\mathrm{RAA}$ at all.)

The test: if everything inside the box follows from its assumption $\neg Q$ alone, and the hypothesis $P$ of the theorem enters only in the line that produces $\bot$ , then the box proved $\neg Q \to \neg P$ . Present it as a contrapositive.

Second readingThe smell the two tests share

The two tests share one smell: the clash at the end is with a statement the proof already had, or would have had without the box. A genuine reductio uses its assumed negation throughout, and the clash comes somewhere the reader did not see coming; in Example (One proof by contradiction, read two ways), the assumption $a > b$ was what made $(a - b)/2$ positive.

Warning. “Assume $P$ ” means different things at the top of different proofs. At the top of a proof of $P \to Q$ , it is the opening of the $\mathrm{{\to}I}$ box, and it is exactly right. At the top of a proof of $P$ itself, it assumes the goal, and everything after it is circular: the last line “hence $P$ ” cites a line that is not available outside the box. For instance, “assume $\sqrt 2$ is irrational; then … ; hence $\sqrt 2$ is irrational” proves nothing, however correct the middle: it is entry (N9) of the catalogue in Section 8.6.

Warning (Not allowed: connective 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.

“Suppose $x \ge 1$ ; then $x^3 \ge x$ . Hence $x^3 \ge x$ for every real $x$ .” The line $x^3 \ge x$ belongs to a box that has closed; outside it only “if $x \ge 1$ , then $x^3 \ge x$ ” is available: (N10). The conclusion is false at $x = \tfrac12$ .
“To prove $\left| x \right| < 1$ , suppose, for a contradiction, that $\left| x \right| > 1$ .” The negation of $\left| x \right| < 1$ is $\left| x \right| \ge 1$ : (N11)(a).
“Suppose $n$ is odd. Then $n^2$ is odd.”, as the whole proof of “if $n^2$ is even, then $n$ is even”. Without the announcement the reader sees a box that opens with neither the hypothesis nor the conclusion of the goal: the never-silent item “the announcement of a contrapositive”.
“Case 1: $x \ge 0$ , so $\left| x \right| = x \ge 0$ . In either case $\left| x \right| \ge 0$ .” There is one case and no disjunction: (N7).

8.1.14. Exercises

A. Check your understanding

Exercise (A1)

(a) Name the rule that each phrase most often carries: (i) “in particular”; (ii) “conversely”; (iii) “in either case”; (iv) “this case cannot occur”; (v) “suppose, for contradiction, that $x$ is not positive”; (vi) “we prove the contrapositive”; (vii) “that is”; (viii) “since $x \ne 0$ , the first case is impossible”; (ix) “so $x \ge 0$ ”, after “ $x > 0$ ”; (x) “which contradicts $x^2 \ge 0$ ”.
(b) Which of the phrases in (a) carry steps that may be silent in plain prose?
(c) A proof ends “Suppose $7 = 2k$ for an integer $k$ . Then $k = 7/2$ , which is not an integer. Hence $7$ is not even.” Which face of “by contradiction” is this?
(d) True or false, with a reason: a proof that begins “suppose, for contradiction” always uses $\mathrm{RAA}$ .

Solution. (a) (i) $\mathrm{\wedge E}$ . (ii) $\mathrm{{\leftrightarrow}I}$ , opening the second direction. (iii) $\mathrm{\vee E}$ , closing. (iv) $\mathrm{\bot E}$ . (v) $\mathrm{RAA}$ , opening its box (the goal is “ $x$ is positive”, and the box assumes its negation). (vi) $\mathrm{CP}$ , or, as the frame of a whole proof, Proposition 2.5.2. (vii) $\mathrm{{\leftrightarrow}E}$ , on a definition. (viii) $\mathrm{DS}$ . (ix) $\mathrm{\vee I}$ . (x) $\mathrm{\neg E}$ .

(b) (i), (iii) (the closing “in either case”), (iv) (once the contradiction is stated), (vii) (for a definition), and (ix). In (viii) the name of $\mathrm{DS}$ may be dropped, but not the fact $x \ne 0$ . The openings (ii), (v), (vi) and the clash (x) are never silent.

(c) Face (i), refuting: the box assumes the positive statement “ $7$ is even”, that is, $7 = 2k$ for some integer $k$ , and the proof concludes its negation, by $\mathrm{\neg I}$ . (The value $7/2$ is not an integer because $3 < 7/2 < 4$ .)

(d) False. The phrase also opens $\mathrm{\neg I}$ boxes. A proof that $\mathbb{N}$ is not bounded above may begin “suppose, for contradiction, that $\mathbb{N}$ is bounded above” and conclude the negation, by $\mathrm{\neg I}$ . What decides is what the box assumes and what the proof concludes.

Exercise (A2: Drill)

Name the rule each phrase carries, and say whether plain prose may leave it out. Some parts ask a different question, and say so.

(a) “Suppose $n$ is odd.”, at the start of a proof of “if $n$ is odd, then $n^2$ is odd”.
(b) “In either case, $x^2 \ge 0$ .”
(c) “Since $x \ne 0$ , the first case is impossible, so $x = 3$ ”, after “ $x = 0$ or $x = 3$ ”.
(d) “ $x > 2$ , so certainly $x \ge 2$ .”
(e) “This contradicts $n^2 \ge 0$ .”
(f) “Conversely, suppose $x^2 = 4$ and $x > 0$ .”
(g) “Suppose, for a contradiction, that $n$ is not prime”, in a proof that ends “Hence $n$ is prime.”
(h) A proof that $\sqrt 5$ is irrational opens: “Suppose, for a contradiction, that $\sqrt 5$ is rational.” Which annotation would its derivation print beside that assumption?
(i) “Suppose $15$ is a perfect square. … a contradiction. Hence $15$ is not a perfect square.” Which face of “by contradiction” is this?
(j) A proof of “if $x^2 < 1$ , then $x > -1$ ” begins “Suppose $x \le -1$ . Then $-x \ge 1$ , so $x^2 = (-x)^2 \ge 1$ .” What should come before it?
(k) “Let $n$ be even, say $n = 2k$ . Suppose, for a contradiction, that $n^2$ is not even. Then $n^2 = 4k^2 = 2(2k^2)$ is even, which contradicts $n^2$ not being even. Hence $n^2$ is even.” Is this proof in costume?
(l) Four conditions are to be shown equivalent. How many implications does a cycle need, and how many would proofs of every ordered pair need?

Solution.

(a) $\mathrm{{\to}I}$ , opening; never silent.
(b) $\mathrm{\vee E}$ , closing; may be silent.
(c) $\mathrm{DS}$ ; its name may go, the fact $x \ne 0$ may not.
(d) $\mathrm{\vee I}$ ( $x \ge 2$ is $x > 2 \vee x = 2$ ); may be silent.
(e) $\mathrm{\neg E}$ ; never silent: both lines of the clash are named.
(f) $\mathrm{{\leftrightarrow}I}$ , opening the second direction; never silent.
(g) $\mathrm{RAA}$ , opening; never silent.
(h) “asm, for $\mathrm{\neg I}$ ”. The goal, “ $\sqrt 5$ is irrational”, is the negation “ $\sqrt 5$ is not rational”. The box assumes the positive statement and is closed by $\mathrm{\neg I}$ , whatever the words “for a contradiction” suggest: Section 2.5’s distinction, face (i) of “The three faces”. (No fact about $\sqrt 5$ is needed.)
(i) Face (i), refuting: $\mathrm{\neg I}$ .
(j) The announcement “We prove the contrapositive” ( $\mathrm{CP}$ ; never silent).
(k) Yes, a direct proof in costume: the assumption is cited only at the clash; delete the box. (The box opens with the negation of the goal, so the item is not an instance of (N11)(a).)
(l) Four for a cycle. Twelve for every ordered pair ( $4 \cdot 3$ ), that is, six biconditionals.

B. Practice

Exercise (B1: Take off the costume)

Here is a proof that $\frac{a + b}{2} \ge \sqrt{ab}$ for all real $a > 0$ and $b > 0$ .

Let $a, b > 0$ . Suppose, for a contradiction, that $\frac{a+b}{2} < \sqrt{ab}$ . Since $(\sqrt a - \sqrt b)^2 \ge 0$ , expanding gives $a - 2\sqrt{ab} + b \ge 0$ , so $\frac{a+b}{2} \ge \sqrt{ab}$ . This contradicts our assumption. Hence $\frac{a+b}{2} \ge \sqrt{ab}$ .

(a) Which costume is this? Justify your answer by saying where the assumption of the box is cited.
(b) Rewrite the proof without the contradiction.

Solution. (a) A direct proof in costume (Example (A direct proof in costume)). The assumption $\frac{a+b}{2} < \sqrt{ab}$ is cited only in “This contradicts our assumption”, the line that produces $\bot$ . The sentence beginning “Since” proves the goal from $a, b > 0$ alone, without using the assumption.

(b) Let $a, b > 0$ , so that $\sqrt a$ and $\sqrt b$ are defined and $\sqrt a \sqrt b = \sqrt{ab}$ . Since $(\sqrt a - \sqrt b)^2 \ge 0$ , expanding gives $a - 2\sqrt{ab} + b \ge 0$ . Adding $2\sqrt{ab}$ to both sides and dividing by $2$ gives $\frac{a+b}{2} \ge \sqrt{ab}$ , as claimed.

Exercise (B2: Where the classical step sits)

Here is a proof that if $x$ is a real number with $\left| x \right| \le \left| y \right|$ for every real $y \ne 0$ , then $x = 0$ .

Suppose $\left| x \right| \le \left| y \right|$ for every real $y \ne 0$ . Suppose, for a contradiction, that $x \ne 0$ . Then $y \mathrel{:=} x/2$ is a non-zero real number, so the hypothesis gives $\left| x \right| \le \left| x/2 \right| = \left| x \right|/2$ , and hence $\left| x \right| \le 0$ . But $\left| x \right| > 0$ , since $x \ne 0$ . This is a contradiction. Hence $x = 0$ .

(a) Is the last step $\mathrm{RAA}$ or $\mathrm{\neg I}$ ? Is the proof in costume?
(b) Rewrite it so that the box closes by $\mathrm{\neg I}$ and one further step removes a double negation. Tag the two steps.
(c) Which of the two versions tells the reader more, and what?

Solution. (a) $\mathrm{RAA}$ : the box assumes $\neg(x = 0)$ , written $x \ne 0$ , and the proof concludes the positive statement $x = 0$ . It is not in costume. The assumption does work inside the box (it makes $x/2$ non-zero, so that the hypothesis applies to it), and the hypothesis is used in the middle of the box, not only at the clash; neither test of this section is met.

(b) Suppose $\left| x \right| \le \left| y \right|$ for every real $y \ne 0$ . If $x \ne 0$ , then $x/2 \ne 0$ , so the hypothesis gives $\left| x \right| \le \left| x \right|/2$ , that is, $\left| x \right| \le 0$ , against $\left| x \right| > 0$ . Hence $x \ne 0$ is impossible [ $\mathrm{\neg I}$ ], so $x = 0$ must hold [ $\mathrm{\neg\neg E}$ ].

(c) The second. It shows that the box uses no classical rule: without one, the argument proves $\neg\neg(x = 0)$ , “ $x$ cannot be non-zero”, and the classical rule enters only in the final step, “so $x = 0$ must hold” [ $\mathrm{\neg\neg E}$ ]. The first version does both steps at once in the single $\mathrm{RAA}$ , and so hides where the classical rule enters.

Exercise (B3: Two clauses of a least upper bound)

Let $A \mathrel{:=} \{ x \in \mathbb{R} : 0 < x < 2 \}$ . Prove that $2$ is an upper bound of $A$ , and that no real number $t < 2$ is an upper bound of $A$ . Tag each step with its rule.

Hint: in the second part, take a number halfway between $\max\{t, 0\}$ and $2$ .

Solution. (a) Let $a \in A$ [ $\mathrm{\forall I}$ ]. Then $0 < a < 2$ , by the definition of $A$ ; in particular $a < 2$ [ $\mathrm{\wedge E}$ ], so $a \le 2$ [ $\mathrm{\vee I}$ ]. So $2$ is an upper bound of $A$ .

(b) Let $t$ be a real number with $t < 2$ [ $\mathrm{\forall I}$ , $\mathrm{{\to}I}$ ], and suppose $t$ is an upper bound of $A$ [assumption for $\mathrm{\neg I}$ ]. Let $m \mathrel{:=} \max\{t, 0\}$ and $a \mathrel{:=} (m + 2)/2$ . We have $t \ge 0$ or $t < 0$ , and by the definition of the maximum we consider the two cases [ $\mathrm{\vee E}$ ]: if $t \ge 0$ , then $m = t$ , so $m \ge t$ , $m \ge 0$ and $m < 2$ ; if $t < 0$ , then $m = 0$ , so $m > t$ , $m \ge 0$ and $m < 2$ . So in either case $m \ge t$ and $0 \le m < 2$ . Hence $1 \le a < 2$ ; thus $0 < a$ and $a < 2$ , that is, $a \in A$ [ $\mathrm{\wedge I}$ ]. As $t$ is an upper bound of $A$ , $a \le t$ [ $\mathrm{\forall E}$ at $a$ ]. But $a - m = (2 - m)/2 > 0$ , so $a > m \ge t$ , and $a > t$ . This contradicts $a \le t$ [ $\mathrm{\neg E}$ ]. Hence $t$ is not an upper bound of $A$ [ $\mathrm{\neg I}$ ].

So $2$ is an upper bound of $A$ , and no smaller number is [ $\mathrm{\wedge I}$ ].

The $\mathrm{\wedge E}$ of (a) could have been silent (“then $a < 2$ , so $a \le 2$ ”); the $\mathrm{\vee I}$ after it weakened a strict inequality, since $a \le 2$ means $a < 2 \vee a = 2$ . In (b), the two conjuncts $0 < a$ and $a < 2$ were displayed and then merged by “that is, $a \in A$ ”. The bound $m < 2$ needed the case split hidden in $\max$ , and it is written out, as the warning on “clearly” in “Disjunction and cases” requires. The final sentence is the $\mathrm{\wedge I}$ of the two clauses. And the clashing lines $a \le t$ and $a > t$ are both named before “contradicts”, as the $\mathrm{\neg E}$ row of the dictionary requires.

Exercise (B4: Two integers of the same parity)

Let $a$ and $b$ be integers. Prove that the following are equivalent, by a cycle: (i) $a + b$ is even; (ii) $a - b$ is even; (iii) $a$ and $b$ are both even or both odd. Say which arrow closes the cycle, and tag the logical steps of that arrow.

Solution. By Proposition 2.4.6, three implications suffice.

- (i) $\Rightarrow$ (ii): Suppose $a + b$ is even; choose $k$ with $a + b = 2k$ [ $\mathrm{\exists E}$ ]. Then $a - b = (a + b) - 2b = 2(k - b)$ , so $a - b$ is even, with the witness $k - b$ [ $\mathrm{\exists I}$ ].
- (ii) $\Rightarrow$ (iii): Suppose $a - b$ is even, and choose $j$ with $a - b = 2j$ [ $\mathrm{\exists E}$ ]. By (E1), $b$ is even or odd [ $\mathrm{\vee E}$ ].
- If $b = 2m$ [ $\mathrm{\exists E}$ ], then $a = 2(j + m)$ is even [ $\mathrm{\exists I}$ ], so both are even [ $\mathrm{\wedge I}$ , then $\mathrm{\vee I}$ ].
- If $b = 2m + 1$ [ $\mathrm{\exists E}$ ], then $a = 2(j + m) + 1$ is odd [ $\mathrm{\exists I}$ ], so both are odd [ $\mathrm{\wedge I}$ , then $\mathrm{\vee I}$ ].
- (iii) $\Rightarrow$ (i), the closing arrow: Suppose $a$ and $b$ are both even or both odd [assumption for $\mathrm{{\to}I}$ ]. There are two cases [ $\mathrm{\vee E}$ ].
- Both even: choose $s$ and $t$ with $a = 2s$ and $b = 2t$ [ $\mathrm{\exists E}$ twice, two fresh names]. Then $a + b = 2(s + t)$ [ $\mathrm{\exists I}$ , witness $s + t$ ].
- Both odd: choose $s$ and $t$ with $a = 2s + 1$ and $b = 2t + 1$ [ $\mathrm{\exists E}$ twice]. Then $a + b = 2(s + t + 1)$ [ $\mathrm{\exists I}$ , witness $s + t + 1$ ].
- In either case $a + b$ is even [ $\mathrm{\vee E}$ , closing; may be silent in plain prose].

The closing arrow is (iii) $\Rightarrow$ (i). Its logic is a two-case $\mathrm{\vee E}$ , each case with two $\mathrm{\exists E}$ boxes under distinct names and one $\mathrm{\exists I}$ ; no $\mathrm{RAA}$ is used. (The names $s$ , $t$ may be reused in the second case: sibling boxes may share a name, as (N4) of Section 8.6 notes.)

Marking scheme. (10 points) Points are given per role, and a correct proof by another cycle earns the same points for the corresponding arrows. - 2: an arrow proved by one $\mathrm{\exists E}$ and one $\mathrm{\exists I}$ (here (i) $\Rightarrow$ (ii), with $k$ chosen and the witness $k - b$ ). - 3: an arrow from a parity hypothesis, by a split with (E1) named (1) and a witness in each case (2) (here (ii) $\Rightarrow$ (iii), witness $j + m$ ). - 3: an arrow from (iii): the two cases (1); two distinct names in each case (1); the witnesses (1). - 1: the cycle named, with Proposition 2.4.6 or the sentence that three implications suffice, and the closing arrow identified. - 1: the last sentence says what was shown.

Fatal errors (0 for the step): only two arrows proved; one name for both witnesses, “ $a = 2s$ and $b = 2s$ ” (N4); “ $a - b$ is even, so $a$ and $b$ have the same parity” given as its own reason, with neither proof nor citation (N9).

C. Going deeper

Exercise (C1: Euclid without the contradiction)

Here is a common proof that there are infinitely many primes. It uses two facts about integers that we take as known here: every integer $m \ge 2$ has a prime divisor (Sets, Relations, and Cardinality, Chapter 2 proves it); and if an integer $d$ divides two integers, it divides their difference (if $u = dk$ and $v = dl$ , then $u - v = d(k - l)$ ).

Suppose, for a contradiction, that there are only finitely many primes, say $p_1, \dots, p_k$ . Let $N \mathrel{:=} p_1 p_2 \cdots p_k + 1$ . Then $N \ge 2$ , so $N$ has a prime divisor $p$ . Since $p_1, \dots, p_k$ are all the primes, $p = p_i$ for some $i$ . Then $p_i$ divides both $N$ and $p_1 p_2 \cdots p_k$ , so it divides their difference $1$ , which is impossible for a prime. This is a contradiction. Hence there are infinitely many primes.

(a) “There are infinitely many primes” means “the set of primes is not finite”. Is the last step of the proof $\mathrm{RAA}$ or $\mathrm{\neg I}$ ?
(b) Where is the assumption “ $p_1, \dots, p_k$ are all the primes” used? Which smell from this section does that suggest?
(c) Rewrite the argument as a direct proof of: for every finite list $p_1, \dots, p_k$ of primes, with $k \ge 1$ , there is a prime not in the list.
(d) Say what the rewrite gains over the original.

Solution. (a) $\mathrm{\neg I}$ . The box opens with “the set of primes is finite”, the positive statement, and the conclusion is its negation: face (i). No $\mathrm{RAA}$ is used.

(b) Once, in “ $p = p_i$ for some $i$ ”, where the clash is manufactured. Everything else holds for any finite list of primes, complete or not: the smell of a costume.

(c) Let $p_1, \dots, p_k$ be a finite list of primes, $k \ge 1$ , and let $N \mathrel{:=} p_1 p_2 \cdots p_k + 1$ . Each $p_i \ge 2$ , so $N \ge 3$ , and $N$ has a prime divisor $p$ . Let $i$ be an index with $1 \le i \le k$ [ $\mathrm{\forall I}$ , opening], and suppose $p = p_i$ [assumption for $\mathrm{\neg I}$ ]. Then $p$ divides $N$ and $p_1 p_2 \cdots p_k$ , so it divides their difference $1$ , say $1 = pm$ with $m$ an integer. Since $p > 0$ , $m > 0$ , so $m \ge 1$ and $1 = pm \ge p \ge 2$ , a contradiction [ $\mathrm{\neg E}$ ]. Hence $p \ne p_i$ [ $\mathrm{\neg I}$ ]. Since $i$ was arbitrary, $p \ne p_i$ for every $i$ [ $\mathrm{\forall I}$ , closing], and $p$ is a prime not in the list.

(d) The rewrite proves a stronger statement: given any finite list of primes, it produces a prime outside it, any prime divisor of $N$ ; the original shows only that a list of all the primes is impossible. Its one $\mathrm{\neg I}$ box, for the negative claim $p \ne p_i$ , is honest, since its assumption is what the clash uses. The original theorem follows at once: a finite list of all the primes is non-empty, since $2$ is prime, so by (c) it would miss a prime.

Marking scheme. (10 points) - 2: (a) $\mathrm{\neg I}$ , with the reason (the box assumes the positive statement and the proof concludes its negation). - 2: (b) locates the single use of the assumption and names the costume smell. - 4: (c) a proof for an arbitrary finite list: $N$ defined, $N \ge 2$ justified, a prime divisor $p$ taken, $p \ne p_i$ for every $i$ shown. - 2: (d) names the gain: a prime outside any given list is produced. Fatal errors (0 for the step): in (c), a proof that still assumes the list contains all the primes; in (a), calling the step $\mathrm{RAA}$ because of the words “for a contradiction”.

Exercise (C2: Which face, and the weakest form)

Here is a proof that if $x$ is a real number with $x^2 < \varepsilon$ for every $\varepsilon > 0$ , then $x = 0$ .

Suppose $x^2 < \varepsilon$ for every $\varepsilon > 0$ . Suppose, for a contradiction, that $x \ne 0$ . Then $x^2 > 0$ , so we may take $\varepsilon = x^2$ , and the hypothesis gives $x^2 < x^2$ , which is impossible. Hence $x = 0$ .

(a) Which face of “by contradiction” is this, as written?
(b) Rewrite the proof in the weakest form you can, and say which rules it uses at its logical steps, and which school fact.

Solution (Hint 1). The goal $x = 0$ is positive. Look for a school fact about $x^2$ that is a disjunction: one case leads to the goal through another school fact, and the hypothesis rules out the other.

Solution (Hint 2). Start: “Since $x^2 \ge 0$ , either $x^2 > 0$ or $x^2 = 0$ .”

Solution. (a) Face (iii), genuine reductio. The box assumes $\neg(x = 0)$ , written $x \ne 0$ , uses it to make $x^2$ a positive number to which the hypothesis applies, and concludes the positive statement $x = 0$ . The last step is $\mathrm{RAA}$ . It is not in costume: the assumption does work inside the box.

(b) Suppose $x^2 < \varepsilon$ for every $\varepsilon > 0$ [assumption for $\mathrm{{\to}I}$ ]. Since $x^2 \ge 0$ , either $x^2 > 0$ or $x^2 = 0$ , and we consider the two cases [ $\mathrm{\vee E}$ ].

Case $x^2 > 0$ . Then the hypothesis applies to $\varepsilon = x^2$ [ $\mathrm{\forall E}$ ] and gives $x^2 < x^2$ , which contradicts the fact that no number is less than itself [ $\mathrm{\neg E}$ ]. So this case cannot occur, and in it $x = 0$ [ $\mathrm{\bot E}$ ].

Case $x^2 = 0$ . Then $x \cdot x = 0$ , so $x = 0$ [ $\mathrm{{\to}E}$ ], since a product of two real numbers is $0$ only if a factor is.

In either case $x = 0$ [ $\mathrm{\vee E}$ ].

The logical steps are $\mathrm{{\to}I}$ , $\mathrm{\vee E}$ , $\mathrm{\forall E}$ , $\mathrm{\neg E}$ , $\mathrm{{\to}E}$ (citing the second school fact, that a product is $0$ only if a factor is) and $\mathrm{\bot E}$ ; no classical rule is used. The classical content has moved into the school fact “ $x^2 > 0$ or $x^2 = 0$ ”, which rests on the trichotomy of the order, one of the axioms for the real numbers; Section 8.7 explains why that axiom is where the book makes its classical commitment.

Marking scheme. (10 points) - 3: (a) identifies $\mathrm{RAA}$ (face (iii)), with the reason: the assumption is a negation and the conclusion is positive. - 2: (b) splits on a disjunction that is justified (from $x^2 \ge 0$ , or from trichotomy). - 3: (b) closes the case $x^2 > 0$ by the instance $\varepsilon = x^2$ , a named clash, and $\mathrm{\bot E}$ . - 2: (b) settles the case $x^2 = 0$ with its reason and concludes “in either case”. A rewrite with $\mathrm{\neg I}$ and $\mathrm{\neg\neg E}$ in place of the case split earns the points of (b) except the 2 for the split, provided it names $\mathrm{\neg\neg E}$ as its one classical step. Fatal errors (0 for the step): calling (a) face (i) because the word “contradiction” appears; splitting on “ $x^2 > 0$ or $x^2 < 0$ ”, which does not exhaust.