12 votos

Hay un "computable" contables modelo de ZFC?

Pregunta

Suponiendo que ZFC es consistente (un modelo), ¿existe un conjunto de $S$ y una relación binaria $\in_S$ $S$ que cumplir con los siguientes?

  1. $S \subseteq \{0,1\}^*$ (esta es la estrella de Kleene, y, en particular, $S$ es contable);

  2. $S$ es decidable, es decir, existe una máquina de Turing $C$ de manera tal que en la entrada de cualquier cadena binaria $x$, $C$ se detiene y acepta al $x \in S$ y se detiene y se rechaza en caso contrario;

  3. $\in_S$ es decidable, es decir, existe una máquina de Turing $D$ de manera tal que en la entrada de cualquier par ordenado $(x,y) \in S \times S$, $D$ se detiene y acepta al $x \in_S y$, y se detiene y se rechaza en caso contrario;

  4. $(S, \in_S)$ es un modelo de los axiomas de ZFC.

Detalles

Esencialmente, estoy interesada en saber si cada coherente de la teoría tiene una "computable" modelo en el anterior sentido. Por supuesto, es fácil ver que las teorías como DLOWE (denso lineal órdenes sin extremos) e incluso de primer orden de la Aritmética de Peano tienen tales modelos, simplemente deje $S$ el conjunto de los números racionales y los números enteros, respectivamente, codificado en binario en algunos canónica manera, y es un resultado estándar que $<, +, \cdots$, etc. son computables las operaciones. Así que pensé que ZFC podría ser un buen ejemplo más difícil de tratar -, pero no he sido capaz de argumentar la existencia de un modelo de la forma requerida.

Me hice esta pregunta a un amigo y se opusieron que tal vez cada contables, con cualquier operación binaria, que puede ser considerado computable en este sentido, después de todo, usted está autorizado a asignar los elementos de los contables conjunto de cadenas binarias en cualquier forma que te gusta. Sin embargo, esto no es cierto. Deje $S$ ser los vértices de un grafo dirigido que consiste de una sola dirigido ciclo para cada entero $n$, donde el ciclo tiene una longitud de busy beaver de $n$. Deje $\in_S$ ser la relación binaria correspondiente a este grafo dirigido. Luego he comprobado que $\in_S$ no es un decidable relación, no importa cómo asignar los vértices en $S$ a las cadenas. Así que es concebible que un contable modelo de la teoría de conjuntos es igualmente no computables.

11voto

ManuelSchneid3r Puntos 116

Gran pregunta! Esto ya fue considerado en Mathoverflow; la respuesta es no. Ver http://mathoverflow.net/questions/12426/is-there-a-computable-model-of-zfc.


He hecho esta wiki de la comunidad, así que no puedo reputación de bonificación de los otros' trabajo duro; yo iba a votar a cerca de como un duplicado, pero el sistema no me deja, ya que el duplicado de la cuestión no está en las matemáticas.stackexchange.


Tenga en cuenta que, a pesar de esto, podemos preguntar: ¿qué tan complicado debe contables modelo de ZFC? Desde que ZFC es una computable de primer orden de teoría, cualquier PA grado calcula un modelo de este tipo, y hay muchos de esos grados; de hecho, hay PA títulos, los cuales son bajos, es decir, cuyo salto es Turing reducible a Detener problema (= tan pequeño como sea posible). Por el contrario, los argumentos en el mathoverflow pregunta citados anteriormente muestran que cualquier contables modelo de ZFC es de PA grado, por lo que esta es una caracterización exacta.

Tenga en cuenta que muy poco específica acerca de ZFC se utiliza aquí! En concreto, y a resolver tu pregunta general: Henkin construcción muestra que cualquier PA grado calcula un modelo de cualquier computable de primer orden de la teoría, y que por el contrario cualquier grado que no es PA falla para calcular un modelo de algunos computable de primer orden de la teoría; aunque, por supuesto, de teorías específicas, el conjunto de grados de modelos de que la teoría puede ser más complicado. De este conjunto, por el camino, se ha estudiado un poco de lo que se conoce como el espectro de la teoría. Ver http://www.math.wisc.edu/~andrews/espectros.pdf.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X