2
$\begingroup$

We can construct a Turing Machine M whose behavior is independent of ZFC by making it look for a contradiction in ZFC.

But I also know that if any Turing Machine does in fact halt, it can always be proved in ZFC. Therefore, if we can prove (in ZFC) that a Turing Machine's behavior is independent of ZFC, then this machine must in fact never halt.

So then, don't we "know" that M (see above) will never halt? Why is it dependent of the consistency of ZFC? It seems to me that ZFC can prove that M is independent of ZFC, and ZFC can also prove that if a Turing Machine's behavior is independent of ZFC then this machine does not halt. So why can't ZFC prove that M never halts?

I get that if ZFC were to be inconsistent, than the negation could also be proved. But isn't this the case for all theorems of ZFC? The Gödel sentences are those ones whose truth and provability depend on the consistency of the system, whereas in this case mentioned above it seems that it is only the truth (of the statement 'M never halts') that is dependent on the consistency of ZFC.

I am sure I am missing something, and would like to understand it better.

$\endgroup$

1 Answer 1

2
$\begingroup$

The error is in the second paragraph, where you wrote "Therefore, if we can prove (in ZFC) that a Turing Machine's behavior is independent of ZFC, then this machine must in fact never halt." A correct version of this is "Therefore, if we can prove (in ZFC) that a Turing Machine's behavior is independent of ZFC, and if ZFC is consistent, then this machine must in fact never halt." The point is that proving (in ZFC) that something is independent doesn't guarantee anything (in particular it doesn't guarantee actual independence) unless ZFC is consistent.

So in your next sentence, we know that $M$ won't halt if we know that ZFC is consistent. But we knew that anyway, by definition of $M$.

$\endgroup$
4
  • $\begingroup$ Thanks for the response Andreas. But then, what is the difference between proving that a statement is independent in ZFC and proving any other theorem, say Fermat's Last Theorem (FLT) in ZFC? When we prove FLT in ZFC, we don't say that FLT is independent of ZFC because if ZFC is inconsistent, the negation of FLT could be proven. We just say FLT has been proved. My sense is that the sentence "Turing Machine M is independent of ZFC" is the same kind of sentence as FLT, i.e., it is not a Gödel sentence. So I still can't see why it should depend (at least its provability) on the consistency of ZFC $\endgroup$ May 15, 2022 at 2:56
  • $\begingroup$ @CharbelBejjani The difference between "ordinary" theorems like FLT and statements of the form "X is independent of ZFC" is that the latter imply (finitistically) the consistency of ZFC and the former do not. As a consequence, by Gödel's second incompleteness theorem, the latter cannot be proved in ZFC (unless ZFC is inconsistent) while some of the former (including FLT) can. $\endgroup$ May 15, 2022 at 13:13
  • $\begingroup$ So is the statement "X is independent of ZFC" a Gödel sentence of ZFC? $\endgroup$ May 15, 2022 at 16:44
  • $\begingroup$ @CharbelBejjani Not necessarily. It implies consistency, but, depending on X, it might not follow from consistency. After all, some statements are provable or refutable in ZFC. $\endgroup$ May 15, 2022 at 20:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .