1.5 Or, Introduced

Sections 1.2 to 1.4 gave the rules for “and” and “implies”. With them we can take a conjunction apart, fire an implication on its hypothesis, and prove an implication by opening a box. This section starts on the third connective of the chapter, “or”. It gives the rule that proves a disjunction, $\mathrm{\vee I}$ , and a habit that goes with it: when the goal is a disjunction, commit to one of its sides only when that side is in hand. Near its end it meets a goal that the rules still cannot reach, and that goal is the question the next section answers.

1.5.1. Throwing information away on purpose

Suppose a proof has just shown that a real number $x$ satisfies $x > 0$ , and the definition it is checking asks for $x \ge 0$ . Every writer takes the step “so $x \ge 0$ ” without a pause. Look at what the step does. Section 1.1 noted that the symbol $\le$ hides a disjunction, so $x \ge 0$ is the statement $(x > 0) \vee (x = 0) .$ The step turns a statement into a disjunction of which it is one side.

The step loses something. “ $x > 0$ ” tells us that $x$ is not $0$ ; “ $x \ge 0$ ” no longer does. A proof that takes the step throws information away, and it does so on purpose: the definition asks for the weaker statement, and the stronger one is not in the form it asks for.

Remark. Convention: inequalities written out. When a rule has to see the disjunction inside $a \le b$ , a derivation writes it out as $(a < b) \vee (a = b)$ , and $a \ge b$ as $(a > b) \vee (a = b)$ : a checker compares symbols, so $\mathrm{\vee I}$ can write “ $x \ge 0$ ” from “ $x > 0$ ”, and $\mathrm{\vee E}$ can split on it, only in the written-out form. Otherwise $a \le b$ may stand in a derivation as one statement, and prose keeps the short forms.

The same move appears whenever a known fact has a disjunction as its hypothesis. School algebra says that if $a = 0$ or $b = 0$ , then $a \cdot b = 0$ . To use this on a product whose first factor we know to be $0$ , we must hand the fact its hypothesis, “ $a = 0$ or $b = 0$ ”. What we have is only “ $a = 0$ ”. So again the step goes from one side to the whole disjunction, and only then does the fact fire.

Both steps are instances of one rule. This section states it as a pattern, reads it in three bullets, and then uses it in two ways: when the goal is a disjunction, and when a premise needs one.

1.5.2. The rule of or-introduction

To prove a disjunction, it is enough to prove one of its two sides.

The rule is defined, like every rule since Section 1.2, by its schema (Definition 1.2.1). The Greek letters stand for arbitrary statements, and $i$ , $k$ for line numbers. The rule has two forms, one for each side, so it is printed as two schemas.

Definition 1.5.1 (Or-Introduction)

i

\varphi

k

\varphi \vee \psi

\mathrm{{\vee}I}

i

i

\varphi

k

\psi \vee \varphi

\mathrm{{\vee}I}

i

The rule given by these two schemas is called $\mathrm{\vee I}$ (or-introduction).

Schema: the two in the block above, one for each side.
Reading: one available line (an earlier line, not inside a box that has closed), cited alone; write a disjunction with that line’s statement as one whole side, left or right, and any statement as the other side: true or false, related or not.
Example: if line 4 is $x > 0$ , then “ $\mathrm{\vee I}$ 4” may write $(x > 0) \vee (x = 0)$ , or $(x = 0) \vee (x > 0)$ , or the silly but correct $(x > 0) \vee (x < -7)$ .

In mathematics “or” is inclusive (Section 1.1): $\varphi \vee \psi$ is true when $\varphi$ is true, when $\psi$ is true, and when both are. So $\varphi \vee \psi$ is true whenever $\varphi$ is, whatever $\psi$ says. The rule is this first clause read as a permission.

$\mathrm{\vee I}$ loses information, never truth.

Second readingEdge cases and near misses

The degenerate case is $\psi$ equal to $\varphi$ . From $P$ the rule writes $P \vee P$ , and then the two schemas give the same line. It is a legal step, and the next section uses the statement $P \vee P$ once.

The near misses, steps that look like $\mathrm{\vee I}$ and are not, are listed after the rule card at the end of this section.

Warning. Do not read “or” as “one but not both” when checking a step. From $x = 2$ , $\mathrm{\vee I}$ gives “ $x = 2$ or $x \le 5$ ”, although at $x = 2$ both sides are true. The step is correct: the disjunction is inclusive, and the rule never claims that the added side is false.

Warning. $\mathrm{\vee I}$ runs one way only. From $\varphi$ it gives $\varphi \vee \psi$ ; from $\varphi \vee \psi$ it gives nothing, and in general $\varphi$ does not follow from $\varphi \vee \psi$ at all. The phrase “in particular” belongs to $\mathrm{\wedge E}$ , not to “or”. For a concrete failure, let $x$ be a real number: “ $x \ge 0$ or $x < 0$ ” is true whatever $x$ is, and “in particular $x \ge 0$ ” is false at $x = -1$ .

Quick check. Let $x$ be a real number, and suppose line 1 of a derivation is $x = 2$ . Which of the following may line 2 be, justified by one application of $\mathrm{\vee I}$ to line 1?

(i) $(x = 2) \vee (x = 3)$ .
(ii) $(x = 3) \vee (x = 2)$ .
(iii) $(x = 2) \vee (1 = 0)$ .
(iv) $x \ge 2$ .

Solution.

(i) Yes, by the first schema, with $\psi$ replaced by $x = 3$ . (ii) Yes, by the second schema. (iii) Yes, by the first schema, with $\psi$ replaced by the false statement $1 = 0$ . The line is true, since its left side is, and it is useless; the rule allows it. (iv) Only once $x \ge 2$ is written out as $(x > 2) \vee (x = 2)$ , as the convention on inequalities above asks when a rule must see the disjunction. In that form it is an instance of the second schema, with $\varphi$ replaced by $x = 2$ . A checker who matches symbols sees the difference.

1.5.3. A disjunction as a goal

Section 1.2 asked two questions before writing any line: what is the goal’s main connective? (goal-directed reasoning, from the bottom up) and what are the available lines’ main connectives? (premise-directed reasoning, from the top down). Each rule so far added an answer. A conjunction as a goal splits into two subgoals, both needed ( $\mathrm{\wedge I}$ ); an implication as a goal opens a box ( $\mathrm{{\to}I}$ , Definition 1.4.1).

Now $\vee$ joins the list of goals. If the goal is $\varphi \vee \psi$ , its last line can be $\mathrm{\vee I}$ , and then the subgoal is $\varphi$ or $\psi$ : one of the two, of our choosing. That choice is new, and a wrong choice can leave us working towards a statement that does not follow from what we have. Suppose the premise is $x > 1$ and the goal is $(x > 3) \vee (x > 0)$ . Choose the left side, and the new goal $x > 3$ does not follow from the premise: try to break the step, and $x = 2$ does, since there $x > 1$ holds and $x > 3$ fails. Choose the right side, and $x > 0$ follows from $x > 1$ .

In the Givens/Goal table, $\mathrm{\vee I}$ replaces the goal $\varphi \vee \psi$ by the side you choose.

So the goal-directed step for $\vee$ comes with a caution:

Postpone a disjunction: choose a side of a goal $\varphi \vee \psi$ only when that side is in hand.

“In hand” means that the side stands on an available line. Until then, work from the premises: take conjunctions apart, fire implications, open the boxes the goal asks for, and look at what appears. When one side of the goal turns up, the choice has been made for us.

Quick check. Let $x$ be a real number. The premise is $0 < x < 1$ and the goal is $(x < 0) \vee (x < 2)$ . Which side should $\mathrm{\vee I}$ take, and why not the other?

Solution. The right side, $x < 2$ : it follows from $x < 1$ , the right half of the premise. The left side $x < 0$ does not follow: at $x = \tfrac12$ the premise holds and $x < 0$ fails.

A side chosen too early is worth watching once, all the way to the point where the search stalls, and then once more done right.

Example (A side chosen too early)

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

Solution. The box. The goal is an implication, so we open a box with its hypothesis $P \wedge Q$ , and the goal inside is $S \vee R$ . The first picture shows the box with its goal at the bottom, and the line that will close it, not yet justified; line 2 records the plan, “asm, for $\mathrm{{\to}I}$ ”.

P \to R

P \wedge Q

asm, for

\mathrm{{{\to}}I}

\vdots

S \vee R

(P \wedge Q) \to (S \vee R)

P \to R

P \wedge Q

asm, for

\mathrm{{{\to}}I}

\vdots

S

S \vee R

\mathrm{{\vee}I}

(P \wedge Q) \to (S \vee R)

The early choice. $S$ is the left side of the goal, so suppose we aim at it at once: line 5 becomes “ $S \vee R$ , $\mathrm{\vee I}$ 4”, and line 4, $S$ , is the new subgoal (the second picture). Now the search stalls. Nothing mentions $S$ except the goal: no premise, no assumption, no part of either.

Try to break the subgoal. Let $x$ be a real number, and take $P$ : “ $x > 1$ ”, $Q$ : “ $x > 0$ ”, $R$ : “ $x^2 > x$ ”, $S$ : “ $x > 5$ ”. The premise $P \to R$ holds for every $x$ : if $x > 1$ , then $x^2 = x \cdot x > x$ . At $x = 2$ the assumption $P \wedge Q$ is true and $S$ is false. So $S$ does not follow from the lines in hand. The goal was not at fault, since at $x = 2$ its right side $R$ is true ( $4 > 2$ ); the choice was.

Redone. Go back to the choice and postpone it. Work from the lines in hand: $\mathrm{\wedge E}$ takes $P$ out of the assumption, the premise fires on it, and $R$ , the right side of the goal, is in hand. Only now does $\mathrm{\vee I}$ choose a side.

P \to R

P \wedge Q

asm, for

\mathrm{{{\to}}I}

P

\mathrm{{\wedge}E}

R

\mathrm{{{\to}}E}

1, 3

S \vee R

\mathrm{{\vee}I}

(P \wedge Q) \to (S \vee R)

\mathrm{{{\to}}I}

2–5

Line 5 uses the second schema, with $R$ on the right. A stalled branch is abandoned, not defended: go back to the last choice and make it later.

Quick check. In Example (A side chosen too early), which side would $\mathrm{\vee I}$ take if the premise were $P \to S$ instead?

Solution. The left side, $S$ : with the premise $P \to S$ , the lines $\mathrm{\wedge E}$ and $\mathrm{{\to}E}$ would put $S$ in hand at line 4. The postponing is the same; the choice is made when a side appears.

The habit of this section as a picture:

$Diagram. Labels: no, a new line, nothing new, goal varphi vee psi, is varphi or psi \on an available line?, veeI with that side, work from the lines in hand:\\wedgeE , to E, the boxes the goal asks for, still stuck: split an available\disjunction (next section)$

Here are four derivations, in order of difficulty. Each Idea says, for each rule, whether it was chosen by the goal or by a premise.

Example (Derivations with or-introduction)

Show that:

(a) $P \vdash P \vee Q$ , and $P \vdash Q \vee P$ ;
(b) $P \wedge Q \vdash P \vee Q$ ;
(c) $P \to Q \vdash P \to (Q \vee R)$ ;
(d) $(P \wedge Q) \to R \vdash P \to (Q \to (R \vee S))$ .

Solution.

(a) Idea. The goal is a disjunction, and one of its sides, $P$ , is the premise: in hand from the start. The only choice is which schema, and the goal decides it: $P$ sits on the left of $P \vee Q$ and on the right of $Q \vee P$ .
1 $P$
2 $P \vee Q$ $\mathrm{{\vee}I}$ 1
1 $P$
2 $Q \vee P$ $\mathrm{{\vee}I}$ 1

In the first, line 2 is the first schema with $\varphi$ replaced by $P$ and $\psi$ by $Q$ ; in the second, it is the second schema with the same replacement. The letter $Q$ appears in no premise. That is the Reading’s “any statement” at work.
(b) Idea. The goal $P \vee Q$ is a disjunction, and neither side stands on a line yet, so we postpone it. Premise-directed: the premise’s main connective is $\wedge$ , so $\mathrm{\wedge E}$ takes it apart. After that, both sides of the goal are in hand, and either choice finishes.
1 $P \wedge Q$
2 $P$ $\mathrm{{\wedge}E}$ 1
3 $P \vee Q$ $\mathrm{{\vee}I}$ 2
1 $P \wedge Q$
2 $Q$ $\mathrm{{\wedge}E}$ 1
3 $P \vee Q$ $\mathrm{{\vee}I}$ 2

The left derivation chose the left side (first schema); the right one chose the right side (second schema). Both are correct, and the choice was free precisely because both sides were in hand. That will not usually be so.
(c) Idea. The goal’s main connective is the outer $\to$ ; the $\vee$ sits inside its conclusion. Goal-directed: open a box with the hypothesis $P$ , and the new goal inside it is $Q \vee R$ , a disjunction, so we postpone it. Premise-directed: the premise $P \to Q$ is an implication whose hypothesis $P$ is now on a line, so $\mathrm{{\to}E}$ fires and gives $Q$ . The left side of the goal is in hand; $\mathrm{\vee I}$ takes it, and $\mathrm{{\to}I}$ closes the box. The pictures show the box opened with its goal at the bottom, and then the box with the side $Q$ written; only the justification of line 4, marked “?”, is left.
1 $P \to Q$
2 $P$ asm, for $\mathrm{{{\to}}I}$
$\vdots$
4 $Q \vee R$
5 $P \to (Q \vee R)$ $\mathrm{{{\to}}I}$ 2–4
1 $P \to Q$
2 $P$ asm, for $\mathrm{{{\to}}I}$
3 $Q$ $\mathrm{{{\to}}E}$ 1, 2
4 $Q \vee R$ ?
5 $P \to (Q \vee R)$ $\mathrm{{{\to}}I}$ 2–4

