3.3 From Argument to Derivation

Most searches in Sections 3.1 and 3.2 started from a sequent: its letters, its premises and its conclusion were given. Mathematics starts from a paragraph. Its premises are scattered among words such as “since” and “so”; some of them are not written at all; and its letters must be chosen. This section turns paragraphs into sequents and derives them. Then it goes the other way, and writes a proof beside the derivation it mirrors. A last page collects the sequents that searches keep needing.

3.3.1. One key for the section

Section 1.1, Exercise B5, fixed one key for an integer $n$ , and this section keeps it: $E$ : “ $n$ is even”, $P$ : “ $n$ is prime”, $T$ : “ $n$ is a multiple of $3$ ”, $G$ : “ $n > 10$ ” (Exercise (B5: One key, sixteen sentences, used later)). A prime is an integer greater than $1$ whose only positive divisors are $1$ and itself. Three facts about integers will serve as premises:

F1 $(P \wedge E) \to \neg G$ : an even prime is at most $10$ . The only even prime is $2$ , since an even $n > 2$ has the divisor $2$ .
F2 $(P \wedge T) \to \neg G$ : a prime multiple of $3$ is at most $10$ . The only one is $3$ , since a multiple of $3$ greater than $3$ has the divisor $3$ .
F3 $(E \wedge T) \to \neg P$ : no even multiple of $3$ is prime. Such an integer is a multiple of $6$ . A positive multiple of $6$ has the divisor $2$ and is greater than $2$ , and $0$ and the negative integers are not prime.

Each fact is true for every integer $n$ . An argument may use any of them as a premise, and a derivation lists the ones it uses.

A translation is checked by reading it back, letter by letter, as in Section 1.1: F3 reads back as “if $n$ is even and a multiple of $3$ , then $n$ is not prime”.

Quick check. On the key, translate “ $n$ is an odd prime greater than $10$ ”. Then read back $G \to \neg(P \wedge E)$ .

Solution. $(\neg E \wedge P) \wedge G$ . And $G \to \neg(P \wedge E)$ reads back as “if $n > 10$ , then $n$ is not an even prime”.

3.3.2. Extracting an argument

To turn a paragraph into a sequent, work through five steps.

Find the conclusion. Words such as so, hence, therefore, thus and it follows that introduce it.
Find the stated premises. Words such as since, because, for and given that introduce them. A supposition (“suppose …”, “let $n$ be …”) is a premise, or the assumption of a box.
Name the unstated facts. Wherever a step does not follow by a rule from the lines before it, write the fact that would make it follow, as an implication, and check that the fact is true. Supply the weakest fact that closes the gap: a stronger one may prove more than the paragraph claims, or be false. (Compare Section 1.3, Exercise B5 (d), where a missing implication was written and checked.)
Translate on a key, with Section 1.1’s phrase book.
Derive the sequent, or break it.

Steps 1–4 are reading. Step 5 is the rest of this book.

Example (An argument about a prime, extracted)

Extract the argument of this paragraph and derive it.

Let $n$ be an integer, and suppose that $n$ is a prime greater than $10$ . Then $n$ is odd, since the only even prime is $2$ . Nor is $n$ a multiple of $3$ , because the only prime that is a multiple of $3$ is $3$ itself. So $n$ is neither even nor a multiple of $3$ .

Solution. We take the five steps in order.

The conclusion follows “So”: $n$ is neither even nor a multiple of $3$ , that is, $\neg E \wedge \neg T$ (“neither … nor” in the phrase book).
The stated premise is the supposition, “ $n$ is a prime greater than $10$ ”: $P \wedge G$ , since “a prime greater than $10$ ” is a conjunction. “ $n$ is odd” and “nor is $n$ a multiple of $3$ ” are not premises. They are steps, each with a reason after “since” or “because”.
The reasons are facts about numbers, but not in a form a rule can use. “The only even prime is $2$ ” is used as “an even prime is not greater than $10$ ”, which is F1. The second reason is used as F2.
The sequent is $P \wedge G, \ (P \wedge E) \to \neg G, \ (P \wedge T) \to \neg G \vdash \neg E \wedge \neg T.$
We read the derivation off the goal. It is a conjunction of two negations: two $\mathrm{\neg I}$ boxes joined by $\mathrm{\wedge I}$ , as in Section 3.1.

In the first picture, the premise is taken apart and the two conjuncts stand as subgoals. In the second, each subgoal has its box, with goal $\bot$ .

P \wedge G

(P \wedge E) \to \neg G

(P \wedge T) \to \neg G

P

\mathrm{{\wedge}E}

G

\mathrm{{\wedge}E}

\vdots

\neg E

\vdots

\neg T

\neg E \wedge \neg T

\mathrm{{\wedge}I}

10, 15

P \wedge G

(P \wedge E) \to \neg G

(P \wedge T) \to \neg G

P

\mathrm{{\wedge}E}

G

\mathrm{{\wedge}E}

E

asm, for

\mathrm{{\neg}I}

\vdots

\bot

\neg E

\mathrm{{\neg}I}

6–9

T

asm, for

\mathrm{{\neg}I}

\vdots

\bot

\neg T

\mathrm{{\neg}I}

11–14

\neg E \wedge \neg T

\mathrm{{\wedge}I}

10, 15

Inside each box, the fact fires once the box’s assumption is joined to $P$ , and its conclusion $\neg G$ clashes with line 5.

P \wedge G

(P \wedge E) \to \neg G

(P \wedge T) \to \neg G

P

\mathrm{{\wedge}E}

G

\mathrm{{\wedge}E}

E

asm, for

\mathrm{{\neg}I}

P \wedge E

\mathrm{{\wedge}I}

4, 6

\neg G

\mathrm{{{\to}}E}

2, 7

\bot

\mathrm{{\neg}E}

5, 8

\neg E

\mathrm{{\neg}I}

6–9

T

asm, for

\mathrm{{\neg}I}

P \wedge T

\mathrm{{\wedge}I}

4, 11

\neg G

\mathrm{{{\to}}E}

3, 12

\bot

\mathrm{{\neg}E}

5, 13

\neg T

\mathrm{{\neg}I}

11–14

\neg E \wedge \neg T

\mathrm{{\wedge}I}

10, 15

Lines 4–5 need nothing new, so they are written before the boxes (Section 3.1). Had the supposition been kept as a supposition, the claim would be $(P \wedge E) \to \neg G, \ (P \wedge T) \to \neg G \vdash (P \wedge G) \to (\neg E \wedge \neg T)$ : the same lines inside one more box, closed by $\mathrm{{\to}I}$ .

