¿Existe un modelo computable de ZFC?

Question

Antecedentes

Asumiendo que ZFC es consistente, entonces por Löwenheim-Skolem descendente, hay un modelo contable (M, $\in$ ) de ZFC. Como el universo M es contable, podemos pensar que es el conjunto de los números naturales, por lo que $\in$ será alguna relación binaria sobre los números naturales.

¿Puede esa relación ser computable?

Resultados parciales

Se puede demostrar que la clase de relaciones binarias $R$ en los números naturales tal que $(\mathbb{N},R) \models ZFC$ forma un $\Pi_0^1$ y será no vacía siempre que ZFC sea consistente. Esto ya nos da algunos resultados interesantes. Por ejemplo, por el teorema de la base baja, existe un $R$ tal que $(\mathbb{N},R) \models ZFC$ . Pero no he podido determinar si tal función puede hacerse computable; lo mejor que puedo hacer es mostrar que si tal función es computable, entonces no hay ninguna manera efectiva de encontrar, dado un conjunto finito D de números naturales, el elemento n tal que D={m : mRn}.

Answer 1

El fenómeno Tennenbaum es sorprendente, y eso es totalmente correcto, pero permítanme dar una prueba directa utilizando la idea de inseparabilidad computable .

Teorema . No existe un modelo computable de ZFC.

Prueba: Supongamos que M es un modelo computable de ZFC. Es decir, suponemos que el conjunto subyacente de M es ω y la relación de pertenencia E de M es computable.

En primer lugar, podemos superar el problema que mencionas al final de tu pregunta, y podemos acceder computacionalmente a lo que M piensa que es el n th número natural, para cualquier número natural n. Para ver esto, observe primero que hay un número natural particular z, que M cree es el número natural 0, otro número natural N, que M cree que es el conjunto de todos los números naturales, y otro número natural s, que M cree que es la función sucesora de los números naturales. Al descifrar lo que significa evaluar una función en la teoría de conjuntos utilizando pares ordenados, Nosotros podemos ahora calcular sucesivamente la función i(0)=z e i(n+1) = el único número que M cree que es la función sucesora s de i(n). Por lo tanto externamente, ahora tenemos acceso computable a lo que M cree que es la función n th número natural. Permítanme denotar i(n) simplemente por n . (Podemos podríamos reordenar computacionalmente las cosas, si lo deseamos, para que estos fueran, digamos, los números Impares).

Sean A, B cualesquiera computacionalmente inseparable conjuntos. Es decir, A y B son conjuntos computables disjuntos conjuntos enumerables que no tienen separación computable. (Por ejemplo, A es el conjunto de programas TM que se detienen con la salida 0 en la entrada 0, y B es el conjunto de programas que se detienen con la salida 1 en la entrada 0). Dado que A y B son cada uno de ellos computables, hay programas p ₀ y p ₁ que los enumeran (en nuestro universo). Estos programas son finitos, y M está de acuerdo en que p ₀ y p ₁ son programas de TM que enumeran un conjunto de lo que cree que son números naturales. Hay algún número natural particular c que M piensa que es el conjunto de números naturales enumerado por p ₀ antes de ser enumerados por p ₁ . Sea A + \= { n | n E c }, que es el conjunto de números naturales n que M piensa que se enumeran en la versión de M de A antes de que se enumeren en la versión de M de B. Este es un conjunto computable ya que E es computable. Además, cada miembro de A está en A + ya que cualquier número realmente enumerado en A será visto por M como si tuviera lo ha sido. Finalmente, por la misma razón, ningún miembro de B está en A + porque M puede ver que están enumerados en B por un (estándar) cuando no han sido enumerados en A. Así, A + es una separación computable de A y B, una contradicción. QED

Esencialmente, este argumento también establece la versión del teorema de Tennenbaum mencionada por Anónimo, de que no hay ningún estándar computable de la AP. Pero en realidad, Tennenbaum demostró un resultado más fuerte, mostrando que ni más ni veces individualmente es computable en un modelo no estándar de AP. Y esto requiere un argumento algo más sutil.

Editar (4/11/2017). La pregunta acaba de ser rebatida por otra edición, por lo que pensé que tenía sentido actualizar mi respuesta aquí mencionando una generalización del resultado. A saber, en un reciente trabajo conjunto,

• M. T. Godziszewski y J. D. Hamkins, Presentaciones computables de cocientes de modelos de aritmética y teoría de conjuntos , haga clic para ver el pdf en el arxiv.

demostramos que no sólo no hay ningún modelo computable de ZFC, sino que tampoco hay ninguna presentación cociente computable de un modelo de ZFC, y de hecho no hay ninguna presentación cociente c.e. de tal modelo, por una relación de equivalencia de cualquier complejidad. Es decir, no hay ninguna relación c.e. $\hat\in$ y la relación de equivalencia $E$ de cualquier complejidad, que es una congruencia con respecto a $\hat\in$ , tal que el cociente $\langle\mathbb{N},\hat\in\rangle/E$ es un modelo de ZFC.

Answer 2

Esto también puede hacerse utilizando Godel-Roesser en lugar de Tennebaum. Supongamos que M es un modelo de ZFC. Hay un elemento $a$ de que M cree es el conjunto de códigos de Godel para las sentencias verdaderas de los enteros de M. Por supuesto $a$ puede contener códigos de Godel no estándar, pero si dejamos que T sea el conjunto de oraciones estándar con códigos de Godel en $a$ , entonces T será una extensión consistente completa de la Aritmética de Peano. Si M es computable, entonces T sería computable, pero no hay extensiones completas consistentes computables de la Aritmética de Peano.

Por supuesto, la apelación a Godel-Roesser no hace más que ocultar el argumento de Joel sobre los conjuntos e.r. recursivos inseparables.

Answer 3

No, no puede ser computable. Es un teorema de Tennenbaum de los años 50 que no existe un modelo computable, no estándar, de la aritmética de Peano. Si hubiera un modelo computable de ZFC, entonces daría un modelo computable y no estándar de la aritmética de Peano. Específicamente, contendría algún modelo no estándar para PA, especificado por un conjunto de elementos y dos relaciones, y la computabilidad del modelo de ZFC implicaría la computabilidad allí. (Si, por ejemplo, quieres la suma de los elementos a y b en el modelo de PA, busca por fuerza bruta un elemento c del modelo tal que (a,b,c) esté en la relación de suma. Esto puede ser terriblemente lento, pero finalmente terminará).

Edición: Es un buen punto sobre la computabilidad de (a,b,c), y no estoy seguro de cómo calcular eso. Afortunadamente, resulta que no es necesario aquí. En concreto, si definimos (a,b,c) = ((a,b),c) y definimos (u,v) = {{u}, {u,v}}, entonces, aunque no esté claro si se puede producir computablemente (a,b,c) dados a, b y c, dado algo que se sabe a priori que es un triple, se puede intentar comprobar si procede de a,b,c encontrando los elementos adecuados. (En el caso más sencillo de los pares, para comprobar si w = (u,v) dado que es algún par ordenado, sólo tenemos que encontrar x e y tales que ambos estén en w, u esté en x, y u y v estén en y). Ahora sólo tenemos que hacer fuerza bruta mayor: no sólo buscar sobre todas las opciones posibles de c, sino también sobre los elementos auxiliares que establecerían que (a,b,c) está en la relación. Espero que haya una forma más agradable de hacer esto, pero creo que funciona.