Godel en jerarquías recursivas de teoría de la computación

Question

Al final de su excelente artículo, "The Emergence of Descriptive Set Theory" (http://math.bu.edu/people/aki/2.pdf), Kanamori escribe:

"Otro retorno matemático eterno: Hacia el final de su vida, Godel consideró la pregunta de si existe una jerarquía lineal para los conjuntos recursivos como uno de los grandes problemas abiertos de la lógica matemática. Intuitivamente, dadas dos procedimientos de decisión, a menudo se puede ver que uno es más simple que el otro. Ahora, un conjunto de enteros es recursivo si y solo si tanto él como su complemento son recursivamente enumerables. El resultado crucial de la teoría clásica de conjuntos descriptivos es que un conjunto es Borel si y solo si tanto él como su complemento son analíticos. Pero antes de eso, ya había una jerarquía para los conjuntos de Borel. En una inversión final, al mirar hacia atrás en los conjuntos recursivos, no se conoce ninguna jerarquía."

Tengo dos preguntas sobre esto.

1) ¿Alguien puede proporcionar una cita para esto? No estaba al tanto de que Godel se enfocara en esta pregunta en algún momento, y me gustaría leer cualquier cosa que haya dicho al respecto.

2) ¿Qué trabajo se ha hecho en esta pregunta? En particular, ¿hay alguna razón para creer que existe tal jerarquía, más allá de la (en mi opinión, poco convincente) analogía con los conjuntos Borel que Kanamori presenta?

Algunas observaciones sobre la segunda pregunta: hay jerarquías lineales conocidas y naturales para subconjuntos propios de los conjuntos recursivos; por ejemplo, la jerarquía de Grzegorczyk (http://en.wikipedia.org/wiki/Grzegorczyk_hierarchy) da una jerarquía de los conjuntos primitivos recursivos con tipo de orden $\omega$. Sin embargo, no está claro para mí que alguna de estas jerarquías tenga la posibilidad de ser extendida a todos los conjuntos recursivos de alguna manera agradable. En particular, una barrera que se enfrentaría sería que las jerarquías que ocurren naturalmente enumeran aquellas funciones computables que son demostrablemente totales en alguna teoría recursiva correspondiente de aritmética (o teoría de conjuntos), y ninguna de esas teorías puede probar la totalidad de todas las funciones recursivas totales. ¿Pero tal vez estoy equivocado en esto?

ADICIONADO: Quiero aclarar que la conexión entre jerarquías y totalidad demostrable - que aquí es un obstáculo - usualmente es increíblemente útil (y si tengo bien mi historia, muchas de estas jerarquías fueron desarrolladas precisamente para comprender qué funciones eran demostrablemente totales en ciertos sistemas).

Answer 1

No pretendo dar esto como una respuesta completa, pero en cuanto a la pregunta 2, ha habido una gran cantidad de resultados negativos en relación con este problema.

De hecho, la mayoría de ellos toman la forma de mostrar que cualquier jerarquía subrecursiva ''razonablemente constructiva'' (léase ''efectivamente generada'') de funciones computables indexadas por caminos a través de $\mathcal O$ de Kleene sufren problemas de definición. En el núcleo de cada argumento, estos resultados negativos explotan alguna variación del principio de acotamiento $\Sigma^1_1$ de Spector. Para ilustrar un ejemplo, Sacks (ubicado en su Higher Recursion Theory) exploró una versión efectiva de este principio de la siguiente manera:

Existe una función computable $\varphi$ tal que, para cada $x \in 2^{\omega}$, tenemos que

$x \subseteq \mathcal O \iff \varphi(x) \in \mathcal O$ y $x \subseteq \mathcal O_{\varphi(x)}$

donde $\mathcal O_{\varphi(x)} := \left\{ y \in \mathcal O : rnk(y) \leq rnk(\varphi(x))\right\}$, y $rnk(x)$ denota el rango de $x$, y se mide como un ordinal.

Aplicando esto a nuestro problema (o alguna variación de este), cualquier clasificación inductiva de las funciones computables en algún camino $\Pi^1_1$ $\mathcal P \subseteq \mathcal O$ terminará "colapsando" antes de que todas las funciones computables hayan sido agotadas en algún nivel contable, que típicamente se mide como la altura ordinal de $\mathcal P$.

Cabe mencionar que Sacks dio una conferencia donde recuerda sus conversaciones con Godel hacia el final de su vida. En particular, mencionó una conversación donde Godel describió una lista de problemas sobresalientes en lógica matemática que pensaba revitalizarían el tema en su totalidad. En la lista, sugirió el problema de probar la existencia de una jerarquía exhaustiva de funciones computables, y creía que tal jerarquía debería existir.

Luego, Sacks concluye que no hay mucha evidencia que respalde la creencia de Godel, a la luz de los resultados parciales negativos mencionados anteriormente. Sin embargo, Sacks continuó diciendo que nadie ha sido capaz de dar una verdadera prueba de que no existe tal jerarquía, por lo que uno se queda con la sensación de que una solución final a este problema está fuera del alcance con los métodos actuales.

Answer 2

Para (1), consulte por ejemplo la página-18:

https://www3.nd.edu/~cfranks/frankstennenbaum.pdf

Específicamente estaba hablando del siguiente párrafo. Creo que los párrafos posteriores son muy interesantes (posiblemente aún más que el citado), pero parece que solo están relacionados indirectamente con la pregunta.

• Por lo tanto, la importancia de la creencia de Gödel en una realidad matemática "bien determinada" no radica en el simple hecho de que él sostuviera esta opinión ni, en última instancia, en las razones que dio para apoyarla. Lo crucial es que enfatizó su platonismo ontológico incluso ante la incompletitud sistemática, y que a su vez fue instigado por su platonismo moral a idear nuevas formas de lograr una vista sinóptica del cuerpo colectivo de hechos matemáticos en lugar de desesperar de cualquier posibilidad de hacerlo. En la conversación del 21 de agosto de 1974, se pregunta si todas las preguntas matemáticas se pueden resolver en las lógicas de los ordinales traspasados. Más tarde ese año, en la conversación del 1 de noviembre, expresa su creencia de que se puede obtener un tipo de resultado de completitud para las lógicas ordinales. Sus propios descubrimientos de medio siglo atrás podrían fácilmente disuadir a alguien de perseguir este tipo de problema aún más, sin embargo, en manos de Gödel parecen solo haber llevado a una visión más rica del tipo de preguntas que se pueden hacer.

Aquí está específicamente parte de una de las conversaciones a las que se alude en el párrafo anterior. No he cambiado la continuidad/el orden de las oraciones. Solo he añadido viñetas (correspondientes a saltos de línea en las notas) para facilitar la lectura:

• Quiero tomar los ordinales recursivos dados por alguna definición canónica (cf. el trabajo de Feferman; Schutte continuó—más allá de lo previamente conocido; la definición no sería constructiva (estaría asignando a cada ordinal recursivo una bien definida ordenación de los enteros como se ha hecho para los pequeños)
• La pregunta entonces es si puedes resolver cada pregunta matemática en las lógicas de estos ordinales
• Esto es un contraparte de la pregunta de la incompletitud.

Parece un poco diferente de la pregunta "específica" planteada aunque (pero podría ser de cierto interés). Lo vi recientemente. Disculpa si la mayoría de la gente ya está muy al tanto de esto.

Editar: Incluí la parte relevante a la que me refería en la publicación.