The argument can also be drawn as a map: each statement a dot, each step an arrow into what it gives. The unstated facts are the dots nobody wrote. The map shows what supports what; it is not a derivation, and it leaves out the boxes.

Quick check. Which line of the derivation in Example (An argument about a prime, extracted) is the paragraph’s sentence “Then $n$ is odd”, and which lines does the paragraph leave silent?

Solution. Line 10. The paragraph is silent on lines 4–5 and on the box, lines 6–9, that shows it, apart from the reason F1 behind line 8.

Warning (Not allowed: extracting an argument). Each entry names the step of the method it breaks.

“Writing ‘ $n$ is odd’ among the premises”: a step taken as a premise. The derivation then proves nothing about whether $n$ is odd (step 2).
“Reading ‘ $n$ is odd, since $n$ is a prime greater than $10$ ’ with ‘ $n$ is odd’ as the premise”: since introduces the premise, not the conclusion (steps 1–2).
“Supplying ‘every prime is odd’ for the first step”: the supplied fact must be true, and this one fails at $n = 2$ (step 3).
“Supplying $\neg E \wedge \neg T$ itself as the unstated fact”: the derivation is legal and proves nothing. Supply the weakest fact that closes the gap (step 3).
“Translating ‘ $n$ is a prime greater than $10$ ’ as $P \to G$ ”: a noun with an adjective is a conjunction, $P \wedge G$ , as “an even prime” was $E \wedge P$ in Section 1.1 (step 4).

3.3.3. Two columns

Now the other direction: a proof is written, and its derivation is wanted. Write the proof in the left column and the derivation in the right, each sentence on the row of the lines it says. A line that no sentence says is a silent step. A sentence that matches no line is a gap in the proof, or a step this book’s rules cannot take.

Example (A proof and its derivation, side by side)

Let $n$ be an integer. Claim: if $n$ is even and prime, then $n$ is not a multiple of $3$ .

Proof. Suppose $n$ is even and prime. If $n$ were a multiple of $3$ , it would be an even multiple of $3$ , and no even multiple of $3$ is prime; but $n$ is prime. So $n$ is not a multiple of $3$ .

Write the derivation the proof mirrors, in two columns.

Solution. The proof uses one fact, F3, and the claim is an implication. The sequent is $(E \wedge T) \to \neg P \vdash (E \wedge P) \to \neg T$ . The goal gives a box on $E \wedge P$ (left). Inside it the goal $\neg T$ is a negation, so a $\mathrm{\neg I}$ box on $T$ opens, after the assumption has been taken apart (right).

(E \wedge T) \to \neg P

E \wedge P

asm, for

\mathrm{{{\to}}I}

\vdots

\neg T

(E \wedge P) \to \neg T

\mathrm{{{\to}}I}

2–9

(E \wedge T) \to \neg P

E \wedge P

asm, for

\mathrm{{{\to}}I}

E

\mathrm{{\wedge}E}

P

\mathrm{{\wedge}E}

T

asm, for

\mathrm{{\neg}I}

\vdots

\bot

\neg T

\mathrm{{\neg}I}

5–8

(E \wedge P) \to \neg T

\mathrm{{{\to}}I}

2–9

The two columns finish the derivation.

The proof	The derivation
“Suppose $n$ is even and prime.”	2 $E \wedge P$ , asm, for $\mathrm{{\to}I}$
(silent)	3 $E$ , 4 $P$ , $\mathrm{\wedge E}$ 2
“If $n$ were a multiple of $3$ ,”	5 $T$ , asm, for $\mathrm{\neg I}$
“it would be an even multiple of $3$ ,”	6 $E \wedge T$ , $\mathrm{\wedge I}$ 3, 5
“and no even multiple of $3$ is prime;”	1 $(E \wedge T) \to \neg P$ , F3; 7 $\neg P$ , $\mathrm{{\to}E}$ 1, 6
“but $n$ is prime.”	8 $\bot$ , $\mathrm{\neg E}$ 4, 7
“So $n$ is not a multiple of $3$ .”	9 $\neg T$ , $\mathrm{\neg I}$ 5–8
(the claim)	10 $(E \wedge P) \to \neg T$ , $\mathrm{{\to}I}$ 2–9

The finished derivation, read down the right column:

(E \wedge T) \to \neg P

E \wedge P

asm, for

\mathrm{{{\to}}I}

E

\mathrm{{\wedge}E}

P

\mathrm{{\wedge}E}

T

asm, for

\mathrm{{\neg}I}

E \wedge T

\mathrm{{\wedge}I}

3, 5

\neg P

\mathrm{{{\to}}E}

1, 6

\bot

\mathrm{{\neg}E}

4, 7

\neg T

\mathrm{{\neg}I}

5–8

(E \wedge P) \to \neg T

\mathrm{{{\to}}I}

2–9

The proof says lines 2 and 5–9, and line 1 only inside a clause. It is silent on lines 3–4, taking the conjunction apart, and on line 10, since closing the outer box is the claim itself. Its “Suppose” is line 2’s “asm, for $\mathrm{{\to}I}$ ”, and its “If $n$ were” is line 5’s “asm, for $\mathrm{\neg I}$ ”. The proof hides the fact F3 in a clause; the derivation lists it.

Quick check. If the claim in Example (A proof and its derivation, side by side) were “if $n$ is even and prime, then $n$ is at most $10$ ”, which fact would replace F3, and what would happen to the box of line 5?

Solution. F1 replaces F3. The box of line 5 disappears: the goal $\neg G$ is F1’s conclusion, so after $\mathrm{\wedge E}$ and $\mathrm{\wedge I}$ give $P \wedge E$ , one $\mathrm{{\to}E}$ line reaches it.

3.3.4. A library of standard sequents

Chapters 1 and 2 and Section 3.2 proved sequents that searches keep needing. Here they are grouped by what they are for: a searcher with a resource or a goal of a given shape looks up its row. Each row is a derived rule (Definition 2.3.1). It is applied to whole available lines, never to a part of a line, and it is cited by the name in its middle column. “The rules in one place” in Section 3.1 lists the primitive rules and most of these derived rules on one card; this page regroups the derived rules, with those of Section 3.2, by use. The last group is different: it holds facts about derivations, which change the task rather than add a line.

