$$\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.2: Hypothesis an Theorems in Two-column Proofs

$$\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}}$$

A two-column proof must start by listing all of the hypotheses of the deduction, and each hypothesis is justified by writing the word hypothesis in the second column. (This is the only rule that is allowed above the dark horizontal line, and it is not allowed below the dark horizontal line.) We saw this rule in the above examples of two-column proofs. As a synonym for “hypothesis,” one sometimes says “given” or “assumption.”

Any deduction that is already known to be valid can be used as a justification if its hypotheses have been verified earlier in the proof. (And the lines where the hypotheses appear are written in parentheses after the name of the theorem.) For example, the theorems “$$\Rightarrow$$-elim” and “$$\lor$$-elim were used in our first examples of two-column proofs. These and several other very useful theorems were given in Exercise $$1.9.4$$. You will be expected to be familiar with all of them.

## Example $$\PageIndex{1}$$

# Assertion Justification English Version of Assertion
1 P $$\lor$$ Q hypothesis Either the Pope is here, or the Queen is here.
2 Q $$\Rightarrow$$ R hypothesis If the Queen is here, then the Registrar is also here.
3 $$\lnot$$ P hypothesis The Pope is not here.
4 Q $$\lor$$-elim (lines 1 and 3) The Queen is here.
5 R $$\Rightarrow$$-elim (lines 2 and 4) The Registrar is here.

## Example $$\PageIndex{2}$$

Here is a proof of the deduction $$\lnot L \Rightarrow (J \lor L)$$, $$\lnot L$$, $$J$$.

# Assertion Justification
1 $$\lnot$$L$$\Rightarrow$$(J$$\lor$$L) hypothesis
2 $$\lnot$$L hypothesis
3 J$$\lor$$L $$\Rightarrow$$-elim (lines 1 and 2)
4 J $$\lor$$-elim (lines 3 and 2)

## Exercise $$\PageIndex{3}$$

Provide a justification (rule and line numbers) for each line of this proof.

# Assertion Justification
1 W$$\Rightarrow\lnot$$B
2 A & W
3 $$\lnot$$B$$\Rightarrow$$(J & K)
4 W
5 $$\lnot$$B
6 J & K
7 K

## Exercise $$\PageIndex{4}$$

Provide a justification (rule and line numbers) for each line of this proof.

# Assertion Justification
1 A$$\Rightarrow$$B
2 $$\lnot$$A$$\Rightarrow$$B
3 A $$\lor\lnot$$A
4 B

## Exercise $$\PageIndex{5}$$

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

1. $$P\lor Q$$, $$Q\lor R$$, $$\lnot Q$$, $$P \& R$$.
2. $$(E\lor F) \lor G$$, $$\lnot F \& \lnot G$$, $$E$$.

## Exercise $$\PageIndex{6}$$

Write a two-column proof of each of the following deductions. (Write the assertions in English.)

1. Hypothesis:

The Pope and the Queen are here.

Conclusion: The Queen is here.

2. Hypothesis:

The Pope is here.
The Registrar and the Queen are here.

Conclusion: The Queen and the Pope are here.

3. Hypothesis:

If the Pope is here, then the Queen is here.
If the Queen is here, then the Registrar is here.
The Pope is here.

Conclusion: The Registrar is here.

4. Grace is sick.
Frank is sick.
$$\therefore$$ Either Grace and Frank are both sick, or Ellen is sick.

## Exercise $$\PageIndex{7}$$

Many proofs use the Rules of Negation or the fact that any statement is logically equivalent to its contrapositive. Here is an example.

# Assertion Justification English Version of Assertion
1 $$\lnot$$P $$\Rightarrow$$ (Q & R) hypothesis If the Pope is not here, then the
Queen and the Registrar are
here.
2 $$\lnot$$Q$$\lor\lnot$$R hypothesis Either the Queen is not here, or
the Registrar is not here.
3 $$\lnot$$(Q & R)$$\Rightarrow\lnot\lnot$$P contrapositive of line 1 If it is not the case that both the
Queen and the Registrar are
here, then it is not the case that
the Pope is not here.
4 ($$\lnot$$Q$$\lor\lnot$$R)$$\Rightarrow$$P Rules of Negation applied to line 3 If it is the case either that the
Queen is not here, or that the
Registrar is not here, then the
Pope is here.
5 P $$\Rightarrow$$-elim (lines 4 and 2) The Pope is here.

## Exercise $$\PageIndex{8}$$

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

1)

# Assertion Justification
1 H$$\Rightarrow$$F
2 H$$\Rightarrow$$G
3 (F & G )$$\Rightarrow$$I
4 $$\lnot$$I
5 $$\lnot$$I$$\Rightarrow\lnot$$ (F & G)
6 $$\lnot$$ (F & G)
7 $$\lnot$$F $$\lor\lnot$$G
8 $$\lnot$$F $$\Rightarrow\lnot$$ H
9 $$\lnot$$G $$\Rightarrow\lnot$$ H
10 $$\lnot$$H

2)

# Assertion Justification
1 (W$$\lor$$X)$$\Rightarrow$$(Y&Z)
2 $$\lnot$$Y
3 $$\lnot$$Y $$\lor\lnot$$Z
4 $$\lnot$$(Y & Z)$$\Rightarrow\lnot$$(W$$\lor$$X)
5 ($$\lnot$$Y$$\lor\lnot$$Z)$$\Rightarrow$$($$\lnot$$W&$$\lnot$$X)
6 $$\lnot$$W $$\&\lnot$$X
7 $$\lnot$$X

## Exercise $$\PageIndex{9}$$

Give a two-column proof of each of these deductions.

1. $$A \Rightarrow B$$, $$\lnot B$$, $$\therefore \lnot A$$
2. $$(L \lor M) \Rightarrow (N \& O)$$, $$M$$, $$\therefore O$$
3. Hypothesis:

Either the Pope is not here, or the Queen is here.
The Pope is here.

Conclusion: Either the Queen is here, or else the Registrar and the Pope are both here.

4. Hypothesis:

If Sammy is not tired, then she does not need a nap.
Sammy needs a nap.

Conclusion: Sammy is tired.

## Remark $$2.2.10$$.

You should also remember that $$\&$$ and $$\lor$$ are commutative, so, for example, $F \Rightarrow((E \& D \& C \& B) \vee(A \& B)) \equiv F \Rightarrow((A \& B) \vee(B \& C \& D \& E)) .$