¿Existe un ordinal computable que codifique la fuerza de prueba de ZF? ¿Es conocible?

Question

En los comentarios sobre Quora (véase, por ejemplo, aquí, aquí, aquí), Ron Maimón en repetidas ocasiones ha expresado la opinión de que el programa de Hilbert era no asesinado por Gödel de los resultados de la forma en que normalmente se reivindica. Más precisamente, argumenta que la consistencia de los axiomas suficiente para todos significativo de las matemáticas debe ser comprobable de "intuitivamente evidente" declaraciones acerca de las diversas computable ordinales estar bien definido. Aquí, por supuesto, él apunta a Gentzen 1936 la consistencia de la prueba, con lo que se demuestra Con(PA) de la primitiva recursiva aritmética, además de la inducción hasta el ordinal ε₀; así como los resultados más recientes en el campo de ordinal de análisis, que muestran que la consistencia de varios más débil conjunto de teorías de ZF (por ejemplo, Aczel constructiva de la ZF y Kripke-Platek la teoría de conjuntos) también puede ser reducido a la bien definedness de diversos computable ordinales. Maimón luego va a decir que Con(ZF) debe igualmente ser reducible a la bien definedness de algunos "combinatoria-especificado," computable ordinal, aunque los detalles no han sido resueltos todavía. (Y, de hecho, la página de Wikipedia sobre ordinal análisis dice que no se ha hecho "a partir de 2008.") Esto suena increíble, sobre todo porque yo nunca había escuchado nada acerca de este problema antes! Así que, aquí están mis preguntas:

• Hay un teorema general que muestra que Con(ZF) debe ser reducible a la bien definedness de algunos computable ordinal, es decir, algo por debajo de la Iglesia-Kleene ordinal (incluso si no sabemos cómo especificar un ordinal "explícitamente")?

• Es encontrar una "descripción explícita" de una computable ordinal cuyo bien definedness implica Con(ZF) reconocida como un problema abierto en la teoría de conjuntos? Hacer el trabajo de la gente sobre este problema? O hay alguna razón por la que generalmente se cree que es imposible, o posible, pero sin interés? O simplemente tiene que bajar a la falta de claridad sobre lo que cuenta como un "descripción explícita"?

Addendum: Hay una conexión de aquí a un anterior MO cuestión de la mina, sobre la existencia de Π₁-declaraciones independiente de ZF con un montón de afirmar la consistencia de los axiomas. En particular, el uso de una observación de Turing de 1938 tesis doctoral, ahora veo que es posible definir una "computable ordinal", cuyo bien definedness es equivalente a Con(ZF), pero sólo a causa de una "hoteles de codificación truco". Es decir, se puede definir el ordinal ω a través de una máquina de Turing que las listas de los enteros positivos, uno por uno, pero que al mismo tiempo busca una prueba de 0=1 en ZF, y que se detiene y salidas de tonterías de que si alguna vez encuentra uno. Lo que supongo que estoy pidiendo, entonces, es una computable ordinal tal que α Con(ZF) se reduce a la afirmación de que hay alguna máquina de Turing que define correctamente α.

Answer 1

Rom de Maimón se describe el programa de la prueba de la teoría ordinal de análisis.

En primer lugar, como se observa en el anexo, no es interesante conocer algunas de codificación de un ordinal cuyo fundamento implica Con(ZFC), sino más bien un ordinal tal que el fundamento de toda representación implica Con(ZFC). Uno tiene la esperanza de que es suficiente con considerar natural de las representaciones de los ordinales, que ha sido así en la práctica, pero no está probado (y probablemente improbable, dada la dificultad de hacer exacto lo que cuenta como una representación natural).

Es posible demostrar que el ordinal menor que ZFC no puede probar bien fundado es computable por darse cuenta de que los computable notaciones para los números ordinales que probablemente se encuentre fundada en ZFC son un $\Sigma_1$ subconjunto de los computable notaciones de números ordinales, así que sin duda $\Sigma^1_1$, y por un resultado de Spector, cualquier $\Sigma_1^1$ subconjunto de los computable notaciones para ordinales está acotada.