Sequent	In a justification	Proved in
To use an implication
$P \to Q, \ \neg Q \vdash \neg P$	$\mathrm{MT}$	Proposition 2.3.1
$P \to Q, \ Q \to R \vdash P \to R$	(implication is transitive)	Proposition 1.4.1
$(P \wedge Q) \to R \dashv\vdash P \to (Q \to R)$	(curry)	Proposition 1.4.2
$P \to Q \vdash \neg P \vee Q$	(implication as disjunction)	Proposition 2.5.6 (b)
To use a disjunction
$P \vee Q, \ \neg P \vdash Q$ ; $P \vee Q, \ \neg Q \vdash P$	$\mathrm{DS}$	Proposition 2.3.4; Exercise (B1: The other disjunctive syllogism, used later) (a)
$(P \to R) \wedge (Q \to R) \dashv\vdash (P \vee Q) \to R$	(cases on a hypothesis)	Example (Cases on a hypothesis are two implications); Example (A disjunctive hypothesis splits into two implications)
$(P \to R) \wedge (Q \to S), \ P \vee Q \vdash R \vee S$	(constructive dilemma)	Example (Constructive dilemma)
$(P \to R) \wedge (Q \to S), \ \neg R \vee \neg S \vdash \neg P \vee \neg Q$	(destructive dilemma)	Exercise (B4: Dilemmas as derived rules, used later) (b)
$\neg(P \wedge Q) \vdash P \to \neg Q$	(modus ponendo tollens)	Exercise (B4: Dilemmas as derived rules, used later) (c)
To use a negation or a clash
$P, \ \neg P \vdash Q$	(ex falso)	Proposition 2.1.1
$\neg P \vdash P \to Q$	VI	Proposition 2.1.2
$\neg\neg P \vdash P$	$\mathrm{\neg\neg E}$	Proposition 2.5.1 (b)
$\neg(P \vee Q) \vdash \neg P \wedge \neg Q$ ; $\neg(P \wedge Q) \vdash \neg P \vee \neg Q$	$\mathrm{DM}$	Proposition 2.5.5 (a), (d)
To reach a negation
$P \to Q \vdash \neg Q \to \neg P$	$\mathrm{CP}$	Proposition 2.3.2
$\vdash (P \to (Q \wedge \neg Q)) \to \neg P$	(implies a contradiction)	Example (A statement that implies a contradiction)
$\neg P \wedge \neg Q \vdash \neg(P \vee Q)$ ; $\neg P \vee \neg Q \vdash \neg(P \wedge Q)$	$\mathrm{DM}$	Proposition 2.5.5 (b), (c)
$P \vdash \neg\neg P$	$\mathrm{\neg\neg I}$	Proposition 2.5.1 (a)
To reach an implication
$\neg P \vee Q \vdash P \to Q$	(implication as disjunction)	Proposition 2.5.6 (a)
$\neg Q \to \neg P \vdash P \to Q$	( $\mathrm{CP}$ , converse)	Proposition 2.5.2
To reach a disjunction
$\vdash P \vee \neg P$	$\mathrm{LEM}$	Proposition 2.5.3
$(P \wedge \neg Q) \to R \dashv\vdash P \to (Q \vee R)$	(refute one side)	Example (Proving a disjunction by refuting one side)
To rearrange
$P \wedge Q \vdash Q \wedge P$ ; $P \vee Q \vdash Q \vee P$	(and commutes); (or commutes)	Proposition 1.2.1; Example (First derivations with “or”)
$(P \wedge Q) \wedge R \vdash P \wedge (Q \wedge R)$ ; $P \vee (Q \vee R) \vdash (P \vee Q) \vee R$	(and regroups); (or regroups)	Proposition 1.2.2; Example (Regrouping a disjunction)
$P \wedge (Q \vee R) \dashv\vdash (P \wedge Q) \vee (P \wedge R)$	(distributivity)	Proposition 1.6.1
$P \leftrightarrow Q \vdash Q \leftrightarrow P$	(iff symmetric)	Example (An iff read both ways)
$P \leftrightarrow Q \dashv\vdash (P \to Q) \wedge (Q \to P)$	(iff as two implications)	Proposition 2.4.1
$P \to Q, \ Q \to R, \ R \to P \vdash P \leftrightarrow Q$	(equivalence cycle)	Proposition 2.4.6
To change the task (facts about derivations, not lines)
more premises never hurt; a derived statement may be used as a premise	(weakening, cut)	Lemma 2.3.3
$\Gamma \vdash \varphi$ exactly when $\Gamma, \neg\varphi$ is inconsistent	—	Proposition 3.2.2
an inconsistent list derives every statement	—	Proposition 3.2.1

Rows proved in exercises (the second form of $\mathrm{DS}$ ; the destructive dilemma and modus ponendo tollens rows, Exercise (B4: Dilemmas as derived rules, used later) (b), (c)) may be used by exercises, as in Section 3.1; the text’s own derivations use only rows proved in the text.

Quick check. Which row would you look up first? (i) The goal is $\neg(P \vee Q)$ . (ii) A resource is $\neg(P \wedge Q)$ , and the goal is $\neg P \vee \neg Q$ . (iii) The resources include $P \to Q$ and $\neg Q$ .

Solution.

(i) $\mathrm{DM}$ (b), under “To reach a negation”. (ii) $\mathrm{DM}$ (d), which gives the goal in one line. (iii) $\mathrm{MT}$ .

Remark (Looking ahead). We show that something is derivable by exhibiting a derivation; how could we ever show that something is not? Chapter 4 gives each statement a truth value and proves that the rules never lead from true premises to a false conclusion. Then one choice of truth values, such as $P$ false and $Q$ true for the failed search of Section 3.1, proves that no derivation exists.

3.3.5. Exercises

A. Check your understanding

Exercise (A1)

(a) In “Since $n^2$ is even, $n$ is even”, which is the premise and which the conclusion?
(b) Find the conclusion: “ $n$ is odd, for $n$ is prime and greater than $10$ .”
(c) Name the unstated fact: “ $n$ is a multiple of $6$ , so $n$ is even.”
(d) On the key of this section, translate “ $n$ is an odd prime at most $10$ .”
(e) In Example (A proof and its derivation, side by side), which sentence of the proof is line 5, and what does line 5’s annotation read?

Solution.

(a) The premise is “ $n^2$ is even”; the conclusion is “ $n$ is even”.
(b) “ $n$ is odd”. For introduces the premise.
(c) Every multiple of $6$ is even: if $6 \mid n$ , then $2 \mid n$ .
(d) $(\neg E \wedge P) \wedge \neg G$ .
(e) “If $n$ were a multiple of $3$ ”; the annotation reads “asm, for $\mathrm{\neg I}$ ”.

B. Practice

Exercise (B1: Extract, then derive)

For each paragraph, find the conclusion, the stated premises and any unstated fact; choose letters; write the sequent; derive it.

