2.1: First Example of a Two-Column Proof

Last updated
Save as PDF

Page ID: 23885

\( \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}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Let us begin our exploration of proofs by looking at the following simple deduction.

Hypothesis:

\(P \Rightarrow (Q \& R)\)
\(P\)

Conclusion: \(R\)

We will prove that it is valid by showing it is a combination of deductions that are already known to be valid. Informally, we could try to convince someone that the deduction is valid by making the following explanation:

Assume the Hypotheses (1) and (2) are true. Then applying \(\Rightarrow\)-elimination (with \(P\) in the role of \(A\), and \(Q \& R\) in the role of \(B\)) establishes that \(Q \& R\) is true. (This is an intermediate conclusion. It follows logically from the hypotheses, and is helpful, but it is not the conclusion we want.) Now, applying \(\&\)-elimination (with \(Q\) in the role of \(A\), and \(R\) in the role of \(B\)) establishes that \(R\) is true. This is the conclusion of the deduction. Thus, we see that if the hypotheses of this deduction are true, then the conclusion is also true. So the deduction is valid.

For emphasis, let us repeat that this explanation shows that the deduction is merely a combination of deductions that were already known to be valid.

Remark \(2.1.1\).

Notice that we are using the fact that a valid deduction applies to all possible values of its variables, so we can plug any assertions we want into its variables. This is what allows us to talk about using (for example) “\(Q \& R\) in the role of \(B\).” Another way of saying this, is that we are introducing a new symbolization key in which we let \(A\) stand for \(P\), and let \(B\) stand for \(Q \& R\).

Formally, a proof is a sequence of assertions. The first assertions of the sequence are assumptions; these are the hypotheses of the deduction. It is required that every assertion later in the sequence is an immediate consequence of earlier assertions. (There are specific rules that determine which assertions are allowed to appear at each point in the proof.) The final assertion of the sequence is the conclusion of the deduction.

In this chapter, we use the format known as “two-column Proofs” for writing our proofs. As indicated in the tableau below:

Assertions appear in the left column.
The reason (or “justification”) for including each assertion appears in the right column. (The allowable justifications will be discussed in the later sections of this chapter.)

#	assertion	justification

Every assertion in a two-column proof needs to have a justification in the second column.

Now, we can translate the deduction into English:For clarity, we draw a dark horizontal line to separate the hypotheses from the rest of the proof. (In addition, we will number each row of the proof, for ease of reference, and we will make the left border of the figure a dark line.) For example, here is a two-column proof that justifies the deduction above. It starts by listing the hypotheses of the deduction, and ends with the correct conclusion.

#	assertion	justification
1	\(P\Rightarrow(Q\&R)\)	hypothesis
2	\(P\)	hypothesis
3	\(Q \& R\)	\(\Rightarrow\)-elim (lines 1 and 2)
4	\(R\)	\(\&\)-elim (line 3)

In this example, the assertions were written in the language of , but sometimes we will write our proofs in English. For example, here is a symbolization key that allows us to translate \(P\), \(Q\), and \(R\) into English. For convenience, this same symbolization key will be used in many of the examples in this chapter.

\(P\) The Pope is here.
\(Q\) The Queen is here.
\(R\) The Registrar is here.

Now, we can translate the deduction into English:

Hypothesis:

If the Pope is here, then the Queen and the Registrar are also here.
The Pope is here.

Conclusion: The Registrar is here.

And we can provide a two-column proof in English:

#	assertion	justification
1	If the Pope is here, then the Queen and the Registrar are also here.	hypothesis
2	The Pope is here	hypothesis
3	The Queen and the Registrar are both here.	\(\Rightarrow\)-elim (lines 1 and 2)
4	The Registrar is here.	\(\&\)-elim (line 3)

While you are getting accustomed to two-column proofs, it will probably be helpful to see examples in both English and . To save space, and make it easier to compare the two, the text will sometimes combine both proofs into one figure, by adding a third column at the right that states the English-language versions of the assertions:

#	Assertion in Propositional Logic	Justification	English Language version of the assertion

For example, here is what we get by combining the above two proofs:

#	assertion	justification	Englision
1	\(P\Rightarrow(Q\&R)\)	hypothesis	If the Pope is here, then the Queen and the Registrar are also here.
2	\(P\)	hypothesis	The Pope is here
3	\(Q \& R\)	\(\Rightarrow\)-elim (lines 1 and 2)	The Queen and the Registrar are both here.
4	\(R\)	\(\&\)-elim (line 3)	The Registrar is here.

The next few sections will explain the justifications that are allowed in a two-column proof.