patternMajor
Can proof by contradiction work without the law of excluded middle?
Viewed 0 times
withoutcantheexcludedcontradictionworkmiddlelawproof
Problem
I was recently thinking about the validity of proof by contradiction. I’ve read for the past few days things on intuitionistic logic and Godel’s theorems to see if they would provide me answers to my questions. Right now I still have questions lingering (perhaps related to the new material I read) and was hoping to get some answers
(WARNING: you are about to proceed to read content with very confused foundations in logic, take everything with a grain of salt, its suppose to be a question and not an answer, there are many misunderstandings in it).
I think my main question is, once we showed that not A leads to some contradiction, so not A must be false, then we go and conclude that A must be true. That part sort of makes sense (especially if I accept the law of excluded middle as something that makes sense) but what bothers me is sort of how proof by contradiction actually occurs. First we start with not A and then we just apply axioms and rules of inferences (say mechanically) and see where that takes us. It usually reaches a contradiction (say A is true or $\neg \varphi$ and $\phi$ is true). The we conclude that not A must be false, so A is true. Thats fine. But my question is, what sort of guarantees do formal systems have that if I applied the same process but started with A that I would not also get a contradiction there? I think that there is some hidden assumption going on in proof by contradictions that if similarly did the same process in A one would not reach a contradiction, what sort of guarantees do we have that would not happen? Is there a proof that’s impossible? In other words if I had a Turning Machine (TM) (or super TM) that went forever, that tried all the logical steps from every axiom starting from the supposedly true statement $A$, what guarantees that it does NOT HALT due to finding a contradiction?
I then made some connections with my past question with Godel’s incompleteness theorem that goes something like this:
A formal system F th
(WARNING: you are about to proceed to read content with very confused foundations in logic, take everything with a grain of salt, its suppose to be a question and not an answer, there are many misunderstandings in it).
I think my main question is, once we showed that not A leads to some contradiction, so not A must be false, then we go and conclude that A must be true. That part sort of makes sense (especially if I accept the law of excluded middle as something that makes sense) but what bothers me is sort of how proof by contradiction actually occurs. First we start with not A and then we just apply axioms and rules of inferences (say mechanically) and see where that takes us. It usually reaches a contradiction (say A is true or $\neg \varphi$ and $\phi$ is true). The we conclude that not A must be false, so A is true. Thats fine. But my question is, what sort of guarantees do formal systems have that if I applied the same process but started with A that I would not also get a contradiction there? I think that there is some hidden assumption going on in proof by contradictions that if similarly did the same process in A one would not reach a contradiction, what sort of guarantees do we have that would not happen? Is there a proof that’s impossible? In other words if I had a Turning Machine (TM) (or super TM) that went forever, that tried all the logical steps from every axiom starting from the supposedly true statement $A$, what guarantees that it does NOT HALT due to finding a contradiction?
I then made some connections with my past question with Godel’s incompleteness theorem that goes something like this:
A formal system F th
Solution
You asked (I am making your question a bit crisper): "What formal guarantee is there that it cannot happen that both $\lnot p$ and $p$ lead to a contradiction?" You seem to worry that if logic is inconsistent, then proof by contradiction is problematic. But this is not the case at all.
If logic is inconsistent then proof by contradiction is still very much a valid rule of reasoning, but so is its negation, and the rule which says that from $1 + 1 = 2$ we can conclude that you are the next pope. An inconsistency in logic does not invalidate anything: quite the opposite, it validates everything!
There is another possible source of confusion: the title of your question may be read as implying that the law of excluded middle says that logic is consistent. That is incorrect. Consistency of logic amounts to “it is not the case that both a statement and its negation have proofs”, while excluded middle is the rule which allows us to prove statements of the form $p \lor \lnot p$.
Supplemental: I do not understand why this question is generating so much discussion. I have trouble understanding what the dilemma actually is, and as far as I can tell, the question arises from some sort of misunderstanding. If someone can elucidate the question, I will be grateful. Also, I would just like to draw attention to the following points:
-
Proof by contradiction and excluded middle are equivalent to each other, and so the title, as written, is non-sensical. Of course we cannot have one without the other, they are equivalent.
-
From what I can understand from the lengthy discussion in the question, the OP seems to be saying, or worrying, that an inconsistency in logic invalidates a proof. This is false, as I pointed out above. I would appreciate some sort of a response from the OP: can the OP see how an inconsistency in logic (i.e., being able to prove everything) does not invalidate any proofs?
-
I find it likely, but cannot really tell for sure, that the OP thinks that the law of excluded middle states that it is impossible for both $p$ and $\lnot p$ to hold (with a formula: $\lnot (p \land \lnot p)$). This is not excluded middle. It is sometimes called the law of non-contradiction, and it is provable (without excluded middle).
-
The OP thinks it is "impossible to directly prove that something is false without excluded middle". He is confusing proof of negation and proof by contradiction, which are not the same thing. The linked post has plenty of examples of constructive proofs that something is false. In fact, most proofs that something is false found in textbooks are already constructive.
-
Gödel's incompleteness is dragged in for a reason that I can discern. Gödel's incompleteness provides a sentence $G$ such that neither $G$ nor $\lnot G$ is provable. This does not imply that $G \lor \lnot G$ is unprovable (it is, by a simple application of excluded middle)! Neither does it imply that $\lnot G \land \lnot\lnot G$ holds, or some such. So how is Gödel's incompleteness relevant here?
P.S. I apologize for the previous version of the supplemental which was rude.
If logic is inconsistent then proof by contradiction is still very much a valid rule of reasoning, but so is its negation, and the rule which says that from $1 + 1 = 2$ we can conclude that you are the next pope. An inconsistency in logic does not invalidate anything: quite the opposite, it validates everything!
There is another possible source of confusion: the title of your question may be read as implying that the law of excluded middle says that logic is consistent. That is incorrect. Consistency of logic amounts to “it is not the case that both a statement and its negation have proofs”, while excluded middle is the rule which allows us to prove statements of the form $p \lor \lnot p$.
Supplemental: I do not understand why this question is generating so much discussion. I have trouble understanding what the dilemma actually is, and as far as I can tell, the question arises from some sort of misunderstanding. If someone can elucidate the question, I will be grateful. Also, I would just like to draw attention to the following points:
-
Proof by contradiction and excluded middle are equivalent to each other, and so the title, as written, is non-sensical. Of course we cannot have one without the other, they are equivalent.
-
From what I can understand from the lengthy discussion in the question, the OP seems to be saying, or worrying, that an inconsistency in logic invalidates a proof. This is false, as I pointed out above. I would appreciate some sort of a response from the OP: can the OP see how an inconsistency in logic (i.e., being able to prove everything) does not invalidate any proofs?
-
I find it likely, but cannot really tell for sure, that the OP thinks that the law of excluded middle states that it is impossible for both $p$ and $\lnot p$ to hold (with a formula: $\lnot (p \land \lnot p)$). This is not excluded middle. It is sometimes called the law of non-contradiction, and it is provable (without excluded middle).
-
The OP thinks it is "impossible to directly prove that something is false without excluded middle". He is confusing proof of negation and proof by contradiction, which are not the same thing. The linked post has plenty of examples of constructive proofs that something is false. In fact, most proofs that something is false found in textbooks are already constructive.
-
Gödel's incompleteness is dragged in for a reason that I can discern. Gödel's incompleteness provides a sentence $G$ such that neither $G$ nor $\lnot G$ is provable. This does not imply that $G \lor \lnot G$ is unprovable (it is, by a simple application of excluded middle)! Neither does it imply that $\lnot G \land \lnot\lnot G$ holds, or some such. So how is Gödel's incompleteness relevant here?
P.S. I apologize for the previous version of the supplemental which was rude.
Context
StackExchange Computer Science Q#88343, answer score: 30
Revisions (0)
No revisions yet.