13

Is it true that every undecidable decision problem has an instance whose solution is independent of ZFC?

For example, let $G$ be a finitely-presented group with undecidable word problem. Does there necessarily exist a finite word $w$ over the generators of $G$ such that the statement "$w$ represents the identity" is independent of ZFC?

Jim Belk
  • 49,278
  • I am curious as to why you think this might be true. It sounds like you have heard it somewhere? (Nice question though!) – user1729 Aug 11 '13 at 18:12
  • 1
    This is related, as the word problem is -essentially- the halting problem. – user1729 Aug 11 '13 at 18:15
  • 1
    @user1729 I have heard this before for the halting problem, which makes me think that it ought to be true in general. – Jim Belk Aug 11 '13 at 18:34
  • 1
    Okay, well, the proofs of insolubility of the word problem basically encode an arbitrary Turing machine, and you can use the halting problem stuff you heave heard about. Then, basically, all proofs of insoluble decision problems (okay, almost all...) reduce to the insolubility of the word problem for a -basically arbitrary- base group. So, well, I believe the answer is "yes". – user1729 Aug 11 '13 at 18:42

1 Answers1

8

I think the answer is yes if you believe that ZFC is true. If all instances of the decision problem were provable or disprovable in ZFC, then you can decide the decision problem for a given instance just by simultaneously searching for a proof and a disproof of the instance in ZFC. (You need the hypothesis that ZFC is true to show that this actually does decide the problem.)

Edit: Instead of "ZFC is true", maybe a better way to phrase it is this: Suppose the decision problem is to decide whether or not $\phi(n)$ for $n\in\mathbb{N}$. Then the hypothesis that all instances are decidable by ZFC is: $\forall n\, \left[(\mathrm{ZFC}\vdash\phi(n))\vee(\mathrm{ZFC}\vdash\neg\phi(n))\right]$.

In order to know that the above procedure actually does decide the problem, you have to know that $\forall n\,\left[ (\mathrm{ZFC}\vdash\phi(n))\rightarrow \phi(n)\right]$ and $\forall n\, \left[(\mathrm{ZFC}\vdash\neg\phi(n))\rightarrow \neg\phi(n)\right]$. One way to guarantee this would be if you believed that for all sentences $\psi$, $(\mathrm{ZFC}\vdash\psi)\rightarrow\psi$ (this is what I informally meant by "ZFC is true"). Note that this is stronger than "ZFC is consistent", since "ZFC is consistent" is obtained by taking $\psi$ to be False.

mkoconnor
  • 196