3.2 Four Kinds of Task

The method of Section 3.1 answers one kind of question: here are premises, here is a conclusion, find a derivation. Mathematics asks others as well:

prove a statement from nothing;
show that two statements say the same thing;
show that some conditions cannot all be met at once;
decide whether a conclusion follows at all, when nobody says whether it does.

Each of these changes where a search starts and what counts as its end. This section takes the four tasks in turn. Underneath, it finds, they are one question.

3.2.1. Four tasks, one method

Let the task choose the search. The four tasks use the same rules and the same method. What differs is the first move and the finish line.

Task	The claim	Where the search starts	What ends it
theorem	$\vdash \varphi$	step 2 on the goal; every resource is an assumption the goal asks for	the goal, reached outside every box
equivalence	$\varphi \dashv\vdash \psi$ (Definition 2.4.2)	two searches, one from each side	two derivations
inconsistency	$\Gamma \vdash \bot$	step 4: the goal is $\bot$ ; look for a clash partner already on a line	$\bot$ , outside every box
derive or break	$\Gamma \vdash \varphi$ ? (verdict withheld)	try to break it first	a derivation, or statements that make the counterexample set true

Only the last task leaves open which way it ends. The other three state their claim: a failed search leaves the question open, as Section 3.1’s failed search did, and a break ends the task against the claim.

Quick check. Which task is each? (i) $\vdash P \vee \neg P$ . (ii) $P \wedge Q \dashv\vdash Q \wedge P$ . (iii) Show that $P$ , $\neg P \vee Q$ and $\neg Q$ cannot all be accepted together. (iv) Does $P \to Q, \ Q \vdash P$ hold?

Solution.

(i) A theorem. (ii) An equivalence. (iii) An inconsistency: the claim $P, \ \neg P \vee Q, \ \neg Q \vdash \bot$ . (iv) Derive or break; it breaks, since it is affirming the consequent (Section 1.3).

3.2.2. Theorems

A theorem of logic is a statement derivable from no premises, $\vdash \varphi$ (Definition 1.2.3 with the list empty).

Example (A statement that implies a contradiction)

Find a derivation of $\vdash (P \to (Q \wedge \neg Q)) \to \neg P$ .

In words: a statement that implies a contradiction is false. Every proof that begins “suppose $P$ ” and ends “which is impossible” has this shape.

Solution. There are no premises, so step 1 writes only the goal. Step 2 opens a box on $P \to (Q \wedge \neg Q)$ with the goal $\neg P$ , and then, inside it, a box on $P$ with the goal $\bot$ :

P \to (Q \wedge \neg Q)

asm, for

\mathrm{{{\to}}I}

\vdots

\neg P

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

\mathrm{{{\to}}I}

1–7

P \to (Q \wedge \neg Q)

asm, for

\mathrm{{{\to}}I}

P

asm, for

\mathrm{{\neg}I}

\vdots

\bot

\neg P

\mathrm{{\neg}I}

2–6

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

\mathrm{{{\to}}I}

1–7

Now there are two resources, both assumptions the goal asked for. Step 3 fires the first on the second, giving $Q \wedge \neg Q$ , and splits it by $\mathrm{\wedge E}$ . Step 4 finds the clash.

P \to (Q \wedge \neg Q)

asm, for

\mathrm{{{\to}}I}

P

asm, for

\mathrm{{\neg}I}

Q \wedge \neg Q

\mathrm{{{\to}}E}

1, 2

Q

\mathrm{{\wedge}E}

\neg Q

\mathrm{{\wedge}E}

\bot

\mathrm{{\neg}E}

4, 5

\neg P

\mathrm{{\neg}I}

2–6

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

\mathrm{{{\to}}I}

1–7

A theorem has no premises, so the goal does all the early work. Once proved, it is a derived rule with nothing above the line (Definition 2.3.1): any derivation, from any premises, may write an instance of it as a line, as derivations already write $\mathrm{LEM}$ .

3.2.3. Equivalences

Example (Proving a disjunction by refuting one side)

Show that $P \to (Q \vee R) \dashv\vdash (P \wedge \neg Q) \to R$ .

This is how mathematics proves a disjunction: to show that $ab = 0$ implies $a = 0$ or $b = 0$ , assume $ab = 0$ and $a \ne 0$ , and show $b = 0$ (divide by $a$ ). The equivalence says that this changes nothing.

Solution. $(\Rightarrow)$ The goal is an implication, so a box on $P \wedge \neg Q$ . $\mathrm{\wedge E}$ splits it, the premise fires on $P$ , and $\mathrm{DS}$ removes the refuted side.

P \to (Q \vee R)

P \wedge \neg Q

asm, for

\mathrm{{{\to}}I}

\vdots

R

(P \wedge \neg Q) \to R

\mathrm{{{\to}}I}

2–6

P \to (Q \vee R)

P \wedge \neg Q

asm, for

\mathrm{{{\to}}I}

P

\mathrm{{\wedge}E}

\neg Q

\mathrm{{\wedge}E}

Q \vee R

\mathrm{{{\to}}E}

1, 3

\vdots

R

(P \wedge \neg Q) \to R

\mathrm{{{\to}}I}

2–6

P \to (Q \vee R)

P \wedge \neg Q

asm, for

\mathrm{{{\to}}I}

P

\mathrm{{\wedge}E}

\neg Q

\mathrm{{\wedge}E}

Q \vee R

\mathrm{{{\to}}E}

1, 3

R

\mathrm{DS}

5, 4

(P \wedge \neg Q) \to R

\mathrm{{{\to}}I}

2–6

$(\Leftarrow)$ The goal is an implication: a box on $P$ , with the goal $Q \vee R$ . That goal is a disjunction, so it is postponed (step 2). The premise waits for $P \wedge \neg Q$ : $P$ is in hand, $\neg Q$ is not, and nothing clashes. That is step 5, and the well-chosen statement is $Q$ , whose negation the premise waits for: $\mathrm{LEM}$ on $Q$ .

(P \wedge \neg Q) \to R

P

asm, for

\mathrm{{{\to}}I}

\vdots

Q \vee R

P \to (Q \vee R)

\mathrm{{{\to}}I}

2–10

(P \wedge \neg Q) \to R

P

asm, for

\mathrm{{{\to}}I}

Q \vee \neg Q

\mathrm{LEM}

Q

asm, for

\mathrm{{\vee}E}

\vdots

Q \vee R

\neg Q

asm, for

\mathrm{{\vee}E}

\vdots

Q \vee R

Q \vee R

\mathrm{{\vee}E}

3, 4–5, 6–9

P \to (Q \vee R)

