$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 2.3: Subproofs for $$\Rightarrow$$-introduction

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

Consider this deduction:

 $$P \Rightarrow R$$ If the Pope is here, then the Registrar is here. $$\therefore (P \& Q) \Rightarrow R$$ If the Pope and the Queen are both here,then the Registrar is here.

The deduction is a valid one. Intuitively, we can justify it by noting that if $$P \& Q$$ is true, then $$P$$ is certainly true, so the hypothesis implies $$R$$ is true. Thus, we have verified that $$(P \& Q) \Rightarrow R$$. The $$\Rightarrow$$-introduction rule will allow us to turn this intuitive justification into an official proof.

We begin the proof by writing down the hypothesis of the deduction and drawing a dark horizontal line, like this:

# Assertion Justification English Version of Assertion
1 P$$\Rightarrow$$R Hypothesis If the Pope is here, then the Registrar is here.

The conclusion of the deduction is an assertion about what happens when $$P \& Q$$ is true. That is, we want to see what happens if we assume, for the sake of argument, that the assertion $$P \& Q$$ is true. To accomplish this, what we will do is start a Subproof, a proof within the main proof, where we assume that $$P \& Q$$ is true. When we start a subproof, we start a new set of double columns, and indent them from the left margin. Then we write in an assumption for the subproof. This can be anything we want. In the case at hand, we want to assume $$P \& Q$$. Our proof now looks like this:

# Assertion Justification English Version of Assertion
1 P$$\Rightarrow$$R Hypothesis If the Pope is here, then the Registrar is here.
2 P & Q assumption Suppose the Pope and the Queen are both here.

It is important to notice that we are not claiming to have proven $$P \& Q$$ (that the Pope and the Queen are here). You can think of the subproof as posing the question: What could we show if $$P \& Q$$ were true? For one thing, we can derive $$P$$. So we do:

# Assertion Justification English Version of Assertion
1 P $$\Rightarrow$$ R hypothesis If the Pope is here, then the Registrar is here.
2 P & Q assumption Suppose the Pope and the Queen are both here.
3 P &-elim (line 2) The Pope is here.

And now, since the Pope is here, we can derive $$R$$, from the hypothesis that $$P \Rightarrow R$$:

# Assertion Justification English Version of Assertion
1 P $$\Rightarrow$$ R hypothesis If the Pope is here, then the Registrar is here.
2 P & Q assumption Suppose the Pope and the Queen are both here.
3 P &-elim (line 2) The Pope is here.
4 R $$\Rightarrow$$-elim (lines 1 and 3) The Registrar is here.

This has shown that if we had $$P \& Q$$ as a hypothesis, then we could prove $$R$$. In effect, we have proven $$(P \& Q) \Rightarrow R$$: that if the Pope and the Queen are here, then the Registrar is here. In recognition of this, the if-introduction rule ($$\Rightarrow$$-intro) will allow us to close the subproof and derive $$(P \& Q) \Rightarrow R$$ in the main proof. Our final proof looks like this:

# Assertion Justification English Version of Assertion
1 P $$\Rightarrow$$ R hypothesis If the Pope is here, then the Registrar is here.
2 P & Q assumption Suppose the Pope and the Queen are both here.
3 P &-elim (line 2) The Pope is here.
4 R $$\Rightarrow$$-elim (lines 1 and 3) The Registrar is here.
5 (P & Q) $$\Rightarrow$$ R $$\Rightarrow$$-intro (lines 2-4) If the Pope and the Queen are both here, then the Registrar is here.

Notice that the justification for applying the $$\Rightarrow$$-intro rule is the entire subproof. Usually that will be more than just three lines.

It may seem as if the ability to assume anything at all in a subproof would lead to chaos: does it allow you to prove any conclusion from any hypotheses? The answer is no, it does not. Consider this proof:

# Assertion Justification English Version of Assertion
1 P hypothesis The Pope is here.
2 Q assumption Suppose that the Queen is here.
3 Q repeat (line 2) As mentioned previously, the Queen is here.

It may seem as if this is a proof that you can derive any conclusion $$Q$$ (such as the conclusion that the Queen is here) from any hypothesis $$P$$ (such as the hypothesis that the Pope is here). When the vertical line for the subproof ends, the subproof is closed. In order to complete a proof, you must close all of the subproofs. And you cannot close the subproof and use the repeat rule again on line 4 to derive $$Q$$ in the main proof. Once you close a subproof, you cannot refer back to individual lines inside it.

