3 ms·

This document misses the point in a way that very commonly arises when mathematicians (as opposed to logicians) discuss proof by contradiction. The examples in

by butokai 3mo ago

This document misses the point in a way that very commonly arises when mathematicians (as opposed to logicians) discuss proof by contradiction. The examples in this document all revolve around assuming a fact, showing that it would lead to an absurd, and thus establishing that that fact can’t be the case: there is no rational equal to sqrt(2), there is no finite listing of all the primes. They are not using proof by contradiction at all, and on the contrary these proof are fully constructive: if one where to give us what they believe is a finite list of all the primes, the proofs gives us a method to construct a new prime. Proof by contradiction, on the other side, deems that we derive a contradiction from the assumption that a statement does not hold. Then, by contradiction, we may state that is true because it is impossible for it to be false. This is why it is rejected by the intuitionists and constructivists: there is no way to extract an explicit procedure from such a proof, since it only states that what can’t be false must me true.

adrian_b 3mo ago
"What can’t be false must me true" is what classic logic called "Tertium non datur", and which has absolutely nothing to do with a demonstration by "Reductio ad absurdum", i.e. with "assuming a fact, showing that it would lead to an absurd". A demonstration by "Reductio ad absurdum" can also be done in multivalent logic, for instance in trivalent logic, where a statement can be true or false or neither true nor false, therefore "Tertium non datur" is not applicable. In my opinion, trivalent logic is the simplest kind of logic that is applicable to mathematics or to the real world. Its subset that is bivalent logic is interesting as an object of study but not as a technique that can be useful for practical reasoning or for mathematical demonstrations. If I understood you correctly, you want to distinguish the following 2 kinds of demonstrations, where P1 and P2 are propositions: 1. One demonstrates that "P1 implies not P1". From this it can be concluded that P1 cannot be true. 2. One demonstrates that "P1 implies not P2". But it is known that P2 is true. From these 2 facts it can be concluded that P1 cannot be true. Which of these 2 you call "proof by contradiction"? Probably a better name is needed, because both kinds of demonstrations end in a contradiction, the first contradicts the premise, while the second contradicts an independently known fact. EDIT: Another poster has provided a link to someone who uses the following definition: "A proof by contradiction is a proof of a positive by refutation of the negative." I believe that such a definition refers to a thing so trivial that it does not deserve a special name. Obviously if P is a proposition and it is shown that "not P cannot be true" (refutation of the negative), only in bivalent logic it can be concluded that P must be true. In trivalent logic, that only proves that P is either true or neither true nor false. In real life, bivalent logic is never applicable, as the statements that are neither true nor false are much more frequently encountered than those that are known to be either true or false. So in real life, any "demonstration" by refutation of the negative is almost certainly a logical fallacy.
- butokai 3mo ago
  Neither of the two. A proof by contradiction, as other comments have stated, is: assuming not P1, we reach a contradiction; thus P1 must be true. This is equivalent to tertium non datur in classical logic. I’m not sure it’s a valid deduction in your trivalent logic.
  - adrian_b 3mo ago
    Another poster has provided a link to a definition of "proof by contradiction", which I assume that it is the one that you mean ("A proof by contradiction is a proof of a positive by refutation of the negative."). Unlike in that unambiguous definition, the words used by you are confusing, because "we reach a contradiction" is also applicable to the 2 variants of "Reductio ad absurdum" that I have described. A demonstration like "a proof of a positive by refutation of the negative" is valid only in strictly bivalent logic and invalid in any multivalent logic. The 2 variants of "Reductio ad absurdum" that I have mentioned are also valid in any multivalent logic or modal logic.
dwenzek 3mo ago
Exactly! A very nice explanation of what is and what is not a proof by contradiction is given by R. Harper in "Proofs by contradiction, versus contradiction proofs" [1] - [1] "https://existentialtype.wordpress.com/2017/03/04/a-proof-by-contradiction-is-not-a-proof-that-derives-a-contradiction/ https://existentialtype.wordpress.com/2017/03/04/a-proof-by-...
sxzygz 3mo ago
To be a little more concrete, what it means to prove a negation ¬P (not P) is to assume P and construct an impossibility from it, like 0=1 (assuming those symbols exist in the theory you are working with) or more generally A∧¬A (A and not A) for some A (0=1 being a absurdity, hopefully, because your ambient theory already proves 0≠1). Now to prove P by contradiction, is to assume, the contrary, ¬P and construct an impossibility. But what you have really done here is prove ¬¬P. Now if you are a normal mathematician, you are classical, and hence you believe every statement A is either true or false, i.e. A∨¬A (A or not A, from any statement A, i.e. the law of the excluded middle). It just so happens that if you accept the law of the excluded middle then from ¬¬P you can deduce P. An interesting question is why is the meaning of a proof of negation the construction of an absurdity? I guess this is philosophical, but if you accept the point of logic is to only conclude true things, then concluding an absurdity must be impossible, and hence if you assume something that leads to an absurdity, it follows that there must be no proof of the assumption because otherwise you'd have a proof of absurdity, and hence the meaning of a negation is showing that there is no proof of the pre-negated statement. In logic, ⊥ is used as the symbol for absurdity. Hence ¬P is really shorthand for P⇒⊥ (P implies absurdity), which is why earlier I identified A∧¬A with absurdity since when you have A and A implies absurdity, you immediately deduce absurdity.
futune 3mo ago
I think this is a good comment. Could you also provide an example of a true (essential?) proof of contradiction of an elementary mathematical statement, to illustrate?
arunix 3mo ago
I agree that the prime list example is really a constructive proof. But what about the sqrt(2) and log(2) examples?
- sxzygz 3mo ago
  You give me a rational candidate for √2 and by the argument of the submitted article I “construct” another rational candidate with strictly smaller numerator and denominator. You give me a rational candidate p/q for log 2 and by the argument of the article I “construct” that p = q = 0. In both instances I create a contradiction thus showing that you could not have provided me such a rational to begin with. Now let me show you non-constructively that there are irrationals a and b with a^b rational. To prove this I consider c = √2^√2. I don’t know whether this is rational or irrational so I invoke the law of the excluded middle. Suppose c is rational. Then take a = b = √2 and we have a^b = c where a and b are irrational and c is rational. Otherwise suppose c is irrational. Then take a = c and b = √2 and we have a^b = (√2^√2)^√2 = √2^2 = 2 and again we have our result. What is the difference here? I have no idea whether c is rational or irrational. Either way I can make it work but I can’t tell you which possibility is the genuine one. You can actually make better choices of a and b and show this result constructively. This leads to a deeper question. Are there statements with no constructive proof and how do you prove that. This is beyond my expertise, but there are indeed high-powered logical tools that allow you prove such results for certain statements. The stuff that human beings have done by simply looking at the stars and dreaming really hard is pretty awe-inspiringly incredible.
loicd 3mo ago
The distinction you make is correct in the sense there is indeed a fundamental difference between proving P by assuming not-P and reaching a contradiction and on the other hand proving not-P by assuming P and reaching a contradiction. However, both are called proof by contradiction. It is just plain wrong to say that the second kind is not proof by contradiction. It has been called like that for more than two millenia, whereas intuitionism is a 20th century idea. Besides, if you insist on the difference, then you have to distinguish between positive and negative mathematical properties. For instance, in your example, "finite" is positive and "infinite" is not-finite, so negative. For a classical mathematician, which is most of them, this is actually an undesirable distinction that depends on how things are defined, and is not intuitively clear.
jerome-jh 3mo ago
There is something which always made me uncomfortable with informal proof by contradiction (by informal I mean "with pen and paper"). So OK we reach a contradiction, and then immediately "oh yeah, that is _this hypothesis_ which is wrong". Erh, well why exactly this one? All we know is we started from an inconsistent state. The article enters this territory at the last paragraph and simply concludes "This can be difficult questions to resolve to student's satisfaction", without even trying to answer it.

by butokai 3mo ago

adrian_b 3mo ago

"What can’t be false must me true" is what classic logic called "Tertium non datur", and which has absolutely nothing to do with a demonstration by "Reductio ad absurdum", i.e. with "assuming a fact, showing that it would lead to an absurd". A demonstration by "Reductio ad absurdum" can also be done in multivalent logic, for instance in trivalent logic, where a statement can be true or false or neither true nor false, therefore "Tertium non datur" is not applicable. In my opinion, trivalent logic is the simplest kind of logic that is applicable to mathematics or to the real world. Its subset that is bivalent logic is interesting as an object of study but not as a technique that can be useful for practical reasoning or for mathematical demonstrations. If I understood you correctly, you want to distinguish the following 2 kinds of demonstrations, where P1 and P2 are propositions: 1. One demonstrates that "P1 implies not P1". From this it can be concluded that P1 cannot be true. 2. One demonstrates that "P1 implies not P2". But it is known that P2 is true. From these 2 facts it can be concluded that P1 cannot be true. Which of these 2 you call "proof by contradiction"? Probably a better name is needed, because both kinds of demonstrations end in a contradiction, the first contradicts the premise, while the second contradicts an independently known fact. EDIT: Another poster has provided a link to someone who uses the following definition: "A proof by contradiction is a proof of a positive by refutation of the negative." I believe that such a definition refers to a thing so trivial that it does not deserve a special name. Obviously if P is a proposition and it is shown that "not P cannot be true" (refutation of the negative), only in bivalent logic it can be concluded that P must be true. In trivalent logic, that only proves that P is either true or neither true nor false. In real life, bivalent logic is never applicable, as the statements that are neither true nor false are much more frequently encountered than those that are known to be either true or false. So in real life, any "demonstration" by refutation of the negative is almost certainly a logical fallacy.

