Como se ve en la "máquina de Turing de A para que frenar es ZFC fuera", teorema de Gödel incompletness puede que no se pueden decidir una máquinas de turing para que frenar. ¿Mi pregunta es, hay un % de la máquina de turing $T$, tal que la declaración "$T$ detiene" es equivalente al axioma de elección o de su negación en teoría determinada ZF?
Respuestas
¿Demasiados anuncios?
No, esto es imposible.
Mientras que $\operatorname{Con}\sf (ZFC)$ es una media aritmética declaración que por lo tanto puede ser utilizado para construir una máquina de Turing que no se puede probar la mitad en $\sf ZFC$, el axioma de elección no es ni remotamente una declaración acerca de los números enteros. Así que no hay ninguna posibilidad de que esto va a suceder.
Un poco más formalmente, sin embargo, recordar que, si $\varphi$ es de primer orden de la declaración sobre los enteros, a continuación, $V\models``\omega\models\varphi"$ si y sólo si $L\models``\omega\models\varphi"$. Desde el axioma de elección es cierto en $L$, si había máquina de Turing, tendría que detener en $L$ y por lo tanto detener en $V$. Por lo que el axioma de elección sería cierto en $V$, y por lo tanto demostrable de $\sf ZF$.
Cuando la consistencia está involucrado, usted puede ir para no estándar de los modelos en los $\operatorname{Con}\sf (ZFC)$ es falso. Pero con el axioma de elección, esto no va a trabajar, ya que siempre que $M$ es un modelo de $\sf ZF$, $M$ $L^M$ tienen el mismo ordinales, por lo que el mismo $\omega$.
David
Puntos
6
Respuesta corta : no
En primer lugar, usted debe entender que, para cualquier máquina de $M$, la proposición "$M$ detiene" es falso o demostrable. Se trata del hecho de que esta fórmula es como $$\exists n\in\mathbb N \;\varphi(n) $$ con $\varphi$ primitiva, y por lo que siempre puede exhibir la $n$ tal que $\varphi(n)$ es verdadera, si es que existe.
Así que cada vez "$M$ detiene" no es demostrable, se significa que el $M$ no se puede detener (en un modelo estándar de los números enteros, donde, como de costumbre, todos los números enteros son finitos, y puede ser demostrado). **
Ahora, "$M$ no detener" puede no ser comprobable (de Gödel del teorema de la incompletitud). Si usted está de acuerdo con el punto anterior, implica siempre que $M$ no detener : la no provability de esta fórmula implica siempre que esta fórmula sea verdadera (si usted no tiene una prueba de su negación).
Así que, por supuesto, no puede ser equivalente a $AC$, que no es ni verdadero o falso en $ZF$, y no implica o no impide que un modelo estándar de los números enteros.
Otra manera de entender que no es posible es tener en cuenta que la fórmula de CA es mucho más complejo que una fórmula para la parada de una máquina ($\Pi_2^1$ vs $\Pi_1^0$ creo). No tendría sentido para CA a ser equivalente a una fórmula más simple.
** Tenga en cuenta que el incompletness teorema implica también que no comprobable fórmula puede ser verdadera en un modelo y falso en otro. Sin embargo, si $n$ existe y es finito, siempre se puede hacer una prueba, tales como : "$n$ es la solución y aquí está el cálculo de $\phi(n)$ que lo demuestre", y que será una válida finito prueba. Esto significa que los modelos donde la fórmula es verdadera ($M$ detiene) y no es demostrable requieren algunos infinito de números enteros. Sin embargo modelos no estándar de $\mathbb N$ son bastante difíciles en $ZF$ y no he encontrado una forma sencilla de entender como usted puede en la aritmética de Peano.