\mathrm{{{\to}}I}

2–10

In the case $Q$ , $\mathrm{\vee I}$ gives the left side. In the case $\neg Q$ , $\mathrm{\wedge I}$ builds $P \wedge \neg Q$ , the premise gives $R$ , and $\mathrm{\vee I}$ gives the right side.

(P \wedge \neg Q) \to R

P

asm, for

\mathrm{{{\to}}I}

Q \vee \neg Q

\mathrm{LEM}

Q

asm, for

\mathrm{{\vee}E}

Q \vee R

\mathrm{{\vee}I}

\neg Q

asm, for

\mathrm{{\vee}E}

P \wedge \neg Q

\mathrm{{\wedge}I}

2, 6

R

\mathrm{{{\to}}E}

1, 7

Q \vee R

\mathrm{{\vee}I}

Q \vee R

\mathrm{{\vee}E}

3, 4–5, 6–9

P \to (Q \vee R)

\mathrm{{{\to}}I}

2–10

An equivalence is two searches, and they need not be alike. The direction $(\Rightarrow)$ used a derived rule and no classical step. The direction $(\Leftarrow)$ reached step 5, because its goal was a disjunction with no side in hand. When one direction is easy, do it first: it checks that the statements are worth comparing, and its lines often suggest the other direction’s split.

3.2.4. Inconsistent lists

Sometimes the task is not to reach a conclusion but to show that some statements cannot be accepted together: a puzzle’s conditions that no number meets, the hypotheses of a lemma that contradict each other, or the assumption of a proof by contradiction together with what is given. Section 2.5 (Exercise (B5: Derive or break, used later)) already read an $\mathrm{RAA}$ derivation as a derivation of $\bot$ from the counterexample set. A derivation of $\bot$ does this job, and the list it starts from gets a name.

Definition 3.2.1 (Inconsistent and Consistent Lists)

Let $\Gamma$ be a list of statements $\varphi_1, \dots, \varphi_n$ , where $n \ge 0$ . The list $\Gamma$ is inconsistent if $\Gamma \vdash \bot$ : some derivation whose premises all belong to $\Gamma$ has $\bot$ as its last line. It is consistent if it is not inconsistent, that is, if no derivation with premises in $\Gamma$ ends with $\bot$ .

In words: a list is inconsistent when a derivation from it reaches $\bot$ outside every box. The definition speaks only of derivations, and says nothing about whether the statements are true. The list $P, \neg P$ is inconsistent, by one $\mathrm{\neg E}$ line, and so is any list with $\bot$ as a member. To show a list inconsistent, exhibit a derivation. To show one consistent, one would have to rule out every derivation, and nothing in this chapter can do that.

Proposition 3.2.1 (An Inconsistent List Proves Everything)

For a list of statements $\Gamma$ , the following are equivalent:

(i) $\Gamma$ is inconsistent;
(ii) $\Gamma \vdash \psi$ for every statement $\psi$ ;
(iii) $\Gamma \vdash \chi$ and $\Gamma \vdash \neg\chi$ for some statement $\chi$ .

In words: an inconsistent list proves every statement, and a list that proves some statement and its negation is inconsistent. This is Proposition 2.1.1 grown from two premises to any inconsistent list. Its proof is in the fold of the next subsection.

Quick check. Without writing a derivation, explain why $P, \ \neg P \vdash Q \wedge \neg Q$ .

Solution. The list $P, \neg P$ is inconsistent (one $\mathrm{\neg E}$ line), so by Proposition 3.2.1, (i) $\Rightarrow$ (ii), it derives every statement, $Q \wedge \neg Q$ included.

Example (Four conditions that no integer meets)

Let $n$ be an integer. A puzzle asks for an $n$ such that:

(1) if $n$ is even, then $n$ is a multiple of $4$ ;
(2) $n$ is even or a multiple of $3$ ;
(3) if $n$ is a multiple of $3$ , then $n$ is even;
(4) $n$ is not a multiple of $4$ .

With $E$ : “ $n$ is even”, $F$ : “ $n$ is a multiple of $4$ ” and $T$ : “ $n$ is a multiple of $3$ ”, show that the list $E \to F, \ E \vee T, \ T \to E, \ \neg F$ is inconsistent.

Solution. The goal is $\bot$ . Look first for a clash partner already on a line (Section 3.1): line 4 is $\neg F$ , so aim at $F$ .

$F$ is the conclusion of line 1, so the new goal is $E$ , a letter. Line 3 gives $E$ from $T$ , but $T$ is not in hand, and $E \vee T$ does not say which side holds. So use line 2 by $\mathrm{\vee E}$ , with both cases ending in $E$ . The case $E$ is a one-line box; the case $T$ fires line 3.

E \to F

E \vee T

T \to E

\neg F

\vdots

F

\bot

\mathrm{{\neg}E}

9, 4

E \to F

E \vee T

T \to E

\neg F

E

asm, for

\mathrm{{\vee}E}

T

asm, for

\mathrm{{\vee}E}

\vdots

E

E

\mathrm{{\vee}E}

2, 5–5, 6–7

F

\mathrm{{{\to}}E}

1, 8

\bot

\mathrm{{\neg}E}

9, 4

E \to F

E \vee T

T \to E

\neg F

E

asm, for

\mathrm{{\vee}E}

T

asm, for

\mathrm{{\vee}E}

E

\mathrm{{{\to}}E}

3, 6

E

\mathrm{{\vee}E}

2, 5–5, 6–7

F

\mathrm{{{\to}}E}

1, 8

\bot

\mathrm{{\neg}E}

9, 4

Read as a proof about $n$ , the derivation shows that no integer meets all four conditions: by (2) and (3), $n$ is even in either case; by (1) it is a multiple of $4$ ; and (4) says it is not. Yet any three of the conditions can be met together: $n = 6$ meets all but (1), $n = 1$ all but (2), $n = 3$ all but (3), and $n = 12$ all but (4). The inconsistency belongs to the four together. The derivation does not say which condition to drop (the fold “Logic permits; it does not choose” in Section 3.1).

Quick check. Which integers between $1$ and $10$ meet conditions (1), (2) and (4) of Example (Four conditions that no integer meets), and which condition does each break?

Solution. $3$ and $9$ : they are odd, so (1) promises nothing; they are multiples of $3$ , so (2) holds; and they are not multiples of $4$ . Each breaks (3).

Here are three more inconsistent lists, each with compound members, and one list that only looks inconsistent.

Example (Three inconsistent lists, and a look-alike)

