The Logic Forum Discussion Area
Hi Smith.
Looking at the two examples given in the text you quote, I am not sure the terminology used is correct, i.e. direct/indirect 'proof'.
The indirect method described is argument by elimination - presumably all the presumed possibilities of solution to a problem are listed, and all but one are eliminated for one reason or another, leaving one probable solution. Of course, this works only so long as we assume all possibles are listed and that those listed are indeed possible.
The direct method presumably refers to all other approaches, where evidence is gathered and a single hypothesis covering them is eventually formulated on that basis. Here again, this is good method, but of course there are many pitfalls possible. Also, this method actually uses the method of elimination in a tacit way, when this hypothesis rather than any other is formulated and adopted.
So, my point is that neither of these examples refers to deductive proof, but both rather to inductively-probable 'proof'.
Something about you (optional) logician-philosopher
Hi Avi,
Maybe that example wasn't such a good one because I was referring only to deductive proofs. I don't have time at the moment but will post another example later. What I mean by direct and indirect proof is that the latter uses an assumption but the former doesn't. So direct proofs only use the given premises whereas an indirect proof such as a reductio argument must assume the contradictory of the conclusion, and a so-called conditional proof introduces an assumption in order to end up with an if-then statement.
This was the answer which received the most upvotes in reply to the question : "Are proofs by contradiction (PBC) weaker than other proofs?"
Actually, the simple answer is "no", because when considering deductive arguments the argument is either valid or not, and for the purpose of proving validity PBC is as good as any other method. The issue is how it compares to a "direct" proof (which doesn't use any assumptions) in terms of its usefulness in generating further propositions relevant to the argument. Anyway here is the answer :
With good reason, we mathematicians prefer a direct proof of an implication over a proof by contradiction, when such a proof is available. (all else being equal)
What is the reason? The reason is the fecundity of the proof, meaning our ability to use the proof to make further mathematical conclusions. When we prove an implication (p implies q) directly, we assume p, and then make some intermediary conclusions r1, r2, before finally deducing q. Thus, our proof not only establishes that p implies q, but also, that p implies r1 and r2 and so on. Our proof has provided us with additional knowledge about the context of p, about what else must hold in any mathematical world where p holds. So we come to a fuller understanding of what is going on in the p worlds.
Similarly, when we prove the contrapositive (¬q implies ¬p) directly, we assume ¬q, make intermediary conclusions r1, r2, and then finally conclude ¬p. Thus, we have also established not only that ¬q implies ¬p, but also, that it implies r1 and r2 and so on. Thus, the proof tells us about what else must be true in worlds where q fails. Equivalently, since these additional implications can be stated as (¬r1 implies q), we learn about many different hypotheses that all imply q.
These kind of conclusions can increase the value of the proof, since we learn not only that (p implies q), but also we learn an entire context about what it is like in a mathematial situation where p holds (or where q fails, or about diverse situations leading to q).
With reductio, in contrast, a proof of (p implies q) by contradiction seems to carry little of this extra value. We assume p and ¬q, and argue r1, r2, and so on, before arriving at a contradiction. The statements r1 and r2 are all deduced under the contradictory hypothesis that p and ¬q, which ultimately does not hold in any mathematical situation. The proof has provided extra knowledge about a nonexistant, contradictory land. (Useless!) So these intermediary statements do not seem to provide us with any greater knowledge about the p worlds or the q worlds, beyond the brute statement that (p implies q) alone.
I believe that this is the reason that sometimes, when a mathematician completes a proof by contradiction, things can still seem unsettled beyond the brute implication, with less context and knowledge about what is going on than would be the case with a direct proof.
For an example of a proof where we are led to false expectations in a proof by contradiction, consider Euclid's theorem that there are infinitely many primes. In a common proof by contradiction, one assumes that p1, ..., pn are all the primes. It follows that since none of them divide the product-plus-one p1...pn+1, that this product-plus-one is also prime. This contradicts that the list was exhaustive. Now, many beginner's falsely expect after this argument that whenever p1, ..., pn are prime, then the product-plus-one is also prime. But of course, this isn't true, and this would be a misplaced instance of attempting to extract greater information from the proof, misplaced because this is a proof by contradiction, and that conclusion relied on the assumption that p1, ..., pn were all the primes. If one organizes the proof, however, as a direct argument showing that whenever p1, ..., pn are prime, then there is yet another prime not on the list, then one is led to the true conclusion, that p1...pn+1 has merely a prime divisor not on the original list.
The question was posted in math.stackexchange and since the answer is relates specifically to mathematical proof, I'm not sure how well it generalises to non-mathematical areas.
I'll post a couple of concrete examples over the weekend, proving each argument in two ways, one direct and the other using PBC.
Hi Smith. I read your post. I am not a mathematician, so cannot deeply comment on this subject as such.
However, from the purely logical point of view, in deductive logic, ‘p implies q’ and its contraposite ‘not-q implies not-p’ are exactly equivalent, both meaning no more or less than “the conjunction ‘p and not-q’ is impossible” (or, identically, “the conjunction ’not-q and p’ is impossible’).
For example, in syllogistic theory, we use direct reduction to the first figure to validate fourth figure moods, and indirect reduction (reductio ad absurdum) to the first figure to validate second figure moods. See here: http://thelogician.net/FUTURE-LOGIC/Syllogisms-Validations-10.htm. Neither method is better or worse than the other in terms of logical certainty. They are just conveniences.
In inductive logic, things are more complicated as already pointed out in my previous reply to you. Notably, any claim to having an exhaustive list of hypotheses implying a certain phenomenon is, of course, itself a mere hypothesis. Indeed, any claim that this or that is a credible hypothesis for that phenomenon is itself, ultimately, a mere hypothesis. So, every conclusion is in the realm of the merely probable, even if some possibilities are more probable than others.
As regards the mathematical case presented, the apparent contradiction seems easy to resolve (if I understand it correctly). Both p and p+1 could well be primes. The fact that the symbol p is used in both terms does not affect this possibility. That is to say, ‘p+1’ could well be a case of ‘p’ – symbols do not signify fixed values but all values of a kind. So, the two series are really one and the same. They differ only superficially in symbols used.
As regards the claim that, in the said mathematical context, a proof viewed as more ‘direct’ might be more informative or productive than one viewed as more ‘indirect’ – well, ok, that might well happen. But the logical validity of both avenues can still be equal, even so, if the logic involved is sufficiently strict.
I hope that helps.
Something about you (optional) logician-philosopher