$\text{You CANNOT use a line from a subproof as a hypothesis for a theorem that is being applied in the main proof. Lines in a subproof stay in the subproof.}$

$\text{In particular, you CANNOT use the repeat theorem to copy a line from a subproof into the main proof.}$

Of course, it is legitimate to do this:

# Assertion Justification English Version of Assertion
1 P hypothesis The Pope is here.
2 Q assumption Suppose that the Queen is here.
3 Q repeat (line 2) As mentioned previously, the Queen is here.
4 Q$$\Rightarrow$$Q $$\Rightarrow$$-intro (lines 2 and 3) If the Queen is here, then the Queen is here.

This should not seem so strange, though. Since $$Q\Rightarrow Q$$ is a tautology, it follows validly from any hypotheses.

Put in a general form, the $$\Rightarrow$$-introduction rule looks like this:

# Assertion Justification English Version of Assertion
m A assumption (want B) Suppose that Alberta is big.
$$\vdots$$ $$\vdots$$ $$\vdots$$ $$\vdots$$
n B Whatever Reason Then BC is big.
A $$\Rightarrow$$ B $$\Rightarrow$$-intro (lines m-n) If Alberta is big, then BC is big.

When we introduce a subproof, it is helpful to make a note of what we want to derive (and add it to the justification). This is so that anyone reading the proof will find it easier to understand why we are doing what we are doing (and also so that we do not forget why we started the subproof if it goes on for five or ten lines). There is no “want” rule. It is a note to ourselves and to the reader; it is not formally part of the proof.

Although it is legal to open a subproof with any assumption you please, there is some strategy involved in picking a useful assumption. Starting a subproof with an arbitrary, wacky assumption would just waste lines of the proof. In order to derive an if-then statement by using $$\Rightarrow$$-intro, for instance, you must assume the hypothesis of the statement in a subproof.

Now that we have both the introduction rule and the elimination rule for “implies,” we can prove that the following deduction is valid:

 $$P \Rightarrow Q$$ If the Pope is here, then so is the Queen. $$Q \Rightarrow R$$ If the Queen is here, then so is the Registrar. $$\therefore P \Rightarrow R$$ Therefore, if the Pope is here, then so is the Registrar.

We begin the proof by writing the two hypotheses as assumptions. Since the main logical operator in the conclusion is $$\Rightarrow$$, we can expect to use the $$\Rightarrow$$-introduction rule. For that, we need a subproof—so we write in the hypothesis of the if-then statement as the assumption of a subproof:

# Assertion Justification English Version of Assertion
1 P $$\Rightarrow$$ Q hypothesis If the Pope is here, then so is the Queen.
2 Q $$\Rightarrow$$ R hypothesis If the Queen is here, then so is the Registrar.
3 P assumption (want R) Suppose that the Pope is here.

We made $$P$$ available by assuming it in a subproof, allowing us to apply $$\Rightarrow$$-elim to line 1. This gives us $$Q$$, which allows us to apply $$\Rightarrow$$-elim to line 2. Having derived $$R$$, we close the subproof. By assuming $$P$$ we were able to prove $$R$$, so $$\Rightarrow$$-elim completes the proof. Here it is written out:

# Assertion Justification English Version of Assertion
1 P $$\Rightarrow$$ Q hypothesis If the Pope is here, then so is the Queen.
2 Q $$\Rightarrow$$ R hypothesis If the Queen is here, then so is the Registrar.
3 P assumption (want R) Suppose that the Pope is here.
4 Q $$\Rightarrow$$-elim (lines 1 and 3) The Queen is here.
5 R $$\Rightarrow$$-elim (lines 2 and 4) The Registrar is here.
6 P $$\Rightarrow$$ R $$\Rightarrow$$-intro (lines 3-5) If the Pope is here, then so is the Registrar.

## Exercise $$\PageIndex{1}$$

Provide a justification (rule and line numbers) for each line of these proofs.

