Proofs for Humans

“I remember the time I was kidnapped and they sent a piece of my finger to my father. He said he wanted more proof.”
—Rodney Dangerfield

Natural Deduction is mathematically precise and has a relatively small number of inference rules. This makes it a lot easier to study the proof system, and to prove properties of all possible ND proofs (e.g., Soundness). But asking humans to write proofs using only ND rules is as painful as asking programmers to write all their code in machine language. In this section, we suggest a number of strategies for writing proofs aimed at humans, many of which are inspired by (but not limited to) the Natural Deduction rules. We also discuss some common mistakes and pitfalls.

The general theme of many of these strategies is that the structure of the proof should be determined by the (logical) structure of the statement being proved.

Useful Non-ND Rules

The following reasoning principles are not official ND rules, but they are provably correct (they are “theorems” of natural deduction, not built-in rules), and hence we can safely use them in our proofs:

\large \frac{p \lor q \qquad \lnot p}{q} \qquad\qquad \frac{p \to q \qquad \lnot q}{\lnot p}

Example

Around 1200 AD, Alexander Neckham gave the following demonstration that “anything follows from a contradiction” (i.e., $~\bot E~$ ) is a valid reasoning principle, assuming one accepts $\land E$ , $\lor I$ , and the first of the above two rules:

“I am amazed also at those criticizing the claim that from the impossible in itself anything whatever follows. This may be established in many ways, but few will show more clearly.

Is it not the case that if Socrates is a man and Socrates is not a man, then Socrates is a man?

But if Socrates is a man, Socrates is a man or a stone.

So if Socrates is a man and Socrates is not a man, Socrates is a man or a stone.

But if Socrates is a man and Socrates is not a man, Socrates is not a man.

So if Socrates is a man and Socrates is not a man, Socrates is a stone.

By a similar deduction, it may be proved that if Socrates is a man and Socrates is not a man, Socrates is a goat, and so on for any other thing, such as a rose, a lily and so on. Don’t you therefore see that in this way from this impossibility, that Socrates is a man and Socrates is not a man, anything follows?”

Sequencing Equalities

Equalities and inequalities generally cause no problems in proofs, but students occasionally make the following error:

Pitfall

The most common error involving equalities in proofs is starting with the goal equality, and drawing conclusions from that goal until a true statement is reached, and then declaring victory.

Example

Here is an invalid proof that $\sqrt 2 + \sqrt 6 = \sqrt{8+2\sqrt{12}}$ :

$\sqrt 2 + \sqrt 6 = \sqrt{8+2\sqrt{12}}$ .
$(\sqrt 2 + \sqrt 6)^2 = \sqrt{8+2\sqrt{12}}^2$ .
${8+2\sqrt{12}} = {8+2\sqrt{12}}$ .

The problem is that, as we know (and as is discussed more below), we have assumed $\sqrt 2 + \sqrt 6 = \sqrt{8+2\sqrt{12}}$ and proved a true statement. From this argument, then, we can conclude

(\sqrt 2 + \sqrt 6 = \sqrt{8+2\sqrt{12}}) \to \top

but this is not an interesting result because it doesn’t tell us whether $\sqrt 2 + \sqrt 6 = \sqrt{8+2\sqrt{12}}$ is true or not!

Another way to look at the problem is to observe that we can use the same strategy to prove obviously false results (e.g., a strictly positive value being equal to a strictly negative value):

$\sqrt 2 + \sqrt 6 = -\sqrt{8+2\sqrt{12}}$ .
$(\sqrt 2 + \sqrt 6)^2 = (-\sqrt{8+2\sqrt{12}})^2$ .
${8+2\sqrt{12}} = {8+2\sqrt{12}}$ .

Correct Equalities

To prove an equality, there are two general strategies:

Give a chain of equalities where each step is obviously true. Then we can conclude that the first term is equal to the last. For example,

(1+2)\times(3+4) = 3\times(3+4) = 3\times 7 = 21.

is a perfectly good argument that $(1+2)\times(3+4) = 21$ .

Start with facts known to be true and derive consequences, ending with the equality we want to prove. For example, another valid (if more verbose) proof that $(1+2)\times(3+4) = 21$ goes as follows:
1. $1+2 = 3$
2. $3+4 = 7$
3. $(1+2)\times (3+4) = 3\times 7$
4. $(1+2)\times (3+4) = 21$

Example

Here is a valid proof of $\sqrt 2 + \sqrt 6 = \sqrt{8+2\sqrt{12}}~$ that uses both of those strategies:

$(\sqrt 2 + \sqrt 6)^2 = 2 + 2\sqrt{12} + 6 = 8 + 2\sqrt{12}$ .
Taking the positive square root of both sides, we get

\sqrt 2 + \sqrt 6 = \sqrt{8+2\sqrt{12}}.

Final Comments

Similar strategies work for inequalities and mixtures of equalities and inequalities, e.g.,

3{\times} 8~~<~~3{\times}8 + 1~~=~~24 + 1~~<~~25 + 1~~=~~26

is an (overly detailed, but valid) argument that $3{\times}8 < 26$ .

There’s a huge difference between finding a proof and presenting or verifying a proof. If you want to prove an equality and aren’t sure how, there is no objection to starting with that equality and working out consequences. This is not a proof, but if you’re lucky, the steps you take are all reversible (each formula is true if and only if the next formula is true), and then you can get a valid proof by reversing the order of the steps.