1 $P \to Q$
2 $P$ asm, for $\mathrm{{{\to}}I}$
3 $Q$ $\mathrm{{{\to}}E}$ 1, 2
4 $Q \vee R$ $\mathrm{{\vee}I}$ 3
5 $P \to (Q \vee R)$ $\mathrm{{{\to}}I}$ 2–4

Line 3 cites line 1, which lies in no box, and line 2, the assumption of the box that contains line 3. Line 4 is a line of the box itself, so $\mathrm{{\to}I}$ may cite the box $2\text{–}4$ .
(d) Idea. The goal has two arrows at the top of its structure, $P \to (Q \to \cdots)$ , so, as in Proposition 1.4.2, we open two nested boxes, first $P$ , then $Q$ ; the inner one will close first. The innermost goal is $R \vee S$ : postpone. Premise-directed: the only line that mentions $R$ is the premise $(P \wedge Q) \to R$ . Its hypothesis is $P \wedge Q$ , which is not on any line, but both of its halves are: the two assumptions. So $\mathrm{\wedge I}$ builds it, $\mathrm{{\to}E}$ fires, and $R$ is in hand. Then $\mathrm{\vee I}$ , and the two boxes close. In the pictures, the two boxes are open with the innermost goal at the bottom; then lines 4 and 5 are written, and only the justification of line 6 is left.

(P \wedge Q) \to R

P

asm, for

\mathrm{{{\to}}I}

Q

asm, for

\mathrm{{{\to}}I}

\vdots

R \vee S

Q \to (R \vee S)

\mathrm{{{\to}}I}

3–6

P \to (Q \to (R \vee S))

\mathrm{{{\to}}I}

2–7

(P \wedge Q) \to R

P

asm, for

\mathrm{{{\to}}I}

Q

asm, for

\mathrm{{{\to}}I}

P \wedge Q

\mathrm{{\wedge}I}

2, 3

R

\mathrm{{{\to}}E}

1, 4

R \vee S

Q \to (R \vee S)

\mathrm{{{\to}}I}

3–6

P \to (Q \to (R \vee S))

\mathrm{{{\to}}I}

2–7

(P \wedge Q) \to R

P

asm, for

\mathrm{{{\to}}I}

Q

asm, for

\mathrm{{{\to}}I}

P \wedge Q

\mathrm{{\wedge}I}

2, 3

R

\mathrm{{{\to}}E}

1, 4

R \vee S

\mathrm{{\vee}I}

Q \to (R \vee S)

\mathrm{{{\to}}I}

3–6

P \to (Q \to (R \vee S))

\mathrm{{{\to}}I}

2–7

This derivation uses every rule of the chapter so far except $\mathrm{\wedge E}$ and $\mathrm{R}$ . Line 4 cites line 2, from the outer box, which is still open at line 4. Line 5 cites line 1 from inside two boxes: a line in no box is available everywhere below it. Line 7 is a line of the outer box itself, which is why $\mathrm{{\to}I}$ at line 8 may cite $2\text{–}7$ .

Warning. Choosing the wrong side of a disjunctive goal too early can leave a goal that does not follow. Derivation (c) is where postponing pays. Had we committed at once, inside the box, to the goal’s right side, planning to reach $Q \vee R$ from $R$ , the box would need $R$ itself, from the premise $P \to Q$ and the assumption $P$ alone. With $x$ a real number, $P$ : “ $x > 2$ ”, $Q$ : “ $x > 1$ ” and $R$ : “ $x > 3$ ”, the premise and the assumption hold at $x = 2.5$ , and $R$ fails there, so $R$ does not follow. Keep the goal as the whole disjunction until one side appears on a line.

1.5.4. Manufacturing a hypothesis

In every derivation so far, $\mathrm{\vee I}$ produced the goal, or the goal of a box. It has a second use. A premise whose hypothesis is a disjunction can fire only when that disjunction stands on a line, exactly as written (the matching clause of Definition 1.3.1). If one side of it is in hand, $\mathrm{\vee I}$ builds the whole hypothesis.

Example (A disjunctive hypothesis splits into two implications)

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

Solution. Idea. Goal-directed: the goal is a conjunction, so $\mathrm{\wedge I}$ splits it into two subgoals, $P \to R$ and $Q \to R$ , and each is an implication, so each gets its own box. Inside the box of $P$ , the goal is $R$ . Premise-directed: the only line that mentions $R$ is the premise, and $\mathrm{{\to}E}$ on it needs its hypothesis $P \vee Q$ on a line. We have $P$ , one side of that hypothesis. So $\mathrm{\vee I}$ manufactures $P \vee Q$ , and the premise fires. Here $\mathrm{\vee I}$ is chosen not because the goal is a disjunction (the goal is $R$ ) but because a premise’s hypothesis is one. The box of $Q$ is the same, with the other schema. In the pictures, both boxes are open with their goals at the bottom; then the $\mathrm{\vee I}$ lines that manufacture the hypothesis are written, and only the $\mathrm{{\to}E}$ lines are left.

(P \vee Q) \to R

P

asm, for

\mathrm{{{\to}}I}

\vdots

R

P \to R

\mathrm{{{\to}}I}

2–4

Q

asm, for

\mathrm{{{\to}}I}

\vdots

R

Q \to R

\mathrm{{{\to}}I}

6–8

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

\mathrm{{\wedge}I}

5, 9

(P \vee Q) \to R

P

asm, for

\mathrm{{{\to}}I}

P \vee Q

\mathrm{{\vee}I}

R

P \to R

\mathrm{{{\to}}I}

2–4

Q

asm, for

\mathrm{{{\to}}I}

P \vee Q

\mathrm{{\vee}I}

R

Q \to R

\mathrm{{{\to}}I}

6–8

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

\mathrm{{\wedge}I}

5, 9

(P \vee Q) \to R

P

asm, for

\mathrm{{{\to}}I}

P \vee Q

\mathrm{{\vee}I}

R

\mathrm{{{\to}}E}

1, 3

P \to R

\mathrm{{{\to}}I}

2–4

Q

asm, for

\mathrm{{{\to}}I}

P \vee Q

\mathrm{{\vee}I}

R

\mathrm{{{\to}}E}

1, 7

Q \to R