(a) Let $x$ be a real number with $x^2 \le x$ . If $x$ were greater than $1$ , then $x^2 = x \cdot x$ would be greater than $x$ . If $x$ were negative, $x^2$ would be positive, hence greater than $x$ . So $x$ is at least $0$ and at most $1$ .
(b) Let $n$ be an integer. Since $n^2$ is odd, $n$ is odd.
(c) Let $a$ and $b$ be real numbers with $ab = 0$ . If $a \ne 0$ , we may divide by $a$ and find $b = 0$ . So $a = 0$ or $b = 0$ .

Solution.

(a) Take $A$ : “ $x > 1$ ”, $B$ : “ $x < 0$ ”, $C$ : “ $x^2 > x$ ”. The paragraph states two facts, each with its reason: $A \to C$ and $B \to C$ . The premise “ $x^2 \le x$ ” is $\neg C$ , by the convention of Section 2.1. The conclusion “at least $0$ and at most $1$ ” is $\neg B \wedge \neg A$ , by the same convention. The sequent is $A \to C, \ B \to C, \ \neg C \vdash \neg B \wedge \neg A$ .
1 $A \to C$
2 $B \to C$
3 $\neg C$
4 $\neg A$ $\mathrm{MT}$ 1, 3
5 $\neg B$ $\mathrm{MT}$ 2, 3
6 $\neg B \wedge \neg A$ $\mathrm{{\wedge}I}$ 5, 4

Nothing is unstated here except the order convention.
(b) Take $E$ : “ $n$ is even”, $S$ : “ $n^2$ is even”. The premise is $\neg S$ and the conclusion $\neg E$ . The unstated fact is $E \to S$ , “the square of an even integer is even”, which is true since $(2k)^2 = 4k^2 = 2(2k^2)$ . The sequent is $E \to S, \ \neg S \vdash \neg E$ .
1 $E \to S$
2 $\neg S$
3 $\neg E$ $\mathrm{MT}$ 1, 2

The tempting wrong supply is “the square of an odd integer is odd”, $\neg E \to \neg S$ . It is true, since $(2k+1)^2 = 2(2k^2+2k)+1$ , but with the premise $\neg S$ it gives nothing: concluding $\neg E$ from it would be affirming the consequent (Section 1.3).
(c) Take $A$ : “ $a = 0$ ”, $B$ : “ $b = 0$ ”, $Z$ : “ $ab = 0$ ”. The stated fact is $(Z \wedge \neg A) \to B$ , dividing by $a$ : $b = a^{-1}(ab) = 0$ . The premise is $Z$ and the conclusion $A \vee B$ . Neither side of the goal is in hand, so we split on $A$ by $\mathrm{LEM}$ , Section 3.1’s step 5, as in Example (Proving a disjunction by refuting one side).

(Z \wedge \neg A) \to B

Z

A \vee \neg A

\mathrm{LEM}

A

asm, for

\mathrm{{\vee}E}

A \vee B

\mathrm{{\vee}I}

\neg A

asm, for

\mathrm{{\vee}E}

Z \wedge \neg A

\mathrm{{\wedge}I}

2, 6

B

\mathrm{{{\to}}E}

1, 7

A \vee B

\mathrm{{\vee}I}

A \vee B

\mathrm{{\vee}E}

3, 4–5, 6–9

Exercise (B2: Two columns)

Let $n$ be an integer. Claim: if $n$ is prime and $n > 10$ , then $n$ is not a multiple of $6$ .

Proof. Suppose $n$ is prime and $n > 10$ . If $n$ were a multiple of $6$ , it would be an even multiple of $3$ , and no even multiple of $3$ is prime; but $n$ is prime. So $n$ is not a multiple of $6$ .

(a) On the key, “ $n$ is a multiple of $6$ ” is $E \wedge T$ . The derivation the proof mirrors has reached the stage below. Name the move, then complete it.

1 $(E \wedge T) \to \neg P$
2 $P \wedge G$ asm, for $\mathrm{{{\to}}I}$
$\vdots$
7 $\neg (E \wedge T)$
8 $(P \wedge G) \to \neg (E \wedge T)$ $\mathrm{{{\to}}I}$ 2–7
(b) Write the two-column table.
(c) Which hypothesis does the derivation never cite? What claim does that show, and is it true?

Solution.

(a) The goal $\neg(E \wedge T)$ is a negation, so step 2 of the method opens a $\mathrm{\neg I}$ box on $E \wedge T$ . F3 fires on it, and the clash partner $P$ comes from line 2.
1 $(E \wedge T) \to \neg P$
2 $P \wedge G$ asm, for $\mathrm{{{\to}}I}$
3 $P$ $\mathrm{{\wedge}E}$ 2
4 $E \wedge T$ asm, for $\mathrm{{\neg}I}$
5 $\neg P$ $\mathrm{{{\to}}E}$ 1, 4
6 $\bot$ $\mathrm{{\neg}E}$ 3, 5
7 $\neg (E \wedge T)$ $\mathrm{{\neg}I}$ 4–6
8 $(P \wedge G) \to \neg (E \wedge T)$ $\mathrm{{{\to}}I}$ 2–7

(b) The two columns:

The proof	The derivation
“Suppose $n$ is prime and $n > 10$ .”	2
(silent)	3
“If $n$ were a multiple of $6$ ,”	4
“it would be an even multiple of $3$ , and no even multiple of $3$ is prime;”	1 (F3), 5
“but $n$ is prime.”	6
“So $n$ is not a multiple of $6$ .”	7
(the claim)	8

Line 4 already is $E \wedge T$ , so “an even multiple of $3$ ” is a rereading, not a step.

(c) $G$ , that is, $n > 10$ , is never cited: no line uses it. The same lines with $P$ in place of $P \wedge G$ as the assumption of the outer box (line 3 dropped), closed by $\mathrm{{\to}I}$ , would derive $(E \wedge T) \to \neg P \vdash P \to \neg(E \wedge T)$ : no prime is a multiple of $6$ . That is true for every integer, by F3. The hypothesis $n > 10$ was idle.

Exercise (B3: Fifteen items)

Items 1–5: derive each sequent, using a row of the library where it shortens the derivation, and name the row; their letters are free, not the key. Items 6–10: translate on the key, using the facts F1–F3 as premises where needed, and derive. Items 11–15: derive or break, as in Example (Two claims, one connective apart). The facts may be used as premises. A break is an integer $n$ at which the premises are true and the conclusion false; since F1–F3 hold at every $n$ , such an $n$ makes the whole counterexample set true.

Derive, with the library.

1. $\neg(P \vee Q) \vdash P \to R$ .
2. $P \vee Q, \ P \to R, \ \neg R \vdash Q \wedge \neg P$ .
3. $\neg(P \wedge \neg Q) \vdash P \to Q$ .
4. $(P \vee Q) \to R \vdash \neg R \to (\neg P \wedge \neg Q)$ .
5. $\neg P \to Q, \ \neg Q \vdash P \wedge (\neg Q \vee R)$ .

