¿Existen enunciados indecidibles pero no demostrablemente indecidibles

Question

Se trata de una variante de ¿Existe algún enunciado cuya indecidibilidad sea indecidible? y ¿Se puede demostrar que la ZFC tiene afirmaciones que no se pueden demostrar como independientes, pero que lo son? (pero no se pregunta ni se responde en ninguno de esos hilos).

Llamar a una fórmula $\phi$ es indecidible si $ZFC$ demuestra que ( $ZFC$ es coherente) $\Rightarrow$ ( $\phi$ es independiente de ZFC). Ahora, (suponiendo que $ZFC$ es consistente) ¿hay afirmaciones indecidibles pero no demostrables?

Esta es otra forma de decirlo. Llamar a una declaración $\phi$ débilmente decidible si ZFC puede demostrar que $\phi$ es verdadera o demostrar que $\phi$ es falso, o al menos demostrar la implicación ( $ZFC$ es coherente) $\Rightarrow$ ( $\phi$ es independiente de ZFC).

Así, la hipótesis del continuo es débilmente decidible en ZFC, y el axioma de elección es débilmente decidible en ZF. Por otra parte, no se sabe hoy en día si la existencia de un cardinal inaccesible es débilmente decidible.

La pregunta original se puede replantear así: ¿hay enunciados que no son ni siquiera débilmente decidibles?

Answer 1

En primer lugar, supongamos que la ZFC es realmente consistente. Si todas las afirmaciones fueran probadamente verdaderas o probadamente falsas o probadamente independientes, entonces habría un procedimiento de decisión que clasificara todas las afirmaciones en estos tres grupos -sólo hay que enumerar todas las pruebas válidas hasta encontrar una cuya conclusión sea una de las tres formas.

Podríamos usar esto para decidir el problema de detención. Para cualquier $n$ Considere la afirmación "Máquina de Turing $T_n$ se detiene". Hay entonces tres casos.

1. $ ZFC \vdash Con(ZFC) \Rightarrow T_n\text{ halts}$

   En este caso, debe ser cierto que $T_n$ se detiene.

2. $ ZFC \vdash Con(ZFC) \Rightarrow \neg(T_n\text{ halts})$

   En este caso debe ser falso que $T_n$ se detiene.

3. $ ZFC \vdash Con(ZFC) \Rightarrow{}$ " $T_n$ La "parada" es independiente de ZFC.

   En este caso debe haber un modelo de ZFC en el que $T_n$ no se detiene y por lo tanto tiene un cálculo infinitamente largo. Sin embargo, en cada modelo de ZFC, el modelo $\omega$ debe contener una imagen suryectiva de la meta- $\omega$ . (Y de forma similar para cualquier objeto que utilicemos para representar las cintas de Turing). Por lo tanto, el cómputo infinito en el modelo corresponde a un cómputo infinito en el metanivel . Por lo tanto, $T_n$ realmente no se detiene.

En conclusión, si ZFC es consistente, entonces su hipótesis conduce a una solución del problema de detención, que sabemos que es imposible. Por lo tanto, por contradicción, su hipótesis debe ser falsa si ZFC es consistente. Por otro lado, si ZFC es no consistente, entonces su hipótesis sigue siendo falsa, porque entonces no hay afirmaciones indemostrables en absoluto.