¿Cuántos dígitos de la constante$\Omega$ de Chaitin sabríamos si tuviéramos un$\Sigma_1$ - Oracle?

Question

De acuerdo a Wikipedia (y parece intuitiva a partir de la definición de sí mismo), $\Omega$ es de Turing equivalente a detener problema y, por tanto, al nivel de $\Delta_2^0$ de la aritmética de la jerarquía. Ello significa que se pueden calcular todos los dígitos de $\Omega$ si tuviéramos un $\Sigma_1$-Oracle? (o debería ser un $\Sigma_2$-Oracle para incluir a todos los $\Pi_2$ declaraciones, las cuales son equivalentes a $\Sigma_3$ declaraciones, todavía estoy confundido acerca de este detalle).

Si es así, la afirmación de que el número de conocidos dígitos de $\Omega$ da cierta medida de la fuerza de una teoría no tiene sentido. El número de conocidos dígitos de $\Omega$ sólo podía discriminar entre las fortalezas de las diferentes teorías de la clase T=PA+$\Psi$ donde $\Psi$ es un subconjunto de todos los posibles $\Sigma_2$ declaraciones, pero no puede medir cualquier cosa, si la teoría de incluir los axiomas de la complejidad de la $\Sigma_3^0$ y por encima. Que es muy baja en la teoría de la fuerza (por no hablar de si se incluyen los niveles superiores, de entrar en el análisis de la jerarquía). Es esto correcto?

Answer 1

Sí, $\Omega$ es computable de $0'$. El conjunto $0'$$\Sigma^0_1$, así que si usted tiene acceso a cualquier otro $\Sigma^0_1$ conjunto completo también puede calcular todos los dígitos de $\Omega$. Así el conjunto de los números codificados por los dígitos de $\Omega$$\Delta^0_2$. Sin embargo, este juego no es $\Sigma^0_1$ - que la distinción puede ser un punto de confusión.

Cada verdadero, eficaz de la teoría de la aritmética sólo puede demostrar que los valores de un cierto número finito de dígitos de $\Omega$, y el número de dígitos para que una teoría pueda demostrar los valores es una medida de la fuerza de la teoría. Pero a pesar de $\Omega$$\Delta^0_2$, una teoría puede obtener información acerca de los dígitos de $\Omega$ a partir de los axiomas arbitrariamente de alta complejidad.

Para la comparación, de una manera más común para medir la fuerza de una teoría de la $T$ es determinar una colección de efectivo de las teorías de $T'$ tal que $T$ demuestra $\text{Con}(T')$. Ahora cada instrucción $\text{Con}(T')$ $\Sigma^0_1$ pregunta, por lo que el oráculo $0'$ es capaz de responder a todas estas preguntas correctamente. Pero una teoría dada $T$ no va a ser capaz de probar la consistencia de arbitrario consistente teorías, por Gödel los teoremas de incompletitud. Y puede ser que la adición de un axioma de alta complejidad a $T$ puede afectar a la $\Sigma^0_1$ consecuencias de $T$.

Esta medida de fuerza no es la intención de distinguir las teorías que tienen el mismo $\Sigma^0_1$ consecuencias. El conjunto de $\Sigma^0_1$ consecuencias resulta ser una interesante medida de fuerza debido a su relación con la consistencia de las declaraciones. Por supuesto, sólo le da un punto de vista sobre la fuerza de una teoría.

Hay tres formas comunes para medir la fuerza de una teoría:

• El conjunto de sus consecuencias lógicas
• La colección de efectivo de las teorías que se puede ser coherente
• La colección de computable bien ordenamientos que puede llegar a ser bien ordenado

Estos tres dan información diferente acerca de una teoría, aunque en la práctica existe una estrecha conexión entre la segunda y la tercera. Uno de los problemas con la primera es que es muy sensible al lenguaje de la teoría. Por ejemplo, el lenguaje de la aritmética de Peano no incluye ningún trivial fórmulas en el análisis de la jerarquía, por lo que PA no puede probar ellos. Pero hay algunos eficaz de teorías en el lenguaje de segundo orden de la aritmética que son más débiles que los PA en el segundo y tercer sentidos, incluso si son capaces de demostrar que las declaraciones arbitrariamente alto en el análisis de la jerarquía.