Translate on the key, then derive.

6. $n$ is an even multiple of $3$ ; so $n$ is not prime, and $n$ is not a prime greater than $10$ .
7. $n$ is a prime at most $10$ , or $n$ is odd; so if $n$ is even, $n$ is at most $10$ .
8. $n$ is a prime multiple of $3$ ; so $n$ is at most $10$ , and $n$ is odd.
9. $n$ is prime; $n$ is not a multiple of $3$ or $n$ is at most $10$ ; and $n$ is a multiple of $3$ . So $n$ is at most $10$ .
10. If $n$ is greater than $10$ , then $n$ is not an even prime.

Derive or break.

11. $n$ is even but not a multiple of $3$ ; so $n$ is not prime.
12. $n$ is an even prime; so $n$ is at most $10$ .
13. $n$ is odd and greater than $10$ ; so $n$ is prime.
14. $n$ is odd; so $n$ is not an even prime.
15. $n$ is not prime; so $n$ is even or a multiple of $3$ .

Solution. 1. $\mathrm{DM}$ (a), then VI.

\neg (P \vee Q)

\neg P \wedge \neg Q

\mathrm{DM}

\neg P

\mathrm{{\wedge}E}

P \to R

VI 3

2. $\mathrm{MT}$ , then $\mathrm{DS}$ .

P \vee Q

P \to R

\neg R

\neg P

\mathrm{MT}

2, 3

Q

\mathrm{DS}

1, 4

Q \wedge \neg P

\mathrm{{\wedge}I}

5, 4

3. Modus ponendo tollens, with $\neg Q$ for $Q$ , turns the premise into $P \to \neg\neg Q$ . Inside a box on $P$ , $\mathrm{{\to}E}$ and $\mathrm{\neg\neg E}$ reach $Q$ .

\neg (P \wedge \neg Q)

P \to \neg\neg Q

modus ponendo tollens 1

P

asm, for

\mathrm{{{\to}}I}

\neg\neg Q

\mathrm{{{\to}}E}

2, 3

Q

\mathrm{{\neg\neg}E}

P \to Q

\mathrm{{{\to}}I}

3–5

Without the library, the goal $Q$ inside the box is a letter, so $\mathrm{RAA}$ on $\neg Q$ , which clashes with the premise once $P \wedge \neg Q$ is built: seven lines.

\neg (P \wedge \neg Q)

P

asm, for

\mathrm{{{\to}}I}

\neg Q

asm, for

\mathrm{RAA}

P \wedge \neg Q

\mathrm{{\wedge}I}

2, 3

\bot

\mathrm{{\neg}E}

4, 1

Q

\mathrm{RAA}

3–5

P \to Q

\mathrm{{{\to}}I}

2–6

The other library route ( $\mathrm{DM}$ (d) on the premise, then $\mathrm{\neg\neg I}$ , $\mathrm{DS}$ and $\mathrm{\neg\neg E}$ inside the box) is no shorter than the seven lines.

4. $\mathrm{MT}$ , then $\mathrm{DM}$ (a), inside one box.

(P \vee Q) \to R

\neg R

asm, for

\mathrm{{{\to}}I}

\neg (P \vee Q)

\mathrm{MT}

1, 2

\neg P \wedge \neg Q

\mathrm{DM}

\neg R \to (\neg P \wedge \neg Q)

\mathrm{{{\to}}I}

2–4

5. $\mathrm{MT}$ , then $\mathrm{\neg\neg E}$ .

\neg P \to Q

\neg Q

\neg\neg P

\mathrm{MT}

1, 2

P

\mathrm{{\neg\neg}E}

\neg Q \vee R

\mathrm{{\vee}I}

P \wedge (\neg Q \vee R)

\mathrm{{\wedge}I}

4, 5

6. $E \wedge T, \ (E \wedge T) \to \neg P \vdash \neg P \wedge \neg(P \wedge G)$ , with F3.

E \wedge T

(E \wedge T) \to \neg P

\neg P

\mathrm{{{\to}}E}

2, 1

P \wedge G

asm, for

\mathrm{{\neg}I}

P

\mathrm{{\wedge}E}

\bot

\mathrm{{\neg}E}

5, 3

\neg (P \wedge G)

\mathrm{{\neg}I}

4–6

\neg P \wedge \neg (P \wedge G)

\mathrm{{\wedge}I}

3, 7

7. $(P \wedge \neg G) \vee \neg E \vdash E \to \neg G$ , with no fact needed.

(P \wedge \neg G) \vee \neg E

E

asm, for

\mathrm{{{\to}}I}

P \wedge \neg G

asm, for

\mathrm{{\vee}E}

\neg G

\mathrm{{\wedge}E}

\neg E

asm, for

\mathrm{{\vee}E}

\bot

\mathrm{{\neg}E}

2, 5

\neg G

\mathrm{{\bot}E}

\neg G

\mathrm{{\vee}E}

1, 3–4, 5–7

E \to \neg G

\mathrm{{{\to}}I}

2–8

8. $P \wedge T, \ (P \wedge T) \to \neg G, \ (E \wedge T) \to \neg P \vdash \neg G \wedge \neg E$ , with F2 and F3.

P \wedge T

(P \wedge T) \to \neg G

(E \wedge T) \to \neg P

\neg G

\mathrm{{{\to}}E}

2, 1

P

\mathrm{{\wedge}E}

T

\mathrm{{\wedge}E}

E

asm, for

\mathrm{{\neg}I}

E \wedge T

\mathrm{{\wedge}I}

7, 6

\neg P

\mathrm{{{\to}}E}

3, 8

\bot

\mathrm{{\neg}E}

5, 9

\neg E

\mathrm{{\neg}I}

7–10

\neg G \wedge \neg E

\mathrm{{\wedge}I}

4, 11

9. $P, \ \neg T \vee \neg G, \ T \vdash \neg G$ .

P

\neg T \vee \neg G

T

\neg\neg T

\mathrm{{\neg\neg}I}

\neg G

\mathrm{DS}

2, 4

The premise $P$ is not needed.

10. $(P \wedge E) \to \neg G \vdash G \to \neg(P \wedge E)$ , with F1.

(P \wedge E) \to \neg G

G

asm, for

\mathrm{{{\to}}I}

P \wedge E

asm, for

\mathrm{{\neg}I}

\neg G

\mathrm{{{\to}}E}

1, 3

\bot

\mathrm{{\neg}E}

2, 4

\neg (P \wedge E)

\mathrm{{\neg}I}

3–5