The list	The clash it reaches	The derivation of $\bot$ , in brief
$(P \vee Q) \to R, \ P \wedge \neg R$	$R$ , $\neg R$	$P$ by $\mathrm{\wedge E}$ ; $P \vee Q$ by $\mathrm{\vee I}$ ; $R$ by $\mathrm{{\to}E}$ ; $\neg R$ by $\mathrm{\wedge E}$ ; $\bot$ by $\mathrm{\neg E}$ (7 lines)
$P \leftrightarrow \neg P$	$P$ , $\neg P$	a box on $P$ : $\neg P$ by $\mathrm{{\leftrightarrow}E}$ , $\bot$ by $\mathrm{\neg E}$ ; $\neg P$ by $\mathrm{\neg I}$ ; then $P$ by $\mathrm{{\leftrightarrow}E}$ , and $\neg P$ by $\mathrm{{\leftrightarrow}E}$ again from that $P$ ; $\bot$ by $\mathrm{\neg E}$ (8 lines)
$\neg(P \to Q), \ \neg P$	$P \to Q$ , $\neg(P \to Q)$	$P \to Q$ by VI from $\neg P$ (Proposition 2.1.2); $\bot$ by $\mathrm{\neg E}$ (4 lines)

Not an instance. $P \to Q, \ P \to \neg Q$ . The two members look opposed. But with $P$ false (say $P$ : “ $0 = 1$ ”) both are true, whatever $Q$ says, so the claim $P \to Q, \ P \to \neg Q \vdash \bot$ breaks. What the list does derive is $\neg P$ : from $P$ it would give $Q$ and $\neg Q$ . This chapter does not call the list inconsistent, and it does not call it consistent either. Whether a break rules out every derivation of $\bot$ is the question the chapter ends on (Section 3.3).

The second row’s derivation is written without a detour: the line $\neg P$ built by $\mathrm{\neg I}$ is cited by $\mathrm{{\leftrightarrow}E}$ , never taken apart at once by $\mathrm{\neg E}$ , so it stays, as Section 3.1’s detour paragraph allows (“an introduced line cited elsewhere stays”).

Warning (Not allowed: claims about inconsistency). Each claim below is wrong; the tag names what it misreads.

“The list is inconsistent because one of its members is false.” Truth for derivation: inconsistency is a derivation of $\bot$ (Definition 3.2.1), not a false member. The one-member list “ $2 > 3$ ” has a false member, and no derivation of $\bot$ is offered.
“ $P \to Q$ and $P \to \neg Q$ contradict each other, so the list is inconsistent.” Looks for derivation: nothing has been derived. Both members are true when $P$ is false, and the claim of inconsistency breaks.
“Line 7, inside the box of the assumption $P$ , is $\bot$ ; so the premises are inconsistent.” A boxed line: that $\bot$ depends on $P$ . It shows the list $\Gamma, P$ inconsistent, and so $\Gamma \vdash \neg P$ . The last line must lie outside every box (Definition 1.4.2).
“A search for $\bot$ stalled, so the list is consistent.” A stall for a proof: a stalled search proves nothing (Section 3.1). Consistency is the absence of every derivation of $\bot$ .
“The list is inconsistent, so its first member is false.” The list for a member: inconsistency belongs to the list. It says that the members cannot all be accepted together, not which one fails (compare the four conditions above).

3.2.5. The counterexample set, derived

Proving and refuting meet in one list. The counterexample set of a claim $\Gamma \vdash \varphi$ is the list $\Gamma, \neg\varphi$ (Definition 1.1.3). Breaking the claim makes that list true. Deriving the claim, it turns out, is showing that list inconsistent.

Proposition 3.2.2 (Derivable Exactly When the Counterexample Set Is Inconsistent)

Let $\Gamma$ be a list of statements and $\varphi$ a statement.

(a) $\Gamma \vdash \neg\varphi$ if and only if the list $\Gamma, \varphi$ is inconsistent.
(b) $\Gamma \vdash \varphi$ if and only if the list $\Gamma, \neg\varphi$ is inconsistent.

In words: (b) says that a claim is derivable exactly when its counterexample set is inconsistent, and (a) says the same for a negated conclusion. In the proofs, the box of (a) closes by $\mathrm{\neg I}$ and that of (b) by $\mathrm{RAA}$ : Section 2.5’s distinction between the two rules, stated about whole derivations. Section 1.1’s test of a form, try to break it, now has a partner on the same list: make the counterexample set true, or derive $\bot$ from it.

With $\Gamma$ empty and $\varphi$ the statement $P \leftrightarrow \neg P$ , part (a) says that the second row of Example (Three inconsistent lists, and a look-alike) and Lemma 2.4.2, $\vdash \neg(P \leftrightarrow \neg P)$ , are the same fact.

Second readingThe proofs: append a line, or copy a derivation into a box

Proof. Proof of Proposition 3.2.1. (i) $\Rightarrow$ (ii): a derivation of $\bot$ with premises in $\Gamma$ , followed by the line $\psi$ by $\mathrm{\bot E}$ , is a derivation of $\psi$ . Its last line lies in no box. (ii) $\Rightarrow$ (iii): apply (ii) to any $\chi$ and to $\neg\chi$ . (iii) $\Rightarrow$ (i): the sequent $\chi, \neg\chi \vdash \bot$ has a one-step derivation ( $\mathrm{\neg E}$ ), so by Lemma 2.3.3 (c), $\Gamma \vdash \bot$ .

Proof. Proof of Proposition 3.2.2. (b), $(\Rightarrow)$ : from $\Gamma \vdash \varphi$ , Lemma 2.3.3 (a) gives $\Gamma, \neg\varphi \vdash \varphi$ . The one-line derivation of the premise $\neg\varphi$ gives $\Gamma, \neg\varphi \vdash \neg\varphi$ . By Lemma 2.3.3 (c) with $\varphi, \neg\varphi \vdash \bot$ , we get $\Gamma, \neg\varphi \vdash \bot$ .

(b), $(\Leftarrow)$ : let $D$ be a derivation of $\bot$ with premises in $\Gamma, \neg\varphi$ . If the last line of $D$ is a premise in $\Gamma$ , then $\bot$ is a member of $\Gamma$ , and $\mathrm{\bot E}$ gives $\varphi$ . (The last line cannot be the premise $\neg\varphi$ , since $\neg\varphi$ is not $\bot$ .) Otherwise, write as premises those premises of $D$ that belong to $\Gamma$ . Open a box with the assumption $\neg\varphi$ . Inside it, copy the lines of $D$ that are not premises, in order, with their boxes, renumbering citations; a citation of the premise $\neg\varphi$ now cites the assumption. Close the box after the copy of the last line of $D$ , and write $\varphi$ by $\mathrm{RAA}$ .

