Wikipedia:Reference desk/Archives/Mathematics/2020 December 26

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

December 26

Can proof by contradiction ever be wrong?

More specifically, is there ever a case in which, if the negation of a statement is false, the actual statement is also false? JJP...MASTER!_{[talk to] JJP... master?} 20:11, 26 December 2020 (UTC)

The final question is independent of the proof technique of "proof by contradiction". It is actually more general than the question in the heading, instead of more specific. In formal logic, it is customary to use the letter P (the first letter of "proposition") to stand for an arbitrary statement; for example, "2⁶⁵ < 3⁴¹", or, "1111111 is evenly divisible by 4649". Just "P", or, more verbose, "P is true", mean the same. The negation of P, which I notate here as "¬P", stands then for the statement "P is false", or, which is the same, "P is not true". What can be proved in a given logic depends on the rules of the logic. If the negation of statement is P false, we can denote that as ¬¬P, a double negation. The question is now, is it ever possible that at the same time ¬¬P and ¬P? This is a slightly more specific instance of the question, can P and ¬P both hold at the same time? Using a notation for logical conjunction, these two can be combined into a single formula:

P ∧ ¬P.

If both hold, there is a contradiction. A formal system in which a contradiction can occur is called inconsistent. This is generally considered highly undesirable. In a normal logic, the principle of explosion applies: if even one contradiction can be proved, then any statement expressible in the logic can be proved. If everything is true – 2 + 2 = 5, the Moon is made of green cheese, and you do not exist – then everything loses its meaning. The distinction between statements that are true and statements that are false, kept sharp in most logics, may become more fuzzy in real life. There is a grey area between "it is raining" and "it is not raining"; neither may be fully true. There have been attempts to create logic systems that can deal with such situations and do not immediately explode with any contradiction; see Paraconsistent logic. There are also many-valued logics, which acknowledge intermediate truth values between true and false; see also Fuzzy logic. However, these generally still exhibit the principle of explosion.  --Lambiam 23:12, 26 December 2020 (UTC)

Proof by contradiction has been used since Euclid. Indeed, if a method of proof is incorrect then the result cannot be called a proof. There are some schools of mathematical philosophy that object to indirect proofs (aka proofs by contradiction), and have some convincing arguments against using them, but afaik an indirect proof is acceptable in most areas of mathematics. The objections against indirect proof center around the assumption that a statement must be either true or false. The events of the 20th century cast some doubt on this assumption, for example the discovery that there are statements which can neither be proven nor disproven. The assumption that a statement and it's negation cannot be both true seems to be fundamental to mathematics though. --RDBury (talk) 15:15, 28 December 2020 (UTC)

Note that the posting contains two questions: the question in the heading, and a different question in the following text.  --Lambiam 19:31, 28 December 2020 (UTC)

I did notice that, and I was tempted to just ask for clarification SE style. In 1899 the two versions would be considered equivalent; men were men, women were women, and mathematical statements were either true or false. But then Russell's paradox, the Brouwer–Hilbert controversy, Gödel's incompleteness theorems, etc. It's hard to explain the difference without bringing in all that history, which may be irrelevant to the OP for all we know. --RDBury (talk) 01:12, 29 December 2020 (UTC)

Lambiam, The second question was intended to simply be a more specific version of the first question. JJP...MASTER!_{[talk to] JJP... master?} 02:46, 29 December 2020 (UTC)

I understood it was meant to be that, but I thought I should point out it was not. Once we get to a discussion of the validity and reliability of proof methods, slight nuances in formulation that are insignificant when discussing everyday events may make a major difference. Consider the following proof of the claim, "Every statement is logically equivalent to a decidable statement." It goes as follows. Let P be an arbitrary statement. It is a tautology that P ∨ ¬P, which we may rewrite as P≡T ∨ P≡F, so either P≡T or P≡F. Now T (true) and F (false) are both (trivially) decidable statements, so in either case P is logically equivalent to a decidable statement. End of proof. While clearly bogus, it is not easy to point out the spot where this goes astray. Coming back to the original question(s), an immediate issue is what it means for a statement to be false. The combination of the reference to "proof by contradiction" in the header with "if the negation of a statement is false" suggests that it means provably false, since a proof by contradiction of some statement needs a proof of the falsehood of its negation. Then, I think, we should also assume that "the actual statement is also false" means that it is provably false. In that case the logic system in which these proofs were given is inconsistent. Any reasonable logic accepts an argument by modus ponens. Expressed in formulas, this means that if we have a proof of some statement P as well as of an implication P→Q, we can combine these proofs to give us a proof of Q. Consider that "the negation of P is false" corresponds to the formula "¬¬P", which is equivalent to "(¬P)→F". So the question is, can the situation ever arise in which we have a proof of (¬P)→F as well as a proof of ¬P. Well, should this situation arise, then, unless the logic is lame, we can combine these two proofs to give a proof of F. So the system we used for these proofs is inconsistent. And conversely, if a logic system is not consistent, you can prove anything, including both ¬¬P and ¬P. Many proposed systems have been shown to be inconsistent; the first documented instance is known as Russell's paradox, which dealt a death blow to the system Frege's had laid down in his magnum opus The Foundations of Arithmetic. Much more recently, Girard's paradox showed an early version of Martin-Löf's type theory to be inconsistent.  --Lambiam 12:09, 29 December 2020 (UTC)

Me, I would say that the statements

I have stopped beating my wife

I have not stopped beating my wife

are both false. —Steve Summit (talk) 17:46, 30 December 2020 (UTC)

Whoever said the human race was logical?  --Lambiam 20:54, 30 December 2020 (UTC)

Consider a quantum computer. We then have qubits that can be in superpositions of the basis states |0> and |1>. The NOT operator interchanges these basis states, which then defines how NOT acts on a general superposition. It then follows that the NOT operator leaves the state 1/sqrt(2) [|0> + |1>] invariant. Count Iblis (talk) 01:14, 1 January 2021 (UTC)