Como se señaló en la respuesta a Timoteo Chow enlaces de arriba, esto suele ser cierto que esta noción de la prueba de la teoría ordinal termina siendo el mismo como ordinales con otras buenas propiedades (como lo implica Con(ZFC)), pero no hay ninguna prueba de que eso siempre va a pasar (y no puede ser, ya que no son defectuosos ejemplos que muestran que no siempre es cierto), ni una prueba de que cubre ZFC.

Sin embargo, se considera en general que para los "naturales" de las teorías, incluyendo ZFC, las diferentes nociones de la prueba de la teoría ordinal de la fila.

Encontrar una descripción explícita de los ordinales para ZFC es un problema en la prueba de la teoría, pero el progreso ha sido muy lento. Los mejores resultados conocidos son por Rathjen y Arai (por separado) en el nivel de $\Pi^1_2$-comprensión (una subteoría de la aritmética de segundo orden, por lo tanto, mucho más débil que ZFC), y después de casi 20 años, aquellos que permanecen inéditos. Los resultados en el área puso muy difícil y técnica, y no parecen dar una idea de las teorías de la forma en que el más pequeño de los números ordinales tenía, así que no es tan activa como la que una vez fue. Wolfram Pohlers y sus estudiantes parece que siguen trabajando en la zona, y algunas otras personas parecen estar pensando en otros enfoques, en lugar de atacar directamente a él (Tim Carlson y Andreas Weiermann y sus estudiantes vienen a la mente).

Answer 2

Para cada c.e. la teoría T (ampliación de una base débil de la teoría), ya sabemos que un polinomio de tiempo computable lineal de pedidos $≺$ que captura la $Π^1_1$ de fuerza de T:
Probablemente se encuentre en una base débil de la teoría, de una $Π^1_1$ enunciado es demostrable en T iff para algunos términos, es comprobable en una base débil de la teoría plus "$≺$ es fundado por debajo de s".
Así, por $Π^1_1$ sonido T, el tipo de orden de $≺$ es el supremum de tipos de orden de modo demostrable en T recursiva bien ordenamientos, y $≺$ es un buen orden si T es $Π^1_1$ sonido.

Aquí es un ejemplo de $≺$:
$(p_1,q_1,n_1) ≺ (p_2,q_2,n_2)$ si $(p_1,q_1)<(p_2,q_2)$ (lexicográficamente)
$(p,q,n_1) ≺ (p,q,n_2)$ fib
- $q$ es un T-prueba de que el acotado de tiempo de máquina de Turing $p$ calcula un buen orden, y $p$ acepta $(n_1,n_2)$ (cualquier opción razonable para 'acotado de tiempo' que mantiene a $≺$ polinomio de momento funciona aquí), o
- $q$ no es un T-prueba de la anterior, y $n_1<n_2$.

El problema es que el anterior $≺$ es informativo acerca de T. Un objetivo clave de los ordinales análisis es encontrar un canónica $≺$ que hace el poder de la T simple y explícito, y por lo tanto nos da un nivel cualitativamente mejor comprensión de T. Existencia de una canónico $≺$, combinado con la existencia de la canónica $≺$ más débiles de las teorías sugiere que un canónica $≺$ también existe para ZFC, pero es difícil estar seguro hasta que de hecho encontrar y probar un $≺$. Normalmente, un enfoque a la búsqueda de $≺$ puede ser extendido hasta que se vuelve demasiado complejo y, a continuación, una nueva idea de permisos de $≺$ a ser más simples de nuevo.

Una precaución sobre ordinal representaciones:
* Cada suficientemente grande recursiva ordinal tiene diferentes recursiva representaciones que no son aritméticamente isomorfo.
* Yo creo que para cada recursiva ordinal α y un c.e. la teoría T (ampliación de una base de la teoría), no es una representación recursiva $≺$ de α tal que T + "$≺$ está bien fundada" es $Σ^1_1$ conservador sobre T. Esto se deduce de la existencia de un recurrente pseudowellordering $≺_p$ tal que T + "$≺_p$ está bien fundada" es $Σ^1_1$ conservador sobre T.