Does contradiction definitively prove nonexistence

Question

It is common to have proofs that use contradiction to show that some language is undecidable in computability theory.

An example proof can be seen in 4.2 Undecidability “Introduction to the Theory of Computation” by Sipser proving 4.11 the undecidability of A_tm.

Basically, these proofs assume the existence of a decider for the undecidable language in question. They then find a contradiction due to their existence.

What I would like to better understand is how does a contradiction prove nonexistence? Couldn’t it instead be the case that the whole model of computability is flawed in a way that it allows for contradictions?

Basically, it seems to me that assuming some decider exists and arriving at a contradiction shows either:

1. the decider cannot exist OR
2. the model of computation is flawed in a way that there can be deciders that cause logical contradictions

Wouldn’t this be somewhat related to Godel’s incompleteness concepts?

Answer 1

A proof is a proof, even if the system you work in is inconsistent.

So if you prove that the existence of a decider leads to contradiction, you have proved that such a decider does not exist. If in addition your system is contradictory, then it will also prove that the decider exists, as well as that you are the Pope. But your proof of non-existence will remain valid. You might want to change the system, though.

Answer 2

That's not how I would describe it. I would say, the proof proves that such a decider cannot exist.

I know that many people find proof by contradiction unconvincing or it makes them uncomfortable, and they wonder whether one can really trust the results one obtain via such proofs. The undecidability results you're likely to run into can typically also be proved, without using proof by contradiction (and in my experience it typically is quite easy to transform the proofs accordingly). So, one can go through the straightforward exercise of converting that proof into one that doesn't use proof by contradiction. I suggest you ask yourself, as a thought experiment, whether you would have the same reaction if you were shown a proof of the result that didn't use proof by contradiction.

Suppose I show you a theorem that $\sqrt{2}$ is irrational. Do you conclude that there does not exist any rational fraction $p/q$ such that $(p/q)^2=2$? Or, do you conclude that either such a fraction does not exist, or else mathematics is flawed in such a way that makes such theorems untrustworthy? I suppose in some sense both conclusions are valid, but normally we trust in mathematics and go with the former conclusion. The same applies this situation here. There is nothing special about these undecidability proofs that requires adding some extra "or else math is flawed" clause.

Of course, if there is a logical contradiction in math, then you can prove everything: you can prove that $1+1=2$, that $1+1=3$, that $\sqrt{2}$ is irrational, that $\sqrt{2}$ is rational, that there is no decider for an undecidable problem, that there is a decider for an undecidable problem. In particular, it is reasonable to conclude that there is no decider for the problem (even if there is a logical contradiction in math, then that implies there is no decider for the problem, by the prior remarks).

Answer 3

Implication

All of science is built on the principle of implication: truth can only imply truth. It cannot imply falsehood. False can imply anything, therefore you cannot rely upon it to derive truth. By starting with a set of truths, one can derive more truths without a falsehood sneaking in. This is logically necessary. If your system of reasoning does not provide this guarantee, then you have no system of reasoning at all, and no reliable way to derive new truths. You might as well resort to crystal balls and magic lamps.

If you derive a contradiction in a chain of reasoning, and the steps in the chain are all proper implications, then the starting premise cannot be true, because a contradiction is exactly the statement: T -> F (true implies false). The entire system of constructing proofs is a framework for ensuring that each step is indeed a proper implication that preserves the "truthiness" of the original premise. Thus, when you arrive at a step in which you imply false, you can collapse the chain of implications backwards by saying: "Therefore, step 9's premise is false. Since step 8 implies step 9, step 8's premise is false. Since step 7 implies step 8, step 7's premise is false." All the way back to: "Therefore, my starting premise is false."

If this entire mechanism has a hole in it, one that allows truth to derive false, then you have not discovered a powerful new truth: you have destroyed the very system that allows you to systematically derive truth to begin with. You have essentially destroyed your very ability to conduct science and mathematics at all.