\mathrm{{{\to}}I}

6–8

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

\mathrm{{\wedge}I}

5, 9

Line 3 uses the first schema of Definition 1.5.1 ( $P$ on the left), line 7 the second ( $Q$ on the right). Both produce the same statement $P \vee Q$ , the one the premise asks for. The two boxes are separate: the second opens after the first has closed, and nothing in it cites a line of the first. Line 10 cites lines 5 and 9, which lie in no box.

The product example below, and several exercises, use $\mathrm{\vee I}$ the same way. Weakening is how a strong fact is fed to a rule, or a theorem, that asks for a weaker one.

In mathematical terms, the derivation says that a theorem with a hypothesis “ $P$ or $Q$ ” splits into two theorems. Let $x$ be a real number, and suppose we know “if $x \ge 0$ , then $x^3 \ge 0$ ”, that is, “if $x > 0$ or $x = 0$ , then $x^3 \ge 0$ ”. Then we know “if $x > 0$ , then $x^3 \ge 0$ ” and “if $x = 0$ , then $x^3 \ge 0$ ”. The way back, from the two implications to the single one with the disjunctive hypothesis, needs the rule of the next section; it is derived there.

Quick check. In the derivation of Example (A disjunctive hypothesis splits into two implications), line 3 could not have been skipped by letting line 4 cite line 2 directly, as “ $R$ — $\mathrm{{\to}E}$ 1, 2”. Why not?

Solution. $\mathrm{{\to}E}$ (Definition 1.3.1) needs the implication on one cited line and its hypothesis, exactly, on the other. The hypothesis of line 1 is $P \vee Q$ , and line 2 is $P$ , which does not match it symbol for symbol. Line 3 writes the hypothesis out, and only then does line 1 fire.

1.5.5. A goal we cannot reach yet

The most obvious fact about “or” is that the order of its sides does not matter: $P \vee Q \vdash Q \vee P$ . Try to derive it with the rules so far.

The goal $Q \vee P$ is a disjunction, so we postpone it and look at the premise. Its main connective is $\vee$ , and no rule so far takes a disjunction apart. $\mathrm{\wedge E}$ needs a conjunction and $\mathrm{{\to}E}$ an implication; $\mathrm{\wedge I}$ , $\mathrm{\vee I}$ , and $\mathrm{R}$ may cite $P \vee Q$ , but only to copy it or to build something larger around it. So the premise gives us nothing, and working from it alone, neither side of the goal ever comes into hand.

We can get this far, though. Each side of the premise, assumed in a box, leads to the goal:

P \vee Q

P

asm, for

\mathrm{{{\to}}I}

Q \vee P

\mathrm{{\vee}I}

P \to (Q \vee P)

\mathrm{{{\to}}I}

2–3

Q

asm, for

\mathrm{{{\to}}I}

Q \vee P

\mathrm{{\vee}I}

Q \to (Q \vee P)

\mathrm{{{\to}}I}

5–6

This derivation is correct, but it shows $P \vee Q \vdash Q \to (Q \vee P)$ , and line 1 is never cited. (A derivation need not use every premise, Definition 1.2.3.) What we would like is to put the three lines 1, 4, and 7 together: one of $P$ , $Q$ holds, and either one leads to $Q \vee P$ ; so $Q \vee P$ . That is a proof by cases, and none of the rules so far performs it. With them we cannot find a derivation of $P \vee Q \vdash Q \vee P$ .

The missing move is to use a disjunction, as $\mathrm{\wedge E}$ uses a conjunction and $\mathrm{{\to}E}$ uses an implication. The next section gives the rule that does this, and with it the six-line derivation that this attempt lacks.

1.5.6. Derive it or break it

From here on, some exercises list claims $\Gamma \vdash \varphi$ without saying which hold. For each, either give a derivation, or break the claim: find statements that make its counterexample set $\Gamma, \neg\varphi$ (Definition 1.1.3) true all at once.

For instance, $P \wedge (Q \vee R) \vdash Q$ breaks. Let $x$ be a real number, and take $P$ : “ $x > 0$ ”, $Q$ : “ $x > 2$ ”, $R$ : “ $x < 3$ ”. At $x = 1$ the set $P \wedge (Q \vee R)$ , $\neg Q$ is true: $1 > 0$ , $1 < 3$ , and $1 > 2$ fails.

A claim can also be of neither kind yet. $P \vee Q \vdash Q \vee P$ cannot be broken: if $P \vee Q$ is true, one of its sides is, and that side makes $Q \vee P$ true. And with the rules so far no derivation of it has been found: the attempt in “A goal we cannot reach yet” stalls, and the claim waits for the next section’s rule. The lists in this section’s exercises contain only claims that the rules so far settle.

1.5.7. How this looks in a mathematical proof

In written mathematics $\mathrm{\vee I}$ is almost always silent. Here are the two steps of the opening, written out as derivations.

Example (A product with a zero factor)

Let $a$ and $b$ be real numbers, and take as known the school fact “if $a = 0$ or $b = 0$ , then $a \cdot b = 0$ ”. Prove that if $a = 0$ , then $a \cdot b = 0$ , naming the rule behind each step. Then write the step from $x > 0$ to $x \ge 0$ as a derivation.

Solution. The goal is an implication, so the proof supposes $a = 0$ (a box). Inside, the fact needs its hypothesis “ $a = 0$ or $b = 0$ ”, which $\mathrm{\vee I}$ manufactures, as in Example (A disjunctive hypothesis splits into two implications). In prose, with each step’s rule in brackets:

Suppose $a = 0$ . Then $a = 0$ or $b = 0$ $[\mathrm{\vee I}]$ . So, by the school fact, $a \cdot b = 0$ $[\mathrm{{\to}E}]$ . Hence, if $a = 0$ , then $a \cdot b = 0$ $[\mathrm{{\to}I}]$ .

As a derivation, with the school fact as the premise:

(a = 0 \vee b = 0) \to a \cdot b = 0

a = 0

asm, for

\mathrm{{{\to}}I}

a = 0 \vee b = 0

\mathrm{{\vee}I}

a \cdot b = 0

\mathrm{{{\to}}E}

1, 3

a = 0 \to a \cdot b = 0

\mathrm{{{\to}}I}

2–4

A written proof would say “if $a = 0$ , then $a \cdot b = 0$ by the fact”, and leave out the words “ $a = 0$ or $b = 0$ ”. The derivation shows what that sentence leaves out: a box, a weakening, and one use of the fact.

For the second step, let $x$ be a real number with $x > 0$ . Written out, $x \ge 0$ is $(x > 0) \vee (x = 0)$ , and the step is one application of the first schema:

x > 0

(x > 0) \vee (x = 0)

\mathrm{{\vee}I}

Line 2 is $x \ge 0$ , written out.

