0
$\begingroup$

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?

$\endgroup$
5
  • 3
    $\begingroup$ If the model of computation is contradictory, then you immediately prove "the decider cannot exist" by the principle of explosion. $\endgroup$
    – Dmitry
    Nov 21, 2022 at 3:38
  • $\begingroup$ Your question asks many different things. The existing answers probably address the main point of confusion, but not what you asked. For the title question, the answer depends on how constructive you require mathematics; intuitionist schools of thought would generally lean towards "no." As for Godel's incompleteness theorems, this is not directly related. $\endgroup$
    – BurnsBA
    Nov 21, 2022 at 17:34
  • $\begingroup$ Your point 2 is not what it shows. If your model is non-consistent, then it's useless as a model. It is possible, however, that the model you used doesn't describe the actual system (a model is an abstract description, based on certain assumptions, and if those assumptions don't hold, then the inferences don't apply in general). But that's always a possibility, regardless of any results you got, and it's on you, the modeler, to determine if the model fits and under what circumstances. $\endgroup$ Nov 21, 2022 at 22:30
  • 1
    $\begingroup$ So what you're proving is nonexistence assuming that things are as described by the model. $\endgroup$ Nov 21, 2022 at 22:35
  • $\begingroup$ You may also be interested in the (unrelated) concept of "reducing a problem to an NP-complete problem". In there, you prove a problem is hard by showing that if that problem were easy, then you can solve a previously proven-to-be-hard problem easily, and then considering this as a contradiction to a known truth, which shows that the problem cannot be easy. $\endgroup$
    – justhalf
    Nov 21, 2022 at 23:34

5 Answers 5

20
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ Well if (i === i++) then the Pope and I are one. Wait... $\endgroup$ Nov 22, 2022 at 2:02
  • $\begingroup$ "If in addition your system is contradictory, then it will also prove that the decider exists, as well as…" What about systems that are not explosive, like minimal logic? $\endgroup$
    – user76284
    Nov 22, 2022 at 7:17
  • 5
    $\begingroup$ Ex falso sum pontifex. $\endgroup$
    – Pseudonym
    Nov 22, 2022 at 8:15
  • $\begingroup$ @user76284: If we use a non-standard notion of falsity and negation, then of course things might be different. But I think it's safe to assume that the OP had in mind the kind of logic that is used in everyday informal math. $\endgroup$ Nov 23, 2022 at 7:46
6
$\begingroup$

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).

$\endgroup$
2
  • 6
    $\begingroup$ ‘I note that every proof by contradiction can be converted (mechanically) into one that does not use proof by contradiction.’ — this is profoundly false. $\endgroup$ Nov 21, 2022 at 12:11
  • $\begingroup$ @user3840170, I have removed the statement that you objected to. (I'm trying to focus on what I see as the central confusion of the original poster, without getting side-tracked onto the topic of constructive/intuitionist logics vs non-constructive logics - a topic that is fascinating, to be sure, but doesn't seem to be a core issue for the undecidability proofs one is likely to run into at the poster's level, as those proofs can be rewritten in a form that both camps would be happy with.) $\endgroup$
    – D.W.
    Nov 21, 2022 at 18:36
5
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.