Every copied citation is legal. A cited premise of $\Gamma$ lies above the box, in no box. The assumption is available throughout the box. The boxes of $D$ sit inside the new box as they sat in $D$ , so every line and every box that was available at a citing line stays available (the scope rule of Definition 1.4.2). The last line of $D$ lies in no box of $D$ , so its copy is a line of the new box itself, as $\mathrm{RAA}$ requires. If $D$ never cites $\neg\varphi$ , nothing changes.

Part (a) is the same, with $\varphi$ in place of $\neg\varphi$ and $\mathrm{\neg I}$ in place of $\mathrm{RAA}$ . If the last line of $D$ is the premise $\varphi$ itself (possible only when $\varphi$ is $\bot$ ), nothing is copied: the box is its one assumption line, and $\mathrm{\neg I}$ closes it at once. In $(\Rightarrow)$ , $\Gamma, \varphi \vdash \varphi$ and, by weakening, $\Gamma, \varphi \vdash \neg\varphi$ ; chaining with $\mathrm{\neg E}$ finishes.

The copying is the move of Section 1.4’s Exercise (C4: The assumptions a line depends on, used later) (b), which turns open assumptions into premises, run backwards.

Quick check. By Proposition 3.2.2, which list must be shown inconsistent to prove $\vdash \neg(P \wedge \neg P)$ ? Show it.

Solution. By (a), with $\Gamma$ empty and $\varphi$ the statement $P \wedge \neg P$ , the list is $P \wedge \neg P$ :

P \wedge \neg P

P

\mathrm{{\wedge}E}

\neg P

\mathrm{{\wedge}E}

\bot

\mathrm{{\neg}E}

2, 3

3.2.6. One task in four costumes

Every task of this section is a claim that something is derivable, and by Proposition 3.2.2 every such claim is a claim that a list is inconsistent.

Task	As a claim of derivability	As a claim of inconsistency	It breaks when some choice of statements makes
theorem	$\vdash \varphi$	the list $\neg\varphi$	$\varphi$ false
equivalence	$\varphi \vdash \psi$ and $\psi \vdash \varphi$	the lists $\varphi, \neg\psi$ and $\psi, \neg\varphi$	one of $\varphi$ , $\psi$ true and the other false
inconsistency	$\Gamma \vdash \bot$	the list $\Gamma$	every member of $\Gamma$ true
derive or break	$\Gamma \vdash \varphi$	the list $\Gamma, \neg\varphi$	every member of $\Gamma, \neg\varphi$ true

An equivalence is also a theorem: $\varphi \dashv\vdash \psi$ holds exactly when $\vdash \varphi \leftrightarrow \psi$ . Copy each of the two derivations into a box, as in the fold above, and close both boxes by $\mathrm{{\leftrightarrow}I}$ . Conversely, add the premise $\varphi$ to a derivation of $\varphi \leftrightarrow \psi$ and write $\psi$ by $\mathrm{{\leftrightarrow}E}$ , and likewise for $\psi$ .

So the four tasks are one: is this list inconsistent? Each costume starts the search in a different place, which is why the task chooses the search. And each row has a second half, the last column: what to do when the list might instead be made true. That is the fourth task.

3.2.7. Derive or break

Section 1.5 listed claims without a verdict (“Derive it or break it”). Here the format becomes a task with its own first move: decide before you search.

Try to break it first. Spend a few minutes trying to make the counterexample set true, starting where the conclusion is false (Section 1.1, “Where to look first”). Either some choice of statements works, and the claim breaks; or every attempt is forced into a clash. Then search for a derivation. The forced attempt usually suggests a plan for it: the statements the attempt had to make true suggest the assumptions of the derivation’s boxes, and the clash it met suggests the derivation’s $\bot$ .

Example (Two claims, one connective apart)

Derive or break each claim.

(a) $P \to (Q \to R), \ P \to \neg R \vdash P \to \neg Q$ .
(b) $P \to (Q \vee R), \ P \to \neg R \vdash P \to \neg Q$ .

Solution. (a), trying to break it. The conclusion is false only with $P$ true and $\neg Q$ false, that is, $Q$ true. Then the first premise needs $Q \to R$ true, so $R$ true. The second needs $\neg R$ true, so $R$ false. Every choice was forced, and the forcing ends in a clash. So we search.

(a), the derivation. The attempt’s plan: a box on $P$ (the conclusion’s hypothesis), a box on $Q$ (the statement whose negation is wanted), and the clash $R$ , $\neg R$ . Before the box on $Q$ opens, both premises fire on $P$ : lines that need nothing new (Section 3.1).

P \to (Q \to R)

P \to \neg R

P

asm, for

\mathrm{{{\to}}I}

\vdots

\neg Q

P \to \neg Q

\mathrm{{{\to}}I}

3–9

P \to (Q \to R)

P \to \neg R

P

asm, for

\mathrm{{{\to}}I}

Q \to R

\mathrm{{{\to}}E}

1, 3

\neg R

\mathrm{{{\to}}E}

2, 3

Q

asm, for

\mathrm{{\neg}I}

\vdots

\bot

\neg Q

\mathrm{{\neg}I}

6–8

P \to \neg Q

\mathrm{{{\to}}I}

3–9

P \to (Q \to R)

P \to \neg R

P

asm, for

\mathrm{{{\to}}I}

Q \to R

\mathrm{{{\to}}E}

1, 3

\neg R

\mathrm{{{\to}}E}

2, 3

Q

asm, for

\mathrm{{\neg}I}

R

\mathrm{{{\to}}E}

4, 6

\bot

\mathrm{{\neg}E}

7, 5

\neg Q

\mathrm{{\neg}I}

6–8

P \to \neg Q

\mathrm{{{\to}}I}

3–9

(b), trying to break it. The same start: $P$ true, $Q$ true. Now the first premise asks only that $Q \vee R$ be true, and $Q$ already makes it so. $R$ is free, and the second premise asks for $R$ false. Nothing clashes: with $P$ and $Q$ true and $R$ false, every member of the counterexample set $P \to (Q \vee R), \ P \to \neg R, \ \neg(P \to \neg Q)$ is true. With statements about a real number $x$ , take $P$ : “ $x > 0$ ”, $Q$ : “ $x > 1$ ”, $R$ : “ $x > 3$ ”, at $x = 2$ . The claim breaks.

The two claims differ in one connective. Trying to break each found its verdict, and for (a) it also found the derivation. The method of Section 3.1 would have found (a) without the attempt. On (b) the method of Section 3.1 could only search, and a stall is not a verdict; the break is.

The task as a chart. The loop at the bottom is honest: nothing in this chapter promises that it ends.

$Diagram. Labels: every try is forced into a clash, a claim Gamma vdash varphi ,\verdict withheld, can the counterexample set\be made true? (start where\the conclusion is false), it breaks:\give the statements, search for a derivation\\(Section 3.1): the forced\clash suggests a plan, has the search\finished ?$

Quick check. Change one symbol of the first premise of claim (b) in Example (Two claims, one connective apart) so that the claim can be derived, and derive it.

Solution. For example, replace $\vee$ by $\to$ : that is claim (a), derived above. Or replace $\vee$ by $\wedge$ : from $P$ , the premises give $Q \wedge R$ and $\neg R$ , which clash.

P \to (Q \wedge R)

P \to \neg R

P

asm, for

\mathrm{{{\to}}I}

Q \wedge R

\mathrm{{{\to}}E}

1, 3

R

\mathrm{{\wedge}E}

\neg R

\mathrm{{{\to}}E}

2, 3

\bot

\mathrm{{\neg}E}

5, 6

\neg Q

\mathrm{{\bot}E}

P \to \neg Q

\mathrm{{{\to}}I}

3–8

Replacing $\vee$ by $\leftrightarrow$ , or $Q$ by $R$ , works too. For $\leftrightarrow$ : from $P$ , the premises give $Q \leftrightarrow R$ and $\neg R$ ; a box on $Q$ gives $R$ by $\mathrm{{\leftrightarrow}E}$ , which clashes with $\neg R$ , so $\neg Q$ by $\mathrm{\neg I}$ . For $Q$ replaced by $R$ : from $P$ , $R \vee R$ gives $R$ by $\mathrm{\vee E}$ , which clashes with $\neg R$ , so $\neg Q$ by $\mathrm{\bot E}$ .

Remark (Looking ahead). Chapter 4 calls a list whose members can all be made true at once satisfiable, and proves that the satisfiable lists are exactly the consistent ones.

3.2.8. Exercises

A. Check your understanding

Exercise (A1)

(a) When is a list of statements inconsistent?
(b) By Proposition 3.2.2, which list is inconsistent exactly when $P \to Q, \ Q \to R \vdash P \to R$ ?
(c) True or false: every list that has $\bot$ as a member is inconsistent.
(d) True or false: if $\Gamma$ is inconsistent, so is every list $\Gamma, \psi$ .
(e) Name the task and the first move: “show that $P \wedge Q \dashv\vdash Q \wedge P$ ”.

Solution.

(a) When $\bot$ is derivable from it (Definition 3.2.1).
(b) The counterexample set $P \to Q, \ Q \to R, \ \neg(P \to R)$ .
(c) True: the one-line derivation whose only line is the premise $\bot$ ends with $\bot$ .
(d) True, by Lemma 2.3.3 (a): the derivation of $\bot$ from $\Gamma$ has its premises in $\Gamma, \psi$ .
(e) An equivalence: two derivations, each starting with $\mathrm{\wedge E}$ on its premise. Each is Proposition 1.2.1, with the letters exchanged for the second.

Exercise (A2: Drill)

The parts run from naming the task, through one step and a missing piece, to claims to judge and short derivations.

(a) Which task is “show $\vdash (P \wedge Q) \to P$ ”?
(b) “Show that $P \to \neg Q$ and $Q \to \neg P$ are provably equivalent.” Which two derivations does this ask for?
(c) Write “ $P$ , $P \to Q$ and $\neg Q$ cannot all be accepted together” as a sequent.
(d) A search for $\bot$ from $P \wedge \neg Q, \ P \to Q$ begins. Write its first three lines after the premises.
(e) Which list must be shown inconsistent to prove $P \to Q \vdash \neg Q \to \neg P$ by Proposition 3.2.2 (b)?
(f) The list $Q, \ \neg P, \ \neg\neg R$ is the counterexample set of which claims?
(g) “ $P \to Q, \ P \to \neg Q$ is inconsistent, since its members contradict each other.” Is this correct?
(h) “Inside the box of the assumption $P$ , line 6 is $\bot$ ; so the premises are inconsistent.” Is this correct?
(i) “A search for $\bot$ from $P \vee Q, \ \neg P$ stalled; so the list is consistent.” Is this correct?
(j) “Since $P, \neg P \vdash \bot$ , the list $P, \neg P$ derives both $Q$ and $\neg Q$ .” Is this correct?
(k) Derive $\bot$ from $P \to Q, \ Q \to R, \ P, \ \neg R$ .
(l) Derive $\bot$ from $P \vee Q, \ \neg P, \ \neg Q$ .

Solution.

(a) A theorem.
(b) $P \to \neg Q \vdash Q \to \neg P$ and $Q \to \neg P \vdash P \to \neg Q$ .
(c) $P, \ P \to Q, \ \neg Q \vdash \bot$ .
(d) 3 $P$ , $\mathrm{\wedge E}$ 1; 4 $Q$ , $\mathrm{{\to}E}$ 2, 3; 5 $\neg Q$ , $\mathrm{\wedge E}$ 1. (Then 6 $\bot$ , $\mathrm{\neg E}$ 4, 5.)
(e) $P \to Q, \ \neg(\neg Q \to \neg P)$ .
(f) Of $Q, \neg P \vdash \neg R$ , with $\neg\neg R$ the negated conclusion, and of $Q, \neg\neg R \vdash P$ , with $\neg P$ the negated conclusion. $Q$ is not a negation, so it is not the negated conclusion of any claim.
(g) No. Both members are true when $P$ is false, and nothing has been derived.
(h) No. It shows the premises together with $P$ inconsistent, so the premises derive $\neg P$ .
(i) No: a stalled search proves nothing.
(j) Yes: Proposition 3.2.1, (i) $\Rightarrow$ (ii).
(k) 5 $Q$ , $\mathrm{{\to}E}$ 1, 3; 6 $R$ , $\mathrm{{\to}E}$ 2, 5; 7 $\bot$ , $\mathrm{\neg E}$ 6, 4.
(l) 4 $P$ , assumption; 5 $\bot$ , $\mathrm{\neg E}$ 4, 2; 6 $Q$ , assumption; 7 $\bot$ , $\mathrm{\neg E}$ 6, 3; 8 $\bot$ , $\mathrm{\vee E}$ 1, 4–5, 6–7.

B. Practice

Exercise (B1: Three theorems)

Derive each theorem, and say which step of Section 3.1’s method opens each box.