Every “so $x \ge 0$ ” after $x > 0$ , every “so $\left| t \right| \le 1$ ” after $\left| t \right| < 1$ , and every “so $n$ is even or $n > 5$ ” after “ $n$ is even” is this rule. A reader who checks a proof line by line should see it, even where the writer did not name it. It is a step that never leads from a truth to a falsehood, and it is also the step that explains why a conclusion can say less than the proof knew.

1.5.8. The rule card

Before the card, the new rule at work on statements larger than single letters. The schema sees only the whole cited line; how much is inside it does not matter.

Example (Instances of

\mathrm{\vee I}

)

Schema	$\varphi$	$\psi$	Cited line	New line
first	$P \to Q$	$R \wedge \neg S$	$P \to Q$	$(P \to Q) \vee (R \wedge \neg S)$
second	$P \vee Q$	$P \wedge \neg R$	$P \vee Q$	$(P \wedge \neg R) \vee (P \vee Q)$
second	$(P \wedge Q) \to R$	$\neg R$	$(P \wedge Q) \to R$	$\neg R \vee ((P \wedge Q) \to R)$

Not an instance. From $P \vee Q$ , the line $P \vee (Q \vee R)$ is not written by $\mathrm{\vee I}$ : the rule adds a side to the whole cited line, giving $(P \vee Q) \vee R$ or $R \vee (P \vee Q)$ ; it never reaches inside.

The card grows by one row. Shape shows the given lines (or box), then the new line.

Rule	Shape	You write	Lean
$\mathrm{\wedge I}$	$\varphi$ , $\psi$ $\Longrightarrow$ $\varphi \wedge \psi$	“We show $P$ , and we show $Q$ .”	`constructor`
$\mathrm{\wedge E}$	$\varphi \wedge \psi$ $\Longrightarrow$ $\varphi$ (or $\psi$ )	“In particular, $P$ .”	`h.1` (and `h.2`)
$\mathrm{{\to}E}$	$\varphi \to \psi$ , $\varphi$ $\Longrightarrow$ $\psi$	“Since $P$ implies $Q$ , and $P$ holds, $Q$ .”	`exact h hp`
$\mathrm{{\to}I}$	box $\varphi$ … $\psi$ $\Longrightarrow$ $\varphi \to \psi$	“Assume $P$ . … Hence $Q$ .”	`intro hp`
$\mathrm{R}$	$\varphi$ (available) $\Longrightarrow$ $\varphi$ , copied	“As shown above, $P$ .”	`exact hp`
$\mathrm{\vee I}$	$\varphi$ $\Longrightarrow$ $\varphi \vee \psi$ (or $\psi \vee \varphi$ )	“So $P$ or $Q$ holds.”	`left` (or `Or.inl hp`); `right`

The phrase is different from the “in particular” of $\mathrm{\wedge E}$ on purpose. “In particular” announces that a part is being taken out of something bigger; “so $P$ or $Q$ ” announces that something bigger, and weaker, is being built.

Warning (Not allowed: $\mathrm{\vee I}$ ). Each step is offered as one application of $\mathrm{\vee I}$ ; each breaks the Reading of the rule where shown.

“ $P$ from $P \vee Q$ ”: it runs the rule backwards. The cited line is a side of the new line, never the other way round.
“ $P \wedge Q$ from $P$ ”: the new line must be a disjunction.
“ $Q \vee P$ from $P \vee Q$ ”: the cited line must be one whole side of the new line.
“ $P \vee (Q \vee R)$ from $P \vee Q$ ”: the rule never reaches inside the cited line.
“ $x \ge 0$ from $x > 0$ , as written”: a checker compares symbols. Write $x \ge 0$ out first, as the convention on inequalities at the start of this section asks.

Quick check. Line 3 is $Q$ . Which of $Q \vee (P \wedge R)$ , $(P \wedge R) \vee Q$ , $Q \vee Q$ , $Q \wedge Q$ may “ $\mathrm{\vee I}$ 3” write?

Solution. The first three. The first is the first schema and the second the second schema, with $\psi$ replaced by $P \wedge R$ ; the third is either schema, with $\psi$ replaced by $Q$ itself. $Q \wedge Q$ is a conjunction, written by $\mathrm{\wedge I}$ 3, 3.

Remark (Looking ahead). Chapter 4 proves that a claim that breaks has no derivation, with any of the rules of Chapters 1 and 2, and that a claim that cannot be broken has a derivation with them.

1.5.9. Exercises

A. Check your understanding

Exercise (A1)

(a) Write the two schemas of Definition 1.5.1 from memory, and say which letter in them may stand for a statement that appears in no earlier line.
(b) Which of the following sentences, taken from proofs about a real number $x$ or real numbers $a$ , $b$ , use $\mathrm{\vee I}$ ? For each of the others, name the rule it uses.
- “We have $x < 3$ , so $x \le 3$ .”
- “We found that $a = 0$ . So $a = 0$ or $b = 0$ , and therefore $a \cdot b = 0$ .”
- “Since $0 < x < 1$ , in particular $x < 1$ .”
- “Since $\left| x - 2 \right| < 1$ implies $1 < x < 3$ , and $\left| x - 2 \right| < 1$ , we get $1 < x < 3$ .”
(c) True or false, with a reason: $\mathrm{\vee I}$ may introduce a side that is false.
(d) To show $Q, \ (P \vee Q) \to (Q \to R) \vdash R$ , which rule writes the first line after the premises, and what is that line? Why is that rule used, although the goal is not a disjunction?

Solution.

(a) From a line $i$ holding $\varphi$ , a line $k$ holding $\varphi \vee \psi$ , justified “ $\mathrm{\vee I}$ $i$ ”; and, from the same line, a line $k$ holding $\psi \vee \varphi$ , with the same justification (Definition 1.5.1). The letter $\psi$ appears in no given line: it may be any statement.
(b) The first uses $\mathrm{\vee I}$ : $x \le 3$ is $(x < 3) \vee (x = 3)$ , and its left side is in hand. The second uses $\mathrm{\vee I}$ to build “ $a = 0$ or $b = 0$ ” from its left side, and then $\mathrm{{\to}E}$ on the fact about products, as in Example (A product with a zero factor). The third uses $\mathrm{\wedge E}$ : $0 < x < 1$ is $(0 < x) \wedge (x < 1)$ , and the sentence takes out its right half. The fourth uses $\mathrm{{\to}E}$ , with the implication first and its hypothesis second.
(c) True. The added side $\psi$ may be any statement, false ones included, as in the line $(x = 2) \vee (1 = 0)$ of the Quick check after the definition. The new line is still true whenever the cited line is, because “or” is inclusive: one true side is enough.
(d) The rule is $\mathrm{\vee I}$ , by its second schema, and line 3 is $P \vee Q$ , from line 1. It is used because a premise’s hypothesis is a disjunction. The goal $R$ occurs only in the premise $(P \vee Q) \to (Q \to R)$ , and $\mathrm{{\to}E}$ fires on that premise only when $P \vee Q$ itself stands on a line. Only its right side $Q$ is on a line, and $\mathrm{\vee I}$ turns it into $P \vee Q$ . Then $Q \to R$ follows by $\mathrm{{\to}E}$ 2, 3, and $R$ by $\mathrm{{\to}E}$ 4, 1. The move is the one of Example (A disjunctive hypothesis splits into two implications), where $\mathrm{\vee I}$ builds a premise’s hypothesis.

