¿Tiene un problema de decisión indecidible una instancia independiente de ZFC?

Question

¿Es cierto que todo problema de decisión indecidible tiene una instancia cuya solución es independiente de ZFC?

Por ejemplo, dejemos que $G$ sea un grupo finitamente representado con undecidible problema de palabras . ¿Existe necesariamente una palabra finita $w$ sobre los generadores de $G$ de manera que la declaración " $w$ representa la identidad" es independiente de ZFC?

Answer 1

Creo que la respuesta es sí si se cree que la ZFC es cierta. Si todas las instancias del problema de decisión fueran demostrables o refutables en ZFC, entonces se puede decidir el problema de decisión para una instancia dada simplemente buscando simultáneamente una prueba y una refutación de la instancia en ZFC. (Se necesita la hipótesis de que ZFC es verdadera para demostrar que esto realmente decide el problema).

Edición: En lugar de "ZFC es verdadera", tal vez una mejor manera de expresarlo es esta: Supongamos que el problema de decisión es decidir si $\phi(n)$ para $n\in\mathbb{N}$ . Entonces la hipótesis de que todas las instancias son decidibles por ZFC es: $\forall n\, \left[(\mathrm{ZFC}\vdash\phi(n))\vee(\mathrm{ZFC}\vdash\neg\phi(n))\right]$ .

Para saber que el procedimiento anterior realmente decide el problema, hay que saber que $\forall n\,\left[ (\mathrm{ZFC}\vdash\phi(n))\rightarrow \phi(n)\right]$ y $\forall n\, \left[(\mathrm{ZFC}\vdash\neg\phi(n))\rightarrow \neg\phi(n)\right]$ . Una forma de garantizar esto sería si se creyera que para todas las frases $\psi$ , $(\mathrm{ZFC}\vdash\psi)\rightarrow\psi$ (esto es lo que informalmente quise decir con "ZFC es verdadera"). Nótese que esto es más fuerte que "ZFC es consistente", ya que "ZFC es consistente" se obtiene tomando $\psi$ para ser falsa.