If you wish to make any kind of scientific statement at all, via experimental or logical proofs, you need to have a system of logic which implements implication to begin with. And once you have material implication, you have non-contradiction and proof by contradiction as inevitable consequences of that. If you somehow lose proof by contradiction, then you also lose implication, and you now must find some other way to arrive at truth. But don't claim that your new system is based on logic, because it's not.

Sudoku

It might help to think of proofs like a sudoku puzzle. If you reach a point where the number 3 appears twice in the same row, you have a problem: you either made a mistake in your deductions, or you don't have a valid sudoku puzzle. What you cannot say is: "My deductions are all valid, this puzzle is a valid sudoku, and there are multiple 3s in this column. I have discovered that sudoku admits this possibility." It does not. The very definition of sudoku prevents this possibility. At no point will you have discovered that sudoku is flawed in a way that allows duplicate numbers.

That's because the definition of sudoku does not allow it. If you have a grid with duplicates, then it's not a sudoku puzzle. It's just a grid with numbers. And if you have a proof that leads to a contradiction, you don't have evidence that mathematics is broken, because the premise is true after all. What you have is a broken proof or a broken premise.

Goedel's Theorems

You are suggesting that Goedel's Incompleteness Theorems will save you by saying: "I proved that P leads to a contradiction, but Goedel tells me that P is really true after all!" That is not what the theorems say. They say that a sufficiently complex proof system is either incomplete or inconsistent. If it's inconsistent, then it's useless: you can prove T -> F, and thus you can prove any statement you like in it. You cannot use an inconsistent system to discover actual truth. Therefore, scientists and mathematicians choose to work in incomplete systems, with the consequence that some statements will be true, but you will not be able to prove they are true within that system (but you can by creating a larger system that contains it).

An undecidable statement is one in which assuming it true does not lead to a contradiction, but assuming it false also does not lead to a contradiction. And thus, the rules of the formal system are unable to determine whether the statement is true or false. On the other hand, if a statement derives false, then in that formal system, the statement is false, full stop.

There is clearly an asymmetry between truth and falsehood and how they propagate and what you can learn from them. And this is why these results can sometimes be confusing. But it is also why they are so powerful: truth is more restrictive than falsehood, which is why it is so difficult to maintain a web of lies. You only need one contradiction to see that the web is a fabrication. Truth networks need no self-consistency effort, because it is an intrinsic property of truth itself.

Conclusion

Systematically discovering truth works because material implication is a "truth-preserving" operation. Once you derive false (i.e., a contradiction), you can propagate that all the way back to the starting premise. If this process is not valid, then your entire system of procedure is also not valid, and you do not have a reliable system for discovering truth.

Answer 4

The whole idea of the ad-absurdum proofs is that the world we prove something in is based on logic and is logically consistent. This is kind of an axiom (a given).

If you now show that some assumption leads to a contradiction, you show that either one is true:

• The assumption is false.
• The way you use to show “assumption ⇒ contradiction” is flawed.
• The world in which you show this is not logically consistent.

But the last point is so disruptive that it also moots all the logical conclusions we can draw here, so it isn’t really worth examining. At least not in a logical discussion; it might make sense in a philosophical discussion.

That leaves two possible culprits: Either the assumption is wrong or the proof is flawed. If you can rule out the latter (by working thoroughly, having a proper peer-review, etc.), the assumption must be wrong.

So, yes, if something leads to a contradiction, it means it cannot be true in a logically consistent world. If your assumption was the existence of something, that something doesn’t exist.

Answer 5

Another way to look at it is, by reaching a contradiction you've shown that one of your assumptions is incorrect. This is usually the assumption stated at the start of the proof, but it could also be another, unstated assumption. "The system I'm working in is inconsistent" is one possibility (albeit unlikely).

This isn't just theoretical. It's actually fairly common for a proof to be submitted, only for a reviewer to find a hidden assumption in the proof. In rare cases this can be so subtle that it takes years or even decades to find.