Exercise (A2: Drill)

Each part takes a line or two. The parts run from single steps, through a missing line and a justification column, to whole derivations. Let $x$ be a real number and $n$ an integer.

(a) Line 2 is $(P \to Q) \wedge R$ . Write two lines that “ $\mathrm{\vee I}$ 2” can give, one by each schema.
(b) Line 6 is $(R \wedge S) \vee (P \to Q)$ , justified “ $\mathrm{\vee I}$ 4”. What can line 4 be?
(c) Justify each line: 1 $P \wedge Q$ , premise; 2 $R$ , premise; 3 $Q$ ; 4 $Q \vee R$ ; 5 $(Q \vee R) \wedge R$ ; 6 $S \vee ((Q \vee R) \wedge R)$ .
(d) Line 1 is $x = 5$ . Which of these may be written as “ $\mathrm{\vee I}$ 1”? (i) $(x = 5) \vee (x = 6)$ ; (ii) $(x > 4) \vee (x = 5)$ ; (iii) $x \ge 5$ , as written; (iv) $(x = 5) \wedge (x \ge 0)$ .
(e) Line 1 is $P \wedge Q$ . Is “ $P \vee Q$ — $\mathrm{\vee I}$ 1” legal?
(f) Line 1 is $Q \vee P$ . Is “ $P \vee Q$ — $\mathrm{\vee I}$ 1” legal?
(g) Is “ $x > 0$ , so $x \ge 0$ ” one step of $\mathrm{\vee I}$ ?
(h) Line 4 is $P \wedge Q$ . Is “ $(P \vee R) \wedge Q$ — $\mathrm{\vee I}$ 4” correct? If not, how many lines does it take?
(i) “We have $n = 4$ . So $n$ is even or $n > 10$ .” Which steps does this sentence take?
(j) The premise is $x < -1$ and the goal is $(x < -5) \vee (x < 0)$ . Which side should $\mathrm{\vee I}$ take?
(k) Derive $P \vdash (P \vee Q) \wedge (R \vee P)$ .
(l) Derive $P \wedge Q \vdash Q \vee R$ .
(m) Derive $P \to Q \vdash P \to (R \vee Q)$ .
(n) Derive $(P \vee Q) \to R, \ Q \vdash R$ .
(o) Derive $P \to (Q \wedge R) \vdash P \to (S \vee R)$ .

Solution.

(a) $((P \to Q) \wedge R) \vee S$ by the first schema and $S \vee ((P \to Q) \wedge R)$ by the second, with any statement for $S$ .
(b) $R \wedge S$ (first schema) or $P \to Q$ (second schema): line 4 is one whole side of line 6.
(c) 3 $\mathrm{\wedge E}$ 1; 4 $\mathrm{\vee I}$ 3 (first schema); 5 $\mathrm{\wedge I}$ 4, 2; 6 $\mathrm{\vee I}$ 5 (second schema).
(d)
- (i) Yes, by the first schema. (ii) Yes, by the second schema: $x = 5$ is the right side. (iii) No: as written, $x \ge 5$ is one statement. Written out as $(x > 5) \vee (x = 5)$ , it is the second schema. (iv) No: the new line is not a disjunction.
(e) No: $P \wedge Q$ is not a side of $P \vee Q$ . From line 1, $\mathrm{\vee I}$ could write $(P \wedge Q) \vee R$ .
(f) No: $Q \vee P$ is not a whole side of $P \vee Q$ .
(g) Yes, once $x \ge 0$ is written out as $(x > 0) \vee (x = 0)$ : it is the first schema.
(h) No. The new line of $\mathrm{\vee I}$ is a disjunction with line 4 as one whole side; this line is a conjunction, and it reaches inside line 4. It takes four lines: 5 $P$ , $\mathrm{\wedge E}$ 4; 6 $Q$ , $\mathrm{\wedge E}$ 4; 7 $P \vee R$ , $\mathrm{\vee I}$ 5; 8 $(P \vee R) \wedge Q$ , $\mathrm{\wedge I}$ 7, 6.
(i) Two steps: algebra ( $4 = 2 \cdot 2$ , so $n$ is even), then $\mathrm{\vee I}$ . From “ $n = 4$ ” itself, $\mathrm{\vee I}$ gives only “ $n = 4$ or …”.
(j) The right side, $x < 0$ , which follows from $x < -1$ . The left side fails at $x = -2$ , where the premise holds and $x < -5$ does not.
(k) 2 $P \vee Q$ , $\mathrm{\vee I}$ 1; 3 $R \vee P$ , $\mathrm{\vee I}$ 1; 4 $(P \vee Q) \wedge (R \vee P)$ , $\mathrm{\wedge I}$ 2, 3.
(l) 2 $Q$ , $\mathrm{\wedge E}$ 1; 3 $Q \vee R$ , $\mathrm{\vee I}$ 2.
(m) A box opened with $P$ : 2 $P$ , assumption, for $\mathrm{{\to}I}$ ; 3 $Q$ , $\mathrm{{\to}E}$ 1, 2; 4 $R \vee Q$ , $\mathrm{\vee I}$ 3; then 5 $P \to (R \vee Q)$ , $\mathrm{{\to}I}$ 2–4.
(n) 3 $P \vee Q$ , $\mathrm{\vee I}$ 2; 4 $R$ , $\mathrm{{\to}E}$ 1, 3.
(o) A box opened with $P$ : 2 $P$ , assumption, for $\mathrm{{\to}I}$ ; 3 $Q \wedge R$ , $\mathrm{{\to}E}$ 1, 2; 4 $R$ , $\mathrm{\wedge E}$ 3; 5 $S \vee R$ , $\mathrm{\vee I}$ 4; then 6 $P \to (S \vee R)$ , $\mathrm{{\to}I}$ 2–5.

B. Practice

Exercise (B1: Committing to a side)

Show that $P \wedge (Q \to R) \vdash Q \to (R \vee S)$ , and that $P \vdash (Q \vee P) \vee R$ . For each derivation, say at which line you committed to a side of a disjunctive goal, and why that was safe.