G \to \neg (P \wedge E)

\mathrm{{{\to}}I}

2–6

With the library, lines 3–6 shrink to two: 3 $\neg\neg G$ , $\mathrm{\neg\neg I}$ 2; 4 $\neg(P \wedge E)$ , $\mathrm{MT}$ 1, 3.

11. Breaks. The claim is $E \wedge \neg T \vdash \neg P$ , and at $n = 2$ the integer is even, not a multiple of $3$ , and prime.

12. Derives: $P \wedge E, \ (P \wedge E) \to \neg G \vdash \neg G$ , with F1.

P \wedge E

(P \wedge E) \to \neg G

\neg G

\mathrm{{{\to}}E}

2, 1

13. Breaks. The claim is $\neg E \wedge G \vdash P$ , and at $n = 15$ the integer is odd, greater than $10$ , and not prime.

14. Derives: $\neg E \vdash \neg(P \wedge E)$ . No fact is needed.

\neg E

P \wedge E

asm, for

\mathrm{{\neg}I}

E

\mathrm{{\wedge}E}

\bot

\mathrm{{\neg}E}

3, 1

\neg (P \wedge E)

\mathrm{{\neg}I}

2–4

15. Breaks. The claim is $\neg P \vdash E \vee T$ , and at $n = 25$ the integer is not prime, odd, and not a multiple of $3$ .

Items 11 and 12, and items 13 and 14, pair a break with a derivation on nearby words; item 15 tries to go back from “not prime” to “even or a multiple of $3$ ”, which F3 does not give, and fails.

Exercise (B4: Put the proof in order)

Let $a$ and $b$ be real numbers. Claim: if $a + b > 2$ , then $a > 1$ or $b > 1$ .

(i) This contradicts $a + b > 2$ .
(ii) Suppose $a + b > 2$ .
(iii) Then $a > 1$ , since $a + b > 2$ .
(iv) Adding, $a + b \le 2$ .
(v) Hence $a > 1$ or $b > 1$ .
(vi) Suppose, for a contradiction, that neither $a > 1$ nor $b > 1$ .
(vii) Suppose $a > 1$ or $b > 1$ .
(viii) Then $a \le 1$ and $b \le 1$ .

(a) Put six of these sentences in an order that proves the claim; two do not belong.
(b) Match each sentence of your order to a line of the derivation below, with $A$ : “ $a > 1$ ”, $B$ : “ $b > 1$ ”, $S$ : “ $a + b > 2$ ”.

(\neg A \wedge \neg B) \to \neg S

S

asm, for

\mathrm{{{\to}}I}

\neg (A \vee B)

asm, for

\mathrm{RAA}

\neg A \wedge \neg B

\mathrm{DM}

\neg S

\mathrm{{{\to}}E}

1, 4

\bot

\mathrm{{\neg}E}

2, 5

A \vee B

\mathrm{RAA}

3–6

S \to (A \vee B)

\mathrm{{{\to}}I}

2–7

Solution.

(a) (ii), (vi), (viii), (iv), (i), (v). No other order is admissible: the supposition (ii) must open first, since the claim is an implication, the $\mathrm{RAA}$ supposition (vi) inside it, and each later sentence uses the one before it. The two distractors:
- - (iii) does not follow: $a = 0$ , $b = 3$ has $a + b > 2$ and $a \le 1$ .
- - (vii) assumes the conclusion, a box opened on the goal (Section 3.1’s warning “Do not assume what you want to prove”).
(b)
- (ii) is line 2, “asm, for $\mathrm{{\to}I}$ ”. (vi) is line 3, “asm, for $\mathrm{RAA}$ ”. (viii) is line 4, by $\mathrm{DM}$ and the order convention of Section 2.1 ( $\neg(a > 1)$ is $a \le 1$ ). (iv) is line 5, with the fact on line 1: adding the two inequalities. (i) is line 6, and (v) is line 7. The claim is line 8. The fact on line 1 is the one step of school algebra: $a \le 1$ and $b \le 1$ give $a + b \le 2$ .

C. Going deeper

Exercise (C1: Exit check: from a paragraph to a derivation)

Let $n$ be an integer greater than $10$ , and suppose $n$ is even or a multiple of $3$ . Then $n$ is not prime. Indeed, suppose $n$ were prime. If $n$ is even, $n$ is an even prime, and every even prime is at most $10$ . If $n$ is a multiple of $3$ , $n$ is a prime multiple of $3$ , and every such number is at most $10$ . Either way $n$ is at most $10$ , which is false. So $n$ is not prime.

(a) Name the conclusion, the stated premises, and the facts the paragraph gives as reasons, each on the key.
(b) Write the sequent.
(c) Derive it.
(d) Write the two-column table.
(e) Is the premise “ $n > 10$ ” needed? Break the claim without it.

Solution.

(a) The conclusion is $\neg P$ . The premises are $G$ and $E \vee T$ . The facts are F1 (“every even prime is at most $10$ ”) and F2.
(b) $G, \ E \vee T, \ (P \wedge E) \to \neg G, \ (P \wedge T) \to \neg G \vdash \neg P$ .
(c) The goal is a negation: a $\mathrm{\neg I}$ box on $P$ . Inside it, the resource $E \vee T$ is split, each case reaching $\neg G$ by its fact, and $\neg G$ clashes with $G$ outside the cases.

1 $G$
2 $E \vee T$
3 $(P \wedge E) \to \neg G$
4 $(P \wedge T) \to \neg G$
5 $P$ asm, for $\mathrm{{\neg}I}$
6 $E$ asm, for $\mathrm{{\vee}E}$
7 $P \wedge E$ $\mathrm{{\wedge}I}$ 5, 6
8 $\neg G$ $\mathrm{{{\to}}E}$ 3, 7
9 $T$ asm, for $\mathrm{{\vee}E}$
10 $P \wedge T$ $\mathrm{{\wedge}I}$ 5, 9
11 $\neg G$ $\mathrm{{{\to}}E}$ 4, 10
12 $\neg G$ $\mathrm{{\vee}E}$ 2, 6–8, 9–11
13 $\bot$ $\mathrm{{\neg}E}$ 1, 12
14 $\neg P$ $\mathrm{{\neg}I}$ 5–13

(d) The two columns:

The proof	The derivation
“Let $n$ … greater than $10$ , and suppose $n$ is even or a multiple of $3$ .”	1, 2
“Then $n$ is not prime.”	the goal, line 14
“suppose $n$ were prime.”	5 (asm, for $\mathrm{\neg I}$ )
“If $n$ is even, … at most $10$ .”	6–8, with 3
“If $n$ is a multiple of $3$ , … at most $10$ .”	9–11, with 4
“Either way $n$ is at most $10$ ,”	12
“which is false.”	13
“So $n$ is not prime.”	14