(a) $\vdash \neg(P \wedge \neg P) \wedge \neg\neg(P \vee \neg P)$ .
(b) $\vdash ((P \to Q) \wedge (P \vee Q)) \to Q$ .
(c) $\vdash ((P \to Q) \to Q) \to ((Q \to P) \to P)$ .

Solution.

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

Boxes 1 and 6 come from step 2: each goal is a negation. Box 7 comes from step 2 inside step 4: step 4 chooses to manufacture $P \vee \neg P$ from its side $\neg P$ , so that it clashes with line 6, and the goal $\neg P$ , a negation, opens the box. The second conjunct needed no classical rule, although $P \vee \neg P$ itself does in this book’s derivation (Proposition 2.5.3).
(b)
1 $(P \to Q) \wedge (P \vee Q)$ asm, for $\mathrm{{{\to}}I}$
2 $P \to Q$ $\mathrm{{\wedge}E}$ 1
3 $P \vee Q$ $\mathrm{{\wedge}E}$ 1
4 $P$ asm, for $\mathrm{{\vee}E}$
5 $Q$ $\mathrm{{{\to}}E}$ 2, 4
6 $Q$ asm, for $\mathrm{{\vee}E}$
7 $Q$ $\mathrm{{\vee}E}$ 3, 4–5, 6–6
8 $((P \to Q) \wedge (P \vee Q)) \to Q$ $\mathrm{{{\to}}I}$ 1–7

Box 1 comes from step 2. Boxes 4 and 6 come from step 3: the resource $P \vee Q$ is split by $\mathrm{\vee E}$ , both cases ending in the goal $Q$ (the case $Q$ is a one-line box). Lines 2 and 3 need nothing new. Read aloud: if $P$ implies $Q$ , and $P$ or $Q$ holds, then $Q$ holds.
(c)

(P \to Q) \to Q

asm, for

\mathrm{{{\to}}I}

Q \to P

asm, for

\mathrm{{{\to}}I}

\neg P

asm, for

\mathrm{RAA}

P \to Q

VI 3

Q

\mathrm{{{\to}}E}

1, 4

P

\mathrm{{{\to}}E}

2, 5

\bot

\mathrm{{\neg}E}

6, 3

P

\mathrm{RAA}

3–7

(Q \to P) \to P

\mathrm{{{\to}}I}

2–8

((P \to Q) \to Q) \to ((Q \to P) \to P)

\mathrm{{{\to}}I}

1–9

Boxes 1 and 2 come from step 2. Box 3 comes from step 5: the goal $P$ is a letter, and the resources wait for $P \to Q$ , which nothing in hand gives.

Exercise (B2: Two directions)

Show that $(P \wedge Q) \to R \dashv\vdash (P \wedge \neg R) \to \neg Q$ .

(a) The search for $(\Leftarrow)$ has reached the stage below. Name the move, then complete it.
(b) Derive $(\Rightarrow)$ .
(c) Which direction used a classical rule, and why did the other not need one?

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

P \wedge Q

asm, for

\mathrm{{{\to}}I}

\vdots

R

(P \wedge Q) \to R

\mathrm{{{\to}}I}

2–9

Solution.

(a) First the lines that need nothing new, $P$ and $Q$ by $\mathrm{\wedge E}$ . Then the move is step 5: the current goal $R$ is a letter, no resource gives it, and nothing clashes, so assume $\neg R$ for $\mathrm{RAA}$ .
1 $(P \wedge \neg R) \to \neg Q$
2 $P \wedge Q$ asm, for $\mathrm{{{\to}}I}$
3 $P$ $\mathrm{{\wedge}E}$ 2
4 $Q$ $\mathrm{{\wedge}E}$ 2
5 $\neg R$ asm, for $\mathrm{RAA}$
6 $P \wedge \neg R$ $\mathrm{{\wedge}I}$ 3, 5
7 $\neg Q$ $\mathrm{{{\to}}E}$ 1, 6
8 $\bot$ $\mathrm{{\neg}E}$ 4, 7
9 $R$ $\mathrm{RAA}$ 5–8
10 $(P \wedge Q) \to R$ $\mathrm{{{\to}}I}$ 2–9
(b)
1 $(P \wedge Q) \to R$
2 $P \wedge \neg R$ asm, for $\mathrm{{{\to}}I}$
3 $P$ $\mathrm{{\wedge}E}$ 2
4 $\neg R$ $\mathrm{{\wedge}E}$ 2
5 $Q$ asm, for $\mathrm{{\neg}I}$
6 $P \wedge Q$ $\mathrm{{\wedge}I}$ 3, 5
7 $R$ $\mathrm{{{\to}}E}$ 1, 6
8 $\bot$ $\mathrm{{\neg}E}$ 7, 4
9 $\neg Q$ $\mathrm{{\neg}I}$ 5–8
10 $(P \wedge \neg R) \to \neg Q$ $\mathrm{{{\to}}I}$ 2–9
(c) $(\Leftarrow)$ used $\mathrm{RAA}$ at line 9, because its goal $R$ is a letter. $(\Rightarrow)$ needed none, because its goal $\neg Q$ is a negation, which $\mathrm{\neg I}$ builds. This is a claim about our two derivations only.

In words: to prove “if $P$ and $Q$ , then $R$ ”, it is enough to prove “if $P$ and not $R$ , then not $Q$ ”, a contrapositive in one hypothesis.

Exercise (B3: Derive or break, used later)

For each claim, derive it or break it. Try to break it first. To break a claim, give statements that make its counterexample set true.

(a) $\neg P \vee \neg Q \vdash \neg(P \vee Q)$
(b) $\neg(P \leftrightarrow Q), \ P \vdash \neg Q$
(c) $P \to Q, \ \neg P \to (R \vee Q), \ \neg R \vdash Q$
(d) $P \to Q, \ \neg P \to (R \vee Q), \ \neg R \vdash P$
(e) $(P \to Q) \to R, \ \neg R \vdash P$
(f) $(P \to Q) \to R, \ \neg R \vdash Q$
(g) $P \vee Q, \ P \vdash \neg Q$
(h) $P \vee Q, \ \neg(P \wedge Q), \ P \vdash \neg Q$
(i) $\neg(P \vee Q) \to P \vdash P \vee Q$

Solution. The verdict comes first, then the derivation or the break. In every break, $x$ is a real number.

(a) Breaks. Take $P$ : “ $x > 2$ ”, $Q$ : “ $x > 0$ ”, at $x = 1$ . $\neg P$ is true, so $\neg P \vee \neg Q$ is true; $Q$ is true, so $P \vee Q$ is true and $\neg(P \vee Q)$ is false. (The De Morgan law with this premise is $\neg P \vee \neg Q \vdash \neg(P \wedge Q)$ , Proposition 2.5.5 (c); here the wrong connective sits inside the negation.)
(b) Derive.