Solution. For the first, the goal is an implication, so open a box with $Q$ ; the goal inside is $R \vee S$ , which we postpone. Premise-directed, $\mathrm{\wedge E}$ takes out $Q \to R$ , and $\mathrm{{\to}E}$ fires on the assumption $Q$ .

P \wedge (Q \to R)

Q

asm, for

\mathrm{{{\to}}I}

Q \to R

\mathrm{{\wedge}E}

R

\mathrm{{{\to}}E}

3, 2

R \vee S

\mathrm{{\vee}I}

Q \to (R \vee S)

\mathrm{{{\to}}I}

2–5

We committed at line 5, to the left side $R$ , and only after line 4 had put $R$ on a line. The other conjunct of the premise, $P$ , is never used.

For the second, the goal $(Q \vee P) \vee R$ is a disjunction whose left side, $Q \vee P$ , is itself a disjunction, and $P$ is one side of that.

P

Q \vee P

\mathrm{{\vee}I}

(Q \vee P) \vee R

\mathrm{{\vee}I}

Line 2 uses the second schema ( $P$ on the right) and line 3 the first, with $\varphi$ replaced by $Q \vee P$ . We committed twice, at lines 2 and 3, and both times the side was in hand: at line 2 the side $P$ was the premise, and at line 3 the side $Q \vee P$ was line 2. Choosing the side $R$ at the outer level would have left the subgoal $R$ , which does not follow from $P$ : take $P$ true and $R$ false.

Exercise (B2: The last line)

A search for $P \to Q, \ Q \to R \vdash P \to (S \vee R)$ has reached the stage below; only the last line is missing. Name the move, then complete it.

P \to Q

Q \to R

P

asm, for

\mathrm{{{\to}}I}

Q

\mathrm{{{\to}}E}

1, 3

R

\mathrm{{{\to}}E}

2, 4

S \vee R

\mathrm{{\vee}I}

\;\textbf{?}

Solution. The move is the one read off the goal: an implication goal opens a box with its hypothesis, and the box is closed by $\mathrm{{\to}I}$ once its last line is the implication’s conclusion. The box opened with $P$ at line 3, and its last line, line 6, is $S \vee R$ , the conclusion of the goal. So line 7 closes the box:

P \to Q

Q \to R

P

asm, for

\mathrm{{{\to}}I}

Q

\mathrm{{{\to}}E}

1, 3

R

\mathrm{{{\to}}E}

2, 4

S \vee R

\mathrm{{\vee}I}

P \to (S \vee R)

\mathrm{{{\to}}I}

3–6

Line 7 cites the box as the range $3\text{–}6$ , not its lines one by one. Inside the box, the disjunction $S \vee R$ was postponed until $R$ came into hand at line 5; the side in hand was the right one, so line 6 uses the second schema.

Exercise (B3: A theorem with a weaker hypothesis)

Let $x$ be a real number, and take as known the school fact “if $x \ge 1$ , then $x^2 \ge x$ ”. Prove that if $x > 1$ , then $x^2 \ge x$ . Write the proof as a derivation whose premise is the school fact, with $x \ge 1$ written out as a disjunction, and then as two or three sentences of prose.

Solution. Written out, $x \ge 1$ is $(x > 1) \vee (x = 1)$ , so the premise is an implication whose hypothesis is a disjunction. The goal is an implication: open a box with $x > 1$ . Inside, $\mathrm{\vee I}$ manufactures the premise’s hypothesis, and $\mathrm{{\to}E}$ fires.

(x > 1 \vee x = 1) \to x^2 \ge x

x > 1

asm, for

\mathrm{{{\to}}I}

x > 1 \vee x = 1

\mathrm{{\vee}I}

x^2 \ge x

\mathrm{{{\to}}E}

1, 3

x > 1 \to x^2 \ge x

\mathrm{{{\to}}I}

2–4

In prose: Suppose $x > 1$ . Then $x \ge 1$ , so $x^2 \ge x$ by the fact. Hence if $x > 1$ , then $x^2 \ge x$ . The words “then $x \ge 1$ ” are line 3. For instance, at $x = 3$ the conclusion reads $9 \ge 3$ .

Exercise (B4: Derive or break)

For each claim, either derive it with the rules of Sections 1.2–1.5, or break it by statements about a real number $x$ that make its counterexample set true.

(a) $P \vdash P \vee (Q \wedge R)$ .
(b) $P \vdash P \wedge (Q \vee R)$ .
(c) $P \to R \vdash (P \vee Q) \to R$ .
(d) $(P \vee Q) \to R \vdash P \to R$ .
(e) $(P \wedge Q) \to R \vdash (Q \wedge P) \to (R \vee S)$ .
(f) $(P \to Q) \wedge (P \to R) \vdash P \to (Q \vee R)$ .
(g) $P \to (Q \vee R) \vdash P \to Q$ .

Solution.

(a) Derive. The side $P$ of the goal is the premise.
1 $P$
2 $P \vee (Q \wedge R)$ $\mathrm{{\vee}I}$ 1
(b) Break. Take $P$ : “ $x > 0$ ”, $Q$ : “ $x > 5$ ”, $R$ : “ $x < -5$ ”. At $x = 1$ , $P$ is true and $Q \vee R$ is false ( $1 > 5$ and $1 < -5$ both fail), so $P \wedge (Q \vee R)$ is false. The counterexample set $P$ , $\neg(P \wedge (Q \vee R))$ is true.
(c) Break. Take $P$ : “ $x > 3$ ”, $Q$ : “ $x < 0$ ”, $R$ : “ $x > 1$ ”. The premise $P \to R$ holds for every $x$ . At $x = -1$ , $P \vee Q$ is true ( $-1 < 0$ ) and $R$ is false, so $(P \vee Q) \to R$ is false, and the counterexample set $P \to R$ , $\neg((P \vee Q) \to R)$ is true.
(d) Derive. Inside the box of $P$ , $\mathrm{\vee I}$ manufactures the premise’s hypothesis, as in Example (A disjunctive hypothesis splits into two implications).

