0
$\begingroup$

A very simple question about the relationship between incompleteness and consistency of any theory strong enough to express PA.

We know from Gödel that if such a theory is consistent, then it is incomplete (First incompleteness theorem). We also know that, if such a theory is consistent, it cannot prove its own consistency (Second incompleteness theorem).

But we also know that if a theory is inconsistent, then it is complete. So, why can't we infer from the fact that a given theory T is incomplete that T is consistent? The reasoning is that if T is inconsistent, then we could not find statements that are not provable in it.

It seems this conclusion is false because it contradicts the Second incompleteness theorem. But where's the flaw in the reasoning? Possible explanations I could come up with so far:

  • It is trivially the case that if a theory is inconsistent, then it is complete. But within the inconsistent theory, one could both "prove" that T is both complete and incomplete, i.e. it is false that "we could not find statements that are not provable in it". So really nothing follows from the fact a theory is provably incomplete.

  • The reasoning is sound; the reason this does not work is that it cannot be done in T, but is only an observation about T in a metatheory (which would again be subject to the Incompleteness theorems)?

$\endgroup$
5
$\begingroup$

Yes, an incomplete theory is in fact consistent.

But Gödel's theorem is a theorem about $\sf ZFC$, or $\sf PA$, and it is done in the meta-theory. And in the meta-theory, we assume that $T$ is consistent. Otherwise, there's no point in investigating it, is there?

The "fact" that $\sf ZFC$ is incomplete follows from the fact that it is consistent. Namely, the correct fact is "If $\sf ZFC$ is consistent at all, then it is incomplete".


Just a minor remark, though, there is an additional requirement for the incompleteness theorems, that the theory is recursively enumerable. Otherwise, simply take $\operatorname{Th}(\Bbb N)$, and this is a complete theory which is consistent and interprets Peano arithmetic. In fact, this is how you prove that $\operatorname{Th}(\Bbb N)$ is not recursively enumerable.

$\endgroup$
1
$\begingroup$

There is also the important fact that the proof of Godel’s first incompleteness theorem assumes the consistency of PA/ZFC, and so deriving the consistency of such a system from the incompleteness theorem would be circular. Additionally, from a contradiction anything will follow- so proving any statement does not entail in the metatheory that the system is consistent.

$\endgroup$
  • $\begingroup$ Yes, I did say exactly that in my answer. That the correct "fact" would be "If ZFC is consistent at all, then it is incomplete". $\endgroup$ – Asaf Karagila Mar 12 '18 at 21:24
  • $\begingroup$ Yes; I was pointing out that not only is your answer correct, but what would be wrong with saying that consistency follows from the incompleteness of ZFC- such an argument would be circular. $\endgroup$ – Rachael Alvir Mar 13 '18 at 0:13
  • $\begingroup$ No, that's actually incorrect. An incomplete theory is almost by definition a consistent one, as it does not prove contradictions. However it is false to say that the incompleteness theorem implies the consistency of ZFC (or any theory it's applied to), because the incompleteness theorem is a conditional which is vacuously true if the theory is inconsistent. $\endgroup$ – Asaf Karagila Mar 13 '18 at 6:39
  • $\begingroup$ What you have mentioned is precisely what it means for an argument to be circular. Yes, the fact is a conditional: “If ZFC is consistent, then ZFC is incomplete.” The following is an incorrect proof of ZFC: “If ZFC is consistent , then ZFC is incomplete. Therefore ZFC is consistent.” It is incorrect because, as you say, the antecedent of the first conditional could be false. That is exactly what it means for the argument to fail because it is circular. I believe we are actually on the same page. $\endgroup$ – Rachael Alvir Mar 13 '18 at 14:37
  • $\begingroup$ Nowhere in my post or comments have I claimed that "ZFC is consistent" is a consequence of the incompleteness theorem. You claim, incorrectly, that the incompleteness theorem assumes the consistency, whereas I point out that it does not. You don't need to assume the consistency of the theory in question, it just a reasonable assumption, since otherwise the statement is vacuously true. However if you proved that a theory is incomplete, then you have proved it is consistent. Since the incompleteness theorem does not prove that ZFC is incomplete, it does not prove it is consistent. [...] $\endgroup$ – Asaf Karagila Mar 13 '18 at 14:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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