1 $\neg (P \leftrightarrow Q)$
2 $P$
3 $Q$ asm, for $\mathrm{{\neg}I}$
4 $P$ asm, for $\mathrm{{{\leftrightarrow}}I}$
5 $Q$ $\mathrm{R}$ 3
6 $Q$ asm, for $\mathrm{{{\leftrightarrow}}I}$
7 $P$ $\mathrm{R}$ 2
8 $P \leftrightarrow Q$ $\mathrm{{{\leftrightarrow}}I}$ 4–5, 6–7
9 $\bot$ $\mathrm{{\neg}E}$ 8, 1
10 $\neg Q$ $\mathrm{{\neg}I}$ 3–9

This is the first box of Exercise (B5: Derive or break, used later) (f).
(c) Derive. Step 5: the goal $Q$ is a letter, and the first two premises wait for $P$ and for $\neg P$ , so $\mathrm{LEM}$ on $P$ . $\mathrm{DS}$ matches as stated in Section 2.3, refuting the left disjunct $R$ .
1 $P \to Q$
2 $\neg P \to (R \vee Q)$
3 $\neg R$
4 $P \vee \neg P$ $\mathrm{LEM}$
5 $P$ asm, for $\mathrm{{\vee}E}$
6 $Q$ $\mathrm{{{\to}}E}$ 1, 5
7 $\neg P$ asm, for $\mathrm{{\vee}E}$
8 $R \vee Q$ $\mathrm{{{\to}}E}$ 2, 7
9 $Q$ $\mathrm{DS}$ 8, 3
10 $Q$ $\mathrm{{\vee}E}$ 4, 5–6, 7–9
(d) Breaks. Take $P$ : “ $x > 5$ ”, $Q$ : “ $x > 0$ ”, $R$ : “ $x > 10$ ”, at $x = 1$ . $P$ is false, so $P \to Q$ is true; $\neg P$ and $Q$ are true, so $\neg P \to (R \vee Q)$ is true; $\neg R$ is true; and $P$ is false. Trying to break it first: with $P$ false, the premises force $Q$ true and $R$ false, and nothing clashes. The tempting step from “ $P$ gives $Q$ ” and “ $Q$ holds”, which (c) derives, to $P$ is affirming the consequent (Section 1.3).
(e) Derive.

1 $(P \to Q) \to R$
2 $\neg R$
3 $\neg (P \to Q)$ $\mathrm{MT}$ 1, 2
4 $\neg P$ asm, for $\mathrm{RAA}$
5 $P \to Q$ VI 4
6 $\bot$ $\mathrm{{\neg}E}$ 5, 3
7 $P$ $\mathrm{RAA}$ 4–6
(f) Breaks. Take $P$ : “ $x > 0$ ”, $Q$ : “ $x > 2$ ”, $R$ : “ $x > 3$ ”, at $x = 1$ . $P \to Q$ is false, so $(P \to Q) \to R$ is true; $\neg R$ is true; and $Q$ is false.
(g) Breaks; it is affirming a disjunct (Section 1.6). Take $P$ : “ $x > 1$ ”, $Q$ : “ $x > 2$ ”, at $x = 3$ : $P \vee Q$ and $P$ are true, and $\neg Q$ is false.
(h) Derive. The premise $P \vee Q$ is not needed.

P \vee Q

\neg (P \wedge Q)

P

Q

asm, for

\mathrm{{\neg}I}

P \wedge Q

\mathrm{{\wedge}I}

3, 4

\bot

\mathrm{{\neg}E}

5, 2

\neg Q

\mathrm{{\neg}I}

4–6

(i) Derive. Step 2 postpones the disjunction. The premise waits for $\neg(P \vee Q)$ , which $\mathrm{RAA}$ on the goal supplies; step 4 then manufactures the clash partner $P \vee Q$ from line 3 by $\mathrm{\vee I}$ , a manufactured clash and not a detour.

\neg (P \vee Q) \to P

\neg (P \vee Q)

asm, for

\mathrm{RAA}

P

\mathrm{{{\to}}E}

1, 2

P \vee Q

\mathrm{{\vee}I}

\bot

\mathrm{{\neg}E}

4, 2

P \vee Q

\mathrm{RAA}

2–5

Read aloud: a statement whose failure would force one of its own sides holds.

(c) and (d), and (e) and (f), are look-alike pairs: each pair has the same premises and differs in the conclusion. (h) is (g) repaired by “not both”. (a) is a De Morgan look-alike with the wrong connective inside.

Exercise (B4: Derive ⊥, or make every member true, used later)

For each list, either derive $\bot$ from it, or give statements that make every member true at once.

(a) $P \to Q, \ Q \to \neg P, \ P$
(b) $P \vee Q, \ P \to \neg Q, \ Q \to \neg P$
(c) $\neg(P \to Q), \ Q \vee \neg P$
(d) $P \to (Q \wedge \neg Q)$
(e) $\neg(P \vee Q), \ P \vee (Q \wedge R)$
(f) $\neg(P \wedge Q), \ \neg(P \wedge \neg Q), \ \neg(\neg P \wedge Q)$

Solution.

(a) Derive $\bot$ : 4 $Q$ , $\mathrm{{\to}E}$ 1, 3; 5 $\neg P$ , $\mathrm{{\to}E}$ 2, 4; 6 $\bot$ , $\mathrm{\neg E}$ 3, 5.
(b) True at once. Take $P$ : “ $x > 0$ ”, $Q$ : “ $x < 0$ ”, at $x = 1$ : $P \vee Q$ is true; $\neg Q$ is true, so $P \to \neg Q$ is true; and $Q \to \neg P$ is true, since $Q$ is false.
(c) Derive $\bot$ .

1 $\neg (P \to Q)$
2 $Q \vee \neg P$
3 $Q$ asm, for $\mathrm{{\vee}E}$
4 $P$ asm, for $\mathrm{{{\to}}I}$
5 $Q$ $\mathrm{R}$ 3
6 $P \to Q$ $\mathrm{{{\to}}I}$ 4–5
7 $\bot$ $\mathrm{{\neg}E}$ 6, 1
8 $\neg P$ asm, for $\mathrm{{\vee}E}$
9 $P \to Q$ VI 8
10 $\bot$ $\mathrm{{\neg}E}$ 9, 1
11 $\bot$ $\mathrm{{\vee}E}$ 2, 3–7, 8–10
(d) True at once, with $P$ false ( $P$ : “ $0 = 1$ ”, any $Q$ ). A member that mentions a contradiction is not itself a clash: with $P$ false every member is true, so the claim that the list derives $\bot$ breaks.
(e) Derive $\bot$ .