1 $(P \vee Q) \to R$
2 $P$ asm, for $\mathrm{{{\to}}I}$
3 $P \vee Q$ $\mathrm{{\vee}I}$ 2
4 $R$ $\mathrm{{{\to}}E}$ 1, 3
5 $P \to R$ $\mathrm{{{\to}}I}$ 2–4
(e) Derive. The premise’s hypothesis is $P \wedge Q$ , and the box gives $Q \wedge P$ : take it apart and join it the other way round, then postpone the goal $R \vee S$ until $R$ is in hand.
1 $(P \wedge Q) \to R$
2 $Q \wedge P$ asm, for $\mathrm{{{\to}}I}$
3 $Q$ $\mathrm{{\wedge}E}$ 2
4 $P$ $\mathrm{{\wedge}E}$ 2
5 $P \wedge Q$ $\mathrm{{\wedge}I}$ 4, 3
6 $R$ $\mathrm{{{\to}}E}$ 1, 5
7 $R \vee S$ $\mathrm{{\vee}I}$ 6
8 $(Q \wedge P) \to (R \vee S)$ $\mathrm{{{\to}}I}$ 2–7
(f) Derive. One half of the premise is enough.
1 $(P \to Q) \wedge (P \to R)$
2 $P$ asm, for $\mathrm{{{\to}}I}$
3 $P \to Q$ $\mathrm{{\wedge}E}$ 1
4 $Q$ $\mathrm{{{\to}}E}$ 3, 2
5 $Q \vee R$ $\mathrm{{\vee}I}$ 4
6 $P \to (Q \vee R)$ $\mathrm{{{\to}}I}$ 2–5
(g) Break. Take $P$ : “ $x > 0$ ”, $Q$ : “ $x > 5$ ”, $R$ : “ $x < 6$ ”. The premise $P \to (Q \vee R)$ holds for every $x$ , since every real number is $> 5$ or $< 6$ . At $x = 1$ , $P$ is true and $Q$ is false, so the counterexample set $P \to (Q \vee R)$ , $\neg(P \to Q)$ is true.

Apart from (e), which simply derives, the claims come in pairs. (a) and (b) are look-alikes, with $\vee$ and $\wedge$ traded; (c) and (d) are converses; (g) is a look-alike of (f), with premise and conclusion traded and weakened. In each pair one claim derives and the other breaks.

C. Going deeper

Exercise (C1: Which new rules are safe?)

Suppose someone proposes new rules for the derivations of this chapter. Let $x$ be a real number.

(a) Take the rule “from $\varphi \vee \psi$ , write $\varphi$ ”. Starting from the premise “ $x \ge 0$ or $x < 0$ ”, which is true for every real $x$ , derive with it a line that is false at $x = -1$ .
(b) $\mathrm{\vee I}$ adds a side $\psi$ that may be any statement at all. Explain why it can never lead from a true line to a false one.
(c) Is the rule “from $\varphi$ , write $\varphi \wedge \psi$ , for any statement $\psi$ ” safe in the same sense? Justify your answer with an instance.

Solution.

(a) With $\varphi$ replaced by $x \ge 0$ and $\psi$ by $x < 0$ , the proposed rule turns the premise into the line $x \ge 0$ . At $x = -1$ the premise is true, since $-1 < 0$ , and the line $-1 \ge 0$ is false. So the rule can lead from a true line to a false one.
(b) Suppose the cited line $\varphi$ is true. The new line $\varphi \vee \psi$ (or $\psi \vee \varphi$ ) is true when at least one of its sides is true, because “or” is inclusive (Section 1.1), and its side $\varphi$ is true. So the new line is true, whatever $\psi$ is. The truth or falsity of $\psi$ never enters.
(c) No. The new line $\varphi \wedge \psi$ is true only when both sides are, and $\psi$ is arbitrary. With $\varphi$ replaced by $x = -1$ and $\psi$ by $x \ge 0$ , at $x = -1$ the cited line is true and the new line, “ $x = -1$ and $x \ge 0$ ”, is false. The contrast with (b) is the whole difference between $\vee$ and $\wedge$ : a disjunction needs one true side, so an arbitrary second side is harmless; a conjunction needs both, so it is not. That is why $\mathrm{\wedge I}$ asks for both sides on lines.

Marking scheme. (10 points)

3: (a) applies the proposed rule to the premise to get $x \ge 0$ , and checks at $x = -1$ that the premise is true and the new line false.
3: (b) argues from the inclusive meaning of “or”: one true side makes the disjunction true, whatever the other side is.
3: (c) answers no, with an instance in which $\varphi$ is true and $\varphi \wedge \psi$ is false.
1: (c) names the difference: a conjunction needs both sides true.

Fatal errors (0 for the step): in (a), a premise that is false at $x = -1$ ; in (b), an argument that assumes $\psi$ is true; in (c), “safe” on the grounds that $\varphi$ is true.

Exercise (C2: Predicting the manufacture)

(a) Show that $(P \vee Q) \to (R \wedge S) \vdash P \to S$ .
(b) Show that $(P \vee Q) \to R \vdash (P \wedge Q) \to R$ .
(c) In each derivation, which rule built the hypothesis of the premise? Could you have predicted, from the premise’s main connective and the shape of its hypothesis alone, that this rule would be needed?

Solution.

(a) The goal is an implication: open a box with $P$ ; the goal inside is $S$ . The only line mentioning $S$ is the premise, whose conclusion $R \wedge S$ contains it; to use the premise, $\mathrm{{\to}E}$ needs $P \vee Q$ , built from $P$ by $\mathrm{\vee I}$ . Then $\mathrm{\wedge E}$ takes out $S$ .
1 $(P \vee Q) \to (R \wedge S)$
2 $P$ asm, for $\mathrm{{{\to}}I}$
3 $P \vee Q$ $\mathrm{{\vee}I}$ 2
4 $R \wedge S$ $\mathrm{{{\to}}E}$ 1, 3
5 $S$ $\mathrm{{\wedge}E}$ 4
6 $P \to S$ $\mathrm{{{\to}}I}$ 2–5
(b) The goal is an implication: open a box with $P \wedge Q$ ; the goal inside is $R$ . The premise fires on $P \vee Q$ . The assumption gives $P$ by $\mathrm{\wedge E}$ , and $\mathrm{\vee I}$ builds $P \vee Q$ .
1 $(P \vee Q) \to R$
2 $P \wedge Q$ asm, for $\mathrm{{{\to}}I}$
3 $P$ $\mathrm{{\wedge}E}$ 2
4 $P \vee Q$ $\mathrm{{\vee}I}$ 3
5 $R$ $\mathrm{{{\to}}E}$ 1, 4
6 $(P \wedge Q) \to R$ $\mathrm{{{\to}}I}$ 2–5

Taking $Q$ at line 3 instead, and building $P \vee Q$ by the second schema, works equally well.
(c) In both, $\mathrm{\vee I}$ built the hypothesis (line 3 in (a), line 4 in (b)), and in both it could be predicted. The premise’s main connective is $\to$ , so the premise is used by $\mathrm{{\to}E}$ , which needs its hypothesis $P \vee Q$ on a line of its own, exactly. That disjunction occurs only inside the premise, as its hypothesis, and no rule takes the hypothesis out of an implication ( $\mathrm{{\to}E}$ gives the conclusion). So it had to be built, and the only rule of the chapter so far that builds a disjunction is $\mathrm{\vee I}$ . The one question left was which side would be in hand; in (b) the conjunction $P \wedge Q$ offered both.