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 that con express arithmetic cannot prove its own consistency (within F).
This basically made it clear to me that if thats true then consistency i.e. guaranteeing that A and not A won’t happen is impossible. Therefore, it made it seem to be that proof by contradiction just implicitly assumes that consistency is guaranteed somehow (otherwise why would it just go ahead and conclude that A is true by proving not A is not possible if it didn’t already know that consistency and contradiction where fine, for any pair of statement A and not A)? Is this incorrect or did I miss something?
Then I thought, ok lets just include in our axioms the rule of excluded middle and then all problems are solved. But then I realized, wait if we do that we are just defining the problem away instead of dealing with it. If I just force my system to be consistent by definition that doesn’t necessarily mean it actually is consistent…right? I’m just trying to make sense of these ideas and I am not quite sure what to do but this is what I am realizing after a few days of reading stuff and watching videos in nearly every aspect of these concepts, contradiction, exclusive middle, intuitionist logic, Godel’s completeness and incompleteness theorems…
Related to this, it seems that its essentially impossible to actually directly prove that something is false without the rule of excluded middle (or contradiction). It seems that proof systems are good at proving true statements but to my understanding are incapable of directly showing that things are false. Perhaps the way they do it is more indirectly with contradiction (where they show something must be false or bad things happen), or excluded middle (where knowing the truth value of only one A or not A gives us the truth of the other) or providing counter examples (which basically shows that the opposite is true so indirectly uses law of excluded middle). I guess perhaps I really want a constructive proof that something is false?
I think if I could know that if I prove not A is false (say I accept contradiction) then that it really is ok and I don’t need to apply all the inference rules and axioms infinitely on A and I am guaranteed that A won’t reach a contradiction. If that were true then I think I could accept proof by contradiction more easily. Is this true or do Godel’s second incompleteness guarantee I can’t have this? If I can’t have this then, what puzzles me is how its even possible of so many years of mathematicians doing maths that we have not found a inconsistency? Do I need to rely on empirical evidence of consistency? Or for example, I prof F is consistent by showing superF proves F but since I will never actually need superF and just F, then I can’t be content that truly works?
I just noticed that my complaint also generalizes to direct proofs. Ok so if I did a direct proof of A then I know A is true...but how do I know that if I did a direct proof of not A that I wouldn't also get a correct proof? Seems the same question just slightly different emphasis....