1. # Assertion Justification
1 A $$\Rightarrow$$ B
2 $$\lnot$$ A $$\Rightarrow$$ C
3 A $$\lor \lnot$$A
4 A
5 B
6 B $$\lor$$ C
7 A$$\Rightarrow$$ (B $$\lor$$ C)
8 $$\lnot$$A
9 C
10 B $$\lor$$ C
11 $$\lnot$$A $$\Rightarrow$$(B $$\lor$$ C)
12 B $$\lor$$ C
2. # Assertion Justification
1 L $$\Leftrightarrow \lnot$$ O
2 L $$\lor \lnot$$ O
3 L
4 L
5 L $$\Rightarrow$$ L
6 $$\lnot$$ O $$\Rightarrow$$ L
7 L
3. # Assertion Justification
1 F $$\Rightarrow$$$$\left(\text{(G & H)}\lor \text{I} \right)$$
2 $$\lnot$$I
3 $$\lnot$$G
4 $$\lnot$$G $$\lor \lnot$$H
5 ($$\lnot$$G $$\lor \lnot$$H) & $$\lnot$$ I
6 $$\lnot$$((G & H) $$\lor$$ I)
7 $$\lnot$$((G & H) $$\lor$$ I)$$\Rightarrow \lnot$$F
8 $$\lnot$$F
9 $$\lnot$$G $$\Rightarrow \lnot$$F
10 $$\lnot\lnot$$F$$\Rightarrow\lnot\lnot$$G
11 F$$\Rightarrow$$G
4. # Assertion Justification
1 $$\lnot$$ C $$\Rightarrow$$ B $$\lor$$ C
2 C $$\lor \lnot$$ C
3 C
4 B $$\lor$$ C
5 C $$\Rightarrow$$(B $$\lor$$ C)
6 B $$\lor$$ C
7 A & $$\lnot$$ B
8 $$\lnot$$B
9 C
10 (A & $$\lnot$$ B) $$\Rightarrow$$C
5. # Assertion Justification
1 Z $$\Rightarrow$$ (C & $$\lnot$$ N)
2 $$\lnot$$ Z $$\Rightarrow$$ (N & $$\lnot$$C)
3 Z $$\lor \lnot$$ Z
4 Z
5 C & $$\lnot$$N
6 C
7 N $$\lor$$ C
8 Z $$\Rightarrow$$ (N $$\lor$$ C)
9 $$\lnot$$Z
10 N & $$\lnot$$ C
11 N
12 N $$\lor$$ C
13 $$\lnot$$Z $$\Rightarrow$$(N $$\lor$$ C)
14 N $$\lor$$ C
6. # Assertion Justification
1 A $$\Rightarrow$$ E
2 C $$\Rightarrow$$ E
3 A $$\lor$$ C
4 E
5 (A $$\lor$$ C)$$\Rightarrow$$ E

## Exercise $$\PageIndex{2}$$

Write a two-column proof of each of the following deductions:

1. $$P \Rightarrow (Q \lor R)$$, $$Q \Rightarrow S$$, $$R \Rightarrow S$$, $$\therefore$$ $$P \Rightarrow S$$
2. $$Q \Rightarrow (Q \Rightarrow P)$$, $$\therefore$$ $$Q \Rightarrow P$$
3. $$M\lor(N\Rightarrow M)$$, $$\therefore$$ $$\lnot M \Rightarrow \lnot N$$
4. $$R \Rightarrow \Bigl(R \Rightarrow \bigl(R \Rightarrow (R \Rightarrow Q) \bigr) \Bigr)$$, $$\therefore$$ $$R \Rightarrow (Q \lor P)$$
5. $$A \lor B$$, $$A \Rightarrow C$$, $$B \Rightarrow D$$, $$C \Rightarrow E$$, $$D \Rightarrow E$$, $$\therefore E$$

6. Hypothesis:

The Pope is here if and only if the Queen is here.
The Queen is here if and only if the Registrar is here.

Conclusion: The Pope is here if and only if the Registrar is here.

7. Hypothesis:

If Jim is sick, he should stay in bed.
If Jim is not sick, he should go outside to play.

Conclusion: Jim should either stay in bed or go outside to play.

8. Hypothesis:

If the King will sing, then the Queen will sing.
If the King and the Queen will both sing, then the Prince and the Princess will also sing.
If the King and the Queen and the Prince and the Princess will all sing, then the party will be fun.

Conclusion: If the King will sing, then the party will be fun.

9. Hypothesis:

If the Pope is here, then either the Queen is here or the Registrar is here.

If the Queen is here, then the Spy is here.
If the Registrar is here, then the Spy is here.

Conclusion: If the Pope is here, then the Spy is here.