(e) It is needed. Without $G$ , the claim $E \vee T, \ (P \wedge E) \to \neg G, \ (P \wedge T) \to \neg G \vdash \neg P$ breaks at $n = 2$ : $2$ is even, so $E \vee T$ holds; F1 and F2 hold, as at every $n$ ; and $2$ is prime, so the negated conclusion $\neg\neg P$ is true too.

Marking scheme. (10 points)

2: (a)–(b), the sequent, with F1 and F2 named as the facts given as reasons, in implication form.
3: (c), a correct derivation; the model has the $\mathrm{\neg I}$ box on $P$ , the two cases both ending in $\neg G$ , and the clash with $G$ outside the cases. In (d), the table is marked against the reader’s own derivation.
2: (d), every sentence placed, the two “suppose”s matched to their annotations.
3: (e), “needed”, with a break that makes every member of the new counterexample set true.

Fatal errors (0 for the step): $\neg P$ taken as a premise; the cases of $\mathrm{\vee E}$ ending in different statements; a “break” in (e) at an $n$ where a premise fails. A derivation that splits $E \vee T$ first and opens a $\mathrm{\neg I}$ box in each case earns full marks for (c).

Exercise (C2: Challenge: A statement that promises anything)

(a) Derive $C \leftrightarrow (C \to Q) \vdash Q$ .
(b) Let $Q$ be “ $0 = 1$ ”. What does (a) say about a statement $C$ that is equivalent to “if $C$ , then $0 = 1$ ”?
(c) Which rules does your derivation use? Compare Lemma 2.4.2.

Solution.

(a) The premise gives nothing until one side of the iff is on a line. The side $C \to Q$ is an implication, and its box can use the premise on its own assumption.
1 $C \leftrightarrow (C \to Q)$
2 $C$ asm, for $\mathrm{{{\to}}I}$
3 $C \to Q$ $\mathrm{{{\leftrightarrow}}E}$ 1, 2
4 $Q$ $\mathrm{{{\to}}E}$ 3, 2
5 $C \to Q$ $\mathrm{{{\to}}I}$ 2–4
6 $C$ $\mathrm{{{\leftrightarrow}}E}$ 1, 5
7 $C \to Q$ $\mathrm{{{\leftrightarrow}}E}$ 1, 6
8 $Q$ $\mathrm{{{\to}}E}$ 7, 6

The shorter ending 7 $Q$ , $\mathrm{{\to}E}$ 5, 6 is a detour: line 5 was built by $\mathrm{{\to}I}$ and is taken apart at once. Cutting it costs a line here, because line 5 is cited again at line 6, so it stays. This is the case Section 3.1 names: cutting a detour need not shorten a derivation, and the rule is advice, not a theorem.
(b) Read as an argument, the derivation proves $0 = 1$ from the condition on $C$ ; since $0 = 1$ is false, no statement can meet the condition. In this chapter’s words, the list $C \leftrightarrow (C \to Q), \ \neg Q$ is inconsistent: add $\neg Q$ as a second premise (line 2, the later lines shifting down by one) and a last line $\bot$ , $\mathrm{\neg E}$ , citing $Q$ and that premise.
(c) Only $\mathrm{{\leftrightarrow}E}$ , $\mathrm{{\to}I}$ and $\mathrm{{\to}E}$ : no rule for $\neg$ or $\bot$ , and no $\mathrm{RAA}$ . Lemma 2.4.2 shows that no statement is equivalent to its own negation. This shows more: any statement equivalent to “if $C$ , then $Q$ ” forces $Q$ , whatever $Q$ is. So when $Q$ is refutable, as “ $0 = 1$ ” is, no statement is equivalent to “if $C$ , then $Q$ ”, and the argument uses no “not”. (Taking $Q$ to be $\bot$ gives back Lemma 2.4.2, since $\neg C$ and $C \to \bot$ are interderivable (Section 2.2).) The trouble is self-reference, not negation. This is known as Curry’s paradox, after the logician whose name is also on the law Proposition 1.4.2. Section 5.6 meets the same shape with “for every”, in the barber and Russell’s theorem.

Marking scheme. (10 points)

4: (a), any correct derivation; the model has the box on $C$ (lines 2–4, with the assumption $C$ cited twice), $C$ recovered outside it by $\mathrm{{\leftrightarrow}E}$ (line 6), and $Q$ reached outside every box. The 7-line ending $\mathrm{{\to}E}$ 5, 6 earns full marks; the detour remark is not required.
3: (b), the conclusion that no statement meets the condition, with the inconsistency.
3: (c), the rules of the reader’s own derivation named correctly, and the point that a derivation using only $\mathrm{{\leftrightarrow}E}$ , $\mathrm{{\to}I}$ and $\mathrm{{\to}E}$ exists (the model), so no negation rule is needed.

Fatal error (0 for (a)): $Q$ obtained inside the box and carried out of it.

R. Review

Exercise (R1)

For real numbers $a$ and $b$ , let $\max(a, b) \mathrel{:=} a$ and $\min(a, b) \mathrel{:=} b$ if $a \ge b$ , and $\max(a, b) \mathrel{:=} b$ and $\min(a, b) \mathrel{:=} a$ if $a < b$ . Prove that $\max(a, b) + \min(a, b) = a + b$ .

Solution. Since $a \ge b$ or $a < b$ , and these two cases cover every pair of real numbers, we argue by cases ( $\mathrm{\vee E}$ , Definition 1.6.1), as in Example (The absolute value of a product).

Case $a \ge b$ . Then $\max(a, b) = a$ and $\min(a, b) = b$ , so $\max(a, b) + \min(a, b) = a + b$ .

Case $a < b$ . Then $\max(a, b) = b$ and $\min(a, b) = a$ , so $\max(a, b) + \min(a, b) = b + a = a + b$ .

In either case the equation holds, which proves it. Both cases end in the same statement, the goal, as $\mathrm{\vee E}$ requires.

Exercise (R2)

Let $x$ be a real number. Write $N$ for “ $x < 0$ ”, $M$ for “ $x > 1$ ”, and $S$ for “ $x = 7$ ”. Translate the argument below into a sequent in these letters, and derive it.

$x$ is neither negative nor greater than $1$ . Therefore $x$ is not negative, and if $x$ is greater than $1$ , then $x = 7$ .