butokai 3mo ago
Neither of the two. A proof by contradiction, as other comments have stated, is: assuming not P1, we reach a contradiction; thus P1 must be true. This is equivalent to tertium non datur in classical logic. I’m not sure it’s a valid deduction in your trivalent logic.
- adrian_b 3mo ago
  Another poster has provided a link to a definition of "proof by contradiction", which I assume that it is the one that you mean ("A proof by contradiction is a proof of a positive by refutation of the negative."). Unlike in that unambiguous definition, the words used by you are confusing, because "we reach a contradiction" is also applicable to the 2 variants of "Reductio ad absurdum" that I have described. A demonstration like "a proof of a positive by refutation of the negative" is valid only in strictly bivalent logic and invalid in any multivalent logic. The 2 variants of "Reductio ad absurdum" that I have mentioned are also valid in any multivalent logic or modal logic.

dwenzek 3mo ago

Exactly! A very nice explanation of what is and what is not a proof by contradiction is given by R. Harper in "Proofs by contradiction, versus contradiction proofs" [1] - [1] "https://existentialtype.wordpress.com/2017/03/04/a-proof-by-contradiction-is-not-a-proof-that-derives-a-contradiction/ https://existentialtype.wordpress.com/2017/03/04/a-proof-by-...

sxzygz 3mo ago

To be a little more concrete, what it means to prove a negation ¬P (not P) is to assume P and construct an impossibility from it, like 0=1 (assuming those symbols exist in the theory you are working with) or more generally A∧¬A (A and not A) for some A (0=1 being a absurdity, hopefully, because your ambient theory already proves 0≠1). Now to prove P by contradiction, is to assume, the contrary, ¬P and construct an impossibility. But what you have really done here is prove ¬¬P. Now if you are a normal mathematician, you are classical, and hence you believe every statement A is either true or false, i.e. A∨¬A (A or not A, from any statement A, i.e. the law of the excluded middle). It just so happens that if you accept the law of the excluded middle then from ¬¬P you can deduce P. An interesting question is why is the meaning of a proof of negation the construction of an absurdity? I guess this is philosophical, but if you accept the point of logic is to only conclude true things, then concluding an absurdity must be impossible, and hence if you assume something that leads to an absurdity, it follows that there must be no proof of the assumption because otherwise you'd have a proof of absurdity, and hence the meaning of a negation is showing that there is no proof of the pre-negated statement. In logic, ⊥ is used as the symbol for absurdity. Hence ¬P is really shorthand for P⇒⊥ (P implies absurdity), which is why earlier I identified A∧¬A with absurdity since when you have A and A implies absurdity, you immediately deduce absurdity.

futune 3mo ago

I think this is a good comment. Could you also provide an example of a true (essential?) proof of contradiction of an elementary mathematical statement, to illustrate?

arunix 3mo ago

I agree that the prime list example is really a constructive proof. But what about the sqrt(2) and log(2) examples?

sxzygz 3mo ago
You give me a rational candidate for √2 and by the argument of the submitted article I “construct” another rational candidate with strictly smaller numerator and denominator. You give me a rational candidate p/q for log 2 and by the argument of the article I “construct” that p = q = 0. In both instances I create a contradiction thus showing that you could not have provided me such a rational to begin with. Now let me show you non-constructively that there are irrationals a and b with a^b rational. To prove this I consider c = √2^√2. I don’t know whether this is rational or irrational so I invoke the law of the excluded middle. Suppose c is rational. Then take a = b = √2 and we have a^b = c where a and b are irrational and c is rational. Otherwise suppose c is irrational. Then take a = c and b = √2 and we have a^b = (√2^√2)^√2 = √2^2 = 2 and again we have our result. What is the difference here? I have no idea whether c is rational or irrational. Either way I can make it work but I can’t tell you which possibility is the genuine one. You can actually make better choices of a and b and show this result constructively. This leads to a deeper question. Are there statements with no constructive proof and how do you prove that. This is beyond my expertise, but there are indeed high-powered logical tools that allow you prove such results for certain statements. The stuff that human beings have done by simply looking at the stars and dreaming really hard is pretty awe-inspiringly incredible.

loicd 3mo ago

The distinction you make is correct in the sense there is indeed a fundamental difference between proving P by assuming not-P and reaching a contradiction and on the other hand proving not-P by assuming P and reaching a contradiction. However, both are called proof by contradiction. It is just plain wrong to say that the second kind is not proof by contradiction. It has been called like that for more than two millenia, whereas intuitionism is a 20th century idea. Besides, if you insist on the difference, then you have to distinguish between positive and negative mathematical properties. For instance, in your example, "finite" is positive and "infinite" is not-finite, so negative. For a classical mathematician, which is most of them, this is actually an undesirable distinction that depends on how things are defined, and is not intuitively clear.

jerome-jh 3mo ago

There is something which always made me uncomfortable with informal proof by contradiction (by informal I mean "with pen and paper"). So OK we reach a contradiction, and then immediately "oh yeah, that is _this hypothesis_ which is wrong". Erh, well why exactly this one? All we know is we started from an inconsistent state. The article enters this territory at the last paragraph and simply concludes "This can be difficult questions to resolve to student's satisfaction", without even trying to answer it.