0

As with most proofs by Indirect Method or Reductio Ad Absurdum, the key step is to discover (at least, to divine or presage) the location of the contradiction. So for the following example, what suggests or reveals F as the cause of the contradiction, as in Step 15?

I already understand, and so ask not about, any of the steps or the proof itself.


[Scroll down 70% hereof to see this example:] 1. R ⊃ B  2. R ⊃ (B ⊃ F)  3. B ⊃ (F ⊃ H)
Conclusion: R ⊃ H

Now, since this has a conditional for its conclusion, CP is the smarter choice, but we’re going to walk through it with IP to exhibit how it can apply.

 | 4. ~ (R ⊃ H)    AIP
 | 5. ~( ~R ∨ H)  Material Implication: 4
 | 6. ~~R ∧ ~H   DeMorgan's Rule: 5
 | 7. R ∧ ~H     Double Negation: 6
 | 8. R       Simplification (SM): 7
 | 9. B      Modus Ponens (MP): 1,8
 | 10. F ⊃ H    MP 9,3
 | 11. ~H     CM, SM 7
 | 12. ~F      MT 11,10
 | 13. B ⊃ F     MP 8,2
 | 14. F      MP 9, 13
 | 15. F ∧ ~F    CN 14,12
16. R ⊃ H     IP 4-15

2

The problem of evaluating the truth of a proposition (including whether it leads to a contradiction or not) from a computational point of view amounts to evaluating the boolean expression corresponding to that proposition.

Determining whether your proposition F would lead to a contradiction or not is the same as being able to determining whether the corresponding boolean expression is satisfiable or not. At the present time there is no known method for evaluating the truth of a general boolean expression without actually calculating the expression itself. This is known as the boolean satisfiability problem, and it is conjectured that there is no efficient algorithm for evaluating whether it has a truth value or not. The only guaranteed way of determining whether it is satisfiable or not, and determining the corresponding variable assignment, is to evaluate all possible combinations of the boolean expression.

This fact that there is no known general efficient solution, and the conjecture that the can't be one, is known as the P vs NP problem.

Here efficient means that it can be solved in (deterministic) polynomial time.
Inefficient means that the problem is solvable in Non-deterministic polynomial time (The "NP" in NP-complete). For practical purposes this means the only way of finding a solution is to evaluate every possible input combination, which can take up to an exponential amount of time.

The P vs NP problem first gained importance after Cook and Levin independently proved the NP-completness theorem in the 70s. In particular Cook was working on automated theorem proving procedures, and it was in this context that he ended up with his result regarding boolean satisfiability.

There is a remote possibility that P=NP and that there is such an efficient procedure, but it is considered highly unlikely, and if it were true, the consequence would be significant for our understanding of computation and science in general.

"If P = NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in "creative leaps," no fundamental gap between solving a problem and recognizing the solution once it's found." — Scott Aaronson, MIT

To summarize, the answer to your overall question "Before starting the Reductio Ad Absurdum, how can you guess or divine that F causes the contradiction?": There is no known method for doing so beforehand. Being able to do so implies an efficient method for solving boolean satisfiability, and it is conjectured (but not yet proven conclusively) that an efficient method is impossible.

  • 1
    This answer is perhaps akin to putting in a finish nail with a sledgehammer... – jobermark Jan 2 '16 at 1:54
  • 1
    @jobermark this is a philosophy forum, the answers have to be pompous or they're irrelevant :-) – Alexander S King Jan 2 '16 at 2:02
  • Thank you for your detailed answer, but which has confused me. Though the argument in the OP did not originate from A Concise Introduction to Logic (12 Ed, 2014) by Patrick Hurley, this textbook (that I am using now) discusses, in many examples, how to divine or presage the key steps in an argument before doing the proof. These presages: do they affect your answer? Do they contradict your answer? Please tell me if you wish me to quote such presages. – Greek - Area 51 Proposal Jan 3 '16 at 22:15
  • Would you please respond in your answer, which is easier to read than comments? – Greek - Area 51 Proposal Jan 3 '16 at 22:20
1

With proofs, there is always more than one way to skin the cat. Your proof proceeds to derive F and ¬F, but there are other ways it could have worked. For example, from 14 and 10 you can prove H by MP, but you also have ¬H at 11, so you have proved H and ¬H. Or alternatively, from 13 and 12 you can prove ¬B by MT, which combined with 9 gives you B and ¬B. Or again, from ¬B and 1 you can prove ¬R by MT which combined with 8 gives you R and ¬R.

So there is no particular unique contradiction that must be found, and it would be misleading to say that F is the cause of the contradiction. With proofs by reductio, as soon as you assume the negation of the conclusion you have created an inconsistent set of sentences, so anything follows by the principle of explosion. You have only to locate a contradiction somewhere and your proof is done.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.