A proof is a proof. What kind of a proof? It’s a proof. A proof is a proof. And when you have a good proof, it’s because it’s proven. - Jean Chretien
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?”
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}}\): > >1. \(\sqrt 2 + \sqrt 6 = \sqrt{8+2\sqrt{12}}\). >2. \((\sqrt 2 + \sqrt 6)^2 = \sqrt{8+2\sqrt{12}}^2\). >3. \({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): > >1. \(\sqrt 2 + \sqrt 6 = -\sqrt{8+2\sqrt{12}}\). >2. \((\sqrt 2 + \sqrt 6)^2 = (-\sqrt{8+2\sqrt{12}})^2\). >3. \({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:
Example
Here is a valid proof of \(\sqrt 2 + \sqrt 6 = \sqrt{8+2\sqrt{12}}~\) that uses both of those strategies: >1. \((\sqrt 2 + \sqrt 6)^2 = 2 + 2\sqrt{12} + 6 = 8 + 2\sqrt{12}\). >2. Taking the positive square root of both sides, we get >\[ \sqrt 2 + \sqrt 6 = \sqrt{8+2\sqrt{12}}. \] ### Final Comments
Previous: 2.3 Predicate Rules of Natural Deduction
Next: 3.3 Bounded Quantifiers