1 $\neg (P \vee Q)$
2 $P \vee (Q \wedge R)$
3 $P$ asm, for $\mathrm{{\vee}E}$
4 $P \vee Q$ $\mathrm{{\vee}I}$ 3
5 $\bot$ $\mathrm{{\neg}E}$ 4, 1
6 $Q \wedge R$ asm, for $\mathrm{{\vee}E}$
7 $Q$ $\mathrm{{\wedge}E}$ 6
8 $P \vee Q$ $\mathrm{{\vee}I}$ 7
9 $\bot$ $\mathrm{{\neg}E}$ 8, 1
10 $\bot$ $\mathrm{{\vee}E}$ 2, 3–5, 6–9
(f) True at once, with $P$ and $Q$ both false ( $P$ : “ $1 > 2$ ”, $Q$ : “ $2 > 3$ ”): each conjunction has a false member, so each negation is true. Adding a fourth member $\neg(\neg P \wedge \neg Q)$ gives a list from which $\bot$ can be derived: the four exclude every way for $P$ and $Q$ to be. Use $\mathrm{LEM}$ on $P$ and, inside each case, on $Q$ ; each of the four cases builds the conjunction that one member negates, by $\mathrm{\wedge I}$ , and clashes with it.

Section 4.7 shows that a list made true at once, as in (b), (d) and (f), is consistent.

C. Going deeper

Exercise (C1: Exit check: the counterexample set, used later)

Let $\Gamma$ be the list $P \to (Q \vee R), \ Q \to S, \ R \to S$ .

(a) Write the counterexample set of $\Gamma \vdash P \to S$ .
(b) Show that it is inconsistent.
(c) What does Proposition 3.2.2 conclude? Give also a direct derivation of $\Gamma \vdash P \to S$ , and compare the two.
(d) Replace one premise so that the claim breaks, and break it.

Solution.

(a) $P \to (Q \vee R), \ Q \to S, \ R \to S, \ \neg(P \to S)$ .
(b) The goal is $\bot$ , and the clash partner $\neg(P \to S)$ is already on a line (Section 3.1), so aim at $P \to S$ .

1 $P \to (Q \vee R)$
2 $Q \to S$
3 $R \to S$
4 $\neg (P \to S)$
5 $P$ asm, for $\mathrm{{{\to}}I}$
6 $Q \vee R$ $\mathrm{{{\to}}E}$ 1, 5
7 $Q$ asm, for $\mathrm{{\vee}E}$
8 $S$ $\mathrm{{{\to}}E}$ 2, 7
9 $R$ asm, for $\mathrm{{\vee}E}$
10 $S$ $\mathrm{{{\to}}E}$ 3, 9
11 $S$ $\mathrm{{\vee}E}$ 6, 7–8, 9–10
12 $P \to S$ $\mathrm{{{\to}}I}$ 5–11
13 $\bot$ $\mathrm{{\neg}E}$ 12, 4
(c) By part (b) of the proposition, $\Gamma \vdash P \to S$ . The direct derivation is lines 1–3 and 5–12 of (b), renumbered: 11 lines. The route through the counterexample set adds the premise $\neg(P \to S)$ and one $\mathrm{\neg E}$ line, and gains nothing here. It pays when the goal gives step 2 nothing (a letter, or a disjunction with no side in hand), and then it is step 5.
(d) For instance, replace $R \to S$ by $R \to T$ . Take $P$ : “ $x > 0$ ”, $Q$ : “ $x > 5$ ”, $R$ : “ $x < 2$ ”, $S$ : “ $x > 3$ ”, $T$ : “ $x < 10$ ”, at $x = 1$ . $P$ and $R$ are true, so $Q \vee R$ and $P \to (Q \vee R)$ are true; $Q \to S$ is true, since $Q$ is false; $R \to T$ is true, since $T$ is true; and $P \to S$ is false, since $S$ is false. So every member of the new counterexample set is true. Any replacement that a choice of statements breaks is accepted.

Marking scheme. (10 points)

2: the counterexample set, with $\neg(P \to S)$ , not $\neg P \to S$ or $P \to \neg S$ .
3: the derivation of $\bot$ : $P \to S$ derived (by a box whose cases of $Q \vee R$ both end in $S$ , or by Example (Cases on a hypothesis are two implications) and Proposition 1.4.1), and $\mathrm{\neg E}$ outside every box.
2: the conclusion drawn by the proposition, and the direct derivation.
3: (d), a changed premise, with statements checked against all four members of the new counterexample set.

Fatal errors (0 for the step): $\bot$ written inside the box of $P$ and taken as the end; a “break” in (d) that leaves a premise false.

Exercise (C2: Challenge: Splitting an inconsistency, used later)

Let $\Gamma$ be a list and $\varphi$ a statement.

(a) Prove that if $\Gamma, \varphi$ and $\Gamma, \neg\varphi$ are both inconsistent, then so is $\Gamma$ .
(b) Deduce: if $\Gamma$ is consistent, then at least one of $\Gamma, \varphi$ and $\Gamma, \neg\varphi$ is consistent.
(c) Does (b) say which one?

Solution.

(a) Since $\Gamma, \varphi$ is inconsistent, Proposition 3.2.2 (a) gives $\Gamma \vdash \neg\varphi$ . Since $\Gamma, \neg\varphi$ is inconsistent, part (b) gives $\Gamma \vdash \varphi$ . So (iii) of Proposition 3.2.1 holds with $\chi$ the statement $\varphi$ , and $\Gamma$ is inconsistent.
(b) This is the contrapositive of (a): if both lists were inconsistent, $\Gamma$ would be.
(c) No. It says that one of the two lists is consistent and gives no way to tell which. Deciding that would need a way to show a list consistent, which this chapter does not have.

Section 4.10 (optional) adds statements to a consistent list one at a time, in exactly this way.

Marking scheme. (10 points)

4: (a) obtains $\Gamma \vdash \neg\varphi$ by part (a) of the proposition or $\Gamma \vdash \varphi$ by part (b), and combines it with the other inconsistency, directly (by Cut, Lemma 2.3.3 (b)) or by the other part.
3: (a) concludes by Proposition 3.2.1, by Lemma 2.3.3 (c) with one $\mathrm{\neg E}$ , or by Cut (Lemma 2.3.3 (b)).
2: (b) as the contrapositive.
1: (c) “no”.

Fatal error: (b) claimed to show that a particular list is consistent.