Solution. The phrase book (Section 1.1) gives “neither … nor” as $\neg N \wedge \neg M$ ; equivalently (Proposition 2.5.5 (a), (b)) $\neg(N \vee M)$ , “ $N \vee M$ fails”, which we use here as the premise. It is not $\neg N \vee M$ . The conclusion is a conjunction whose second part is an implication. The sequent (Definition 1.2.4) is $\neg(N \vee M) \vdash \neg N \wedge (M \to S).$ The goal is a conjunction; the first conjunct is a negation (a $\mathrm{\neg I}$ box on $N$ ), and the second an implication (a box on $M$ ). In both boxes $\mathrm{\vee I}$ builds $N \vee M$ , which clashes with the premise; in the second box $\mathrm{\bot E}$ then gives $S$ .

\neg (N \vee M)

N

asm, for

\mathrm{{\neg}I}

N \vee M

\mathrm{{\vee}I}

\bot

\mathrm{{\neg}E}

3, 1

\neg N

\mathrm{{\neg}I}

2–4

M

asm, for

\mathrm{{{\to}}I}

N \vee M

\mathrm{{\vee}I}

\bot

\mathrm{{\neg}E}

7, 1

S

\mathrm{{\bot}E}

M \to S

\mathrm{{{\to}}I}

6–9

\neg N \wedge (M \to S)

\mathrm{{\wedge}I}

5, 10

Lines 2–5 are half of Proposition 2.5.5 (a), which turns $\neg(N \vee M)$ into the phrase book’s $\neg N \wedge \neg M$ ; with $\neg N \wedge \neg M$ as the premise, $\mathrm{\wedge E}$ shortens both boxes. The implication $M \to S$ is vacuously true, as in Proposition 2.1.2: the premise rules out $M$ , and a promise never tested is never broken, whatever $S$ says.

Exercise (R3)

Is $(P \to Q) \to R \vdash P \to (Q \to R)$ derivable? Derive or break its converse, $P \to (Q \to R) \vdash (P \to Q) \to R$ .

Solution. The first is derivable, by the search method of Section 3.1. The goal gives a box on $P$ , then a box on $Q$ , with the goal $R$ . The premise gives $R$ by $\mathrm{{\to}E}$ once we produce $P \to Q$ , a new goal: a box on $P$ whose last line repeats $Q$ .

(P \to Q) \to R

P

asm, for

\mathrm{{{\to}}I}

Q

asm, for

\mathrm{{{\to}}I}

P

asm, for

\mathrm{{{\to}}I}

Q

\mathrm{R}

P \to Q

\mathrm{{{\to}}I}

4–5

R

\mathrm{{{\to}}E}

1, 6

Q \to R

\mathrm{{{\to}}I}

3–7

P \to (Q \to R)

\mathrm{{{\to}}I}

2–8

The repetition at line 5 puts $Q$ inside the box of line 4, as $\mathrm{{\to}I}$ requires (clause (D3) of Definition 1.4.2). Two look-alike tools do not apply. Proposition 1.4.2 moves a conjunction in and out of a hypothesis, $(P \wedge Q) \to R \dashv\vdash P \to (Q \to R)$ , and the premise here has $P \to Q$ , not $P \wedge Q$ , in that place. And Proposition 1.4.1 chains two implications, which we do not have.

The converse breaks: with $P$ and $R$ false (and $Q$ either way), the premise $P \to (Q \to R)$ is true because $P$ is false, while $P \to Q$ is true and $R$ is false, so the conclusion is false. Chapter 4 proves that such a choice rules out every derivation, so that a search for it can only stall: the chapter’s open question, in a new place.

Exercise (R4)

Ana and Ben talk about a real number.

Ana. Let $x$ be a real number with $x^2 < x$ . Then $x$ is positive.

Ben. Why can’t it be negative?

Ana. A negative number is less than its square.

Ben. And zero?

Ana. At zero, $x^2$ equals $x$ . And $x$ is less than $1$ , because for $x \ge 1$ we would have $x^2 \ge x$ .

Ben. So $0 < x < 1$ . But you never said why $x^2 \ge x$ when $x \ge 1$ .

Ana. Multiply $x \ge 1$ by $x$ , which is positive.

(a) What is the conclusion, and who states it?
(b) Turn the dialogue into a derivation.
(c) Is Ana’s last answer enough?

Solution.

(a) “ $0 < x < 1$ ”, stated by Ben. Ana’s first line, “ $x$ is positive”, is an intermediate step.
(b) With, for instance, $N$ : “ $x < 0$ ”, $Z$ : “ $x = 0$ ”, $B$ : “ $x \ge 1$ ”, $L$ : “ $x^2 < x$ ”, the premise is $L$ . The facts:
- $N \to \neg L$ (Ana: a negative $x$ has $x^2 > 0 > x$ );
- $Z \to \neg L$ (Ana: $x^2 = x$ at $0$ );
- $B \to \neg L$ (Ana, then justified at Ben’s request).
The conclusion $(\neg N \wedge \neg Z) \wedge \neg B$ reads as “ $x \ge 0$ , $x \ne 0$ , $x < 1$ ” by the convention of Section 2.1, that is, $0 < x < 1$ , since $x \ge 0$ and $x \ne 0$ give $x > 0$ . The sequent is $N \to \neg L, \ Z \to \neg L, \ B \to \neg L, \ L \vdash (\neg N \wedge \neg Z) \wedge \neg B.$

For the derivation: $\mathrm{MT}$ (Proposition 2.3.1) needs the negation of each fact’s conclusion, and that is $\neg\neg L$ , given by $\mathrm{\neg\neg I}$ (Proposition 2.5.1 (a)); hence line 5.

1 $N \to \neg L$
2 $Z \to \neg L$
3 $B \to \neg L$
4 $L$
5 $\neg\neg L$ $\mathrm{{\neg\neg}I}$ 4
6 $\neg N$ $\mathrm{MT}$ 1, 5
7 $\neg Z$ $\mathrm{MT}$ 2, 5
8 $\neg B$ $\mathrm{MT}$ 3, 5
9 $\neg N \wedge \neg Z$ $\mathrm{{\wedge}I}$ 6, 7
10 $(\neg N \wedge \neg Z) \wedge \neg B$ $\mathrm{{\wedge}I}$ 9, 8
(c) Yes: $x \ge 1$ gives $x > 0$ , and multiplying $x \ge 1$ by the positive $x$ gives $x^2 \ge x$ .

The method is the extraction of this section (Example (An argument about a prime, extracted)), run on a dialogue; the rules are Chapter 2’s. The look-alike, $\neg N$ by $\mathrm{{\to}E}$ from line 1 and $L$ , fails: $\mathrm{{\to}E}$ needs the hypothesis $N$ on a line, and $\mathrm{MT}$ needs $\neg\neg L$ , not $L$ , which is why line 5 is written.