Teoremas de la teoría de conjuntos que utilizan herramientas de la teoría de la computabilidad, y viceversa.

Question

Hace poco me enteré de que la demostración del teorema clásico " $\mathsf{AD}$ $\implies$ $\aleph_1$ es medible" utiliza herramientas de la teoría de la computabilidad (o al menos una de sus pruebas lo hace). Me interesan más ejemplos de esto. Más concretamente:

1. ¿Cuáles son otros resultados conocidos de la teoría de conjuntos para cuya demostración se utilizan herramientas no triviales de la teoría de la computabilidad?

2. ¿Cuáles son algunos resultados conocidos de la teoría de la computabilidad para cuya demostración se utilizan herramientas no triviales de la teoría de conjuntos?

Me interesan más los resultados clásicos, pero los ejemplos modernos también son bienvenidos. Si es posible, también me gustaría una referencia (libro de texto / papel) para cada ejemplo.

Answer 1

He aquí varios ejemplos.

• Existe una afinidad natural entre el forzamiento y muchas construcciones en los grados de Turing. En concreto, muchas construcciones de grados mediante el cumplimiento sucesivo de requisitos pueden verse como el cumplimiento de conjuntos densos en una noción de forzamiento adecuada, con el resultado de que la construcción de computabilidad equivale a un argumento de genericidad. Por ejemplo, para demostrar que hay grados incomparables, uno debe construir los oráculos por segmento inicial (por tanto, forzamiento de Cohen), y extenderlos genéricamente de tal manera que ninguno sea computable con respecto al otro como oráculo. Hay docenas de ejemplos como este, y recomiendo la manera de forzar para entender tales construcciones en computabilidad. Esto es similar a la forma de forzar la genericidad para ver el límite de Fraïssé de una clase de estructuras finitas.

• Otro ejemplo de este tipo: deben existir anticanales fuertemente independientes en los grados (ningún elemento es computable a partir de la suma de todos los demás), ya que si se suman infinitos reales de Cohen, son así, y la afirmación de que existe es $\Sigma^1_1$ y, por tanto, absoluto. De tal anticadena, se obtiene la universalidad como una consecuencia fácil - cada orden contable se incrusta en los grados.

• La analogía anterior es muy fuerte en ciertos casos, y fue históricamente la forma en que se probaron los resultados. Por ejemplo, la construcción de Sacks de un grado mínimo en los grados de Turing se traduce directamente en la prueba de la característica de minimalidad del forzamiento de Sacks.

• El concepto de grados de Turing es directamente análogo a muchas otras nociones de grado de la teoría de conjuntos. Por ejemplo, muchos argumentos se traducen a los grados de constructibilidad, donde $x\sim y$ si $L[x]=L[y]$ . Por ejemplo, el papel del forzamiento iterado de Sacks se ha utilizado (especialmente en trabajos de Marcia Groszek y otros) para producir modelos de teoría de conjuntos que realizan una estructura especificada para los grados de constructibilidad. Este método también aparece en mi trabajo con Groszek sobre la Universo implícitamente construible . Y lo mismo ocurre con los grados aritméticos e hiperaritméticos.

• La noción de computabilidad se generaliza a la hipercomputación y a la E-recursión, de una forma que está profundamente conectada con la teoría descriptiva de conjuntos.

• La noción de computabilidad también se generaliza mediante Máquinas de Turing de tiempo infinito que también está profundamente relacionada con la teoría descriptiva de conjuntos. Esta noción, a su vez, se generaliza mediante la computación ordinal, que proporciona una presentación alternativa de la jerarquía L en términos de teoría de la computabilidad.

• En mi trabajo, El forzamiento como proceso computacional mis coautores y yo investigamos la teoría computable de modelos de forzamiento, estudiando cómo se puede calcular una extensión de forzamiento a partir de un oráculo para un modelo dado.

• Hay un divertido argumento mío para la no linealidad de los grados de Turing usando la teoría de conjuntos: si los grados son lineales, entonces como cada segmento inicial es contable, la cofinalidad tendría que ser $\omega_1$ pero como hay muchos grados continuos, esto implica CH. Pero CH falla en una extensión forzada. La afirmación de que hay grados incomparables es $\Sigma^1_1$ y, por tanto, absoluto. Así que debe haber grados incomparables en el modelo de tierra.

• Otro argumento, que me acaba de recordar Jason Chen (pero creo que aparece en otra parte aquí en MO): la relación de grado de Turing $x\leq_T y$ es definible aritméticamente y, por tanto, de Borel, y como tiene secciones contables, debe tener medida 0. Por tanto, la relación inversa también tiene medida 0. Así pues, existe un conjunto de pares de medida uno $(x,y)$ no relacionados por computabilidad relativa. Así que los grados no son lineales.

Answer 2

La teoría de conjuntos descriptiva eficaz es un área en la que se da una fructífera interacción entre la teoría de conjuntos y la teoría de la recursividad. Aquí hay un hilo en MO sobre qué leer si está interesado: Good source for Teoría descriptiva eficaz de conjuntos

EDST revela una serie de profundas y bellas analogías entre computabilidad, Borelness e hiperaritmeticidad. La sección de Introducción antes del Capítulo 1 de la Teoría Descriptiva de Conjuntos de Moschovakis contiene algunos párrafos sobre estas analogías. Por ejemplo, la prueba de que la propiedad de preordenación implica la propiedad de reducción recuerda mucho a la técnica común de utilizar máquinas de Turing para enumerar conjuntos alternativamente mientras se mira hacia atrás para comprobar los elementos enumerados en cada paso.

El campo más reciente de la teoría de la aleatoriedad superior es otro lugar en el que los dos campos tienen un profundo compromiso. Aquí, uno busca análogos superiores de la teoría de la aleatoriedad algorítmica, donde "algorítmica" puede generalizarse para significar definible proyectivamente. Por supuesto, esto choca rápidamente con la independencia en la $\Sigma^1_2$ y un desarrollo satisfactorio de la teoría se basa a menudo en la teoría de la determinabilidad y los modelos internos. Que yo sepa, los únicos libros de texto que contienen un tratamiento sistemático de este tema son Computability and Randomness, de Andre Nies, y Recursion Theory, de Chong Chi Tat y Yu Liang (aunque hay bastantes buenos recursos sobre teoría de la aleatoriedad "inferior").

Answer 3

Mis favoritos son los resultados en teoría de la computabilidad que se basan en el teorema del cono de Martin (si A es un conjunto invariante de grado suficientemente definible (ciertamente si es Borel pero creo que más) entonces o A o su complemento contienen un cono.

Esto se puede utilizar para todo tipo de resultados, como la existencia de un cono de cubiertas mínimas (tanto bajo Turing y reducibilidad aritmética ... el primero tiene una prueba constructiva, pero no soy consciente de uno para el segundo). Véase el volumen 2 de Odifreddi sobre los grados aritméticos y el volumen 1 sobre la afirmación del grado de Turing.

Otros ejemplos aquí

Véase también debate donde Noah respondió a una pregunta mía sobre 2-lubs dándole en la cabeza con la teoría de conjuntos forzados.

Answer 4

Tengo otro ejemplo interesante en el que se aplica el método de la teoría de conjuntos para demostrar un resultado de la teoría de la recursividad.

Dado un conjunto infinito $E\subseteq \omega$ una pregunta es cuál es la cardinalidad del conjunto $A_E=\{x\in 2^{\omega}\mid \exists c\forall n\in E K^x(n)\geq K(n)-c\}$ donde $K$ es la complejidad de Kolmogorov y $K^x$ es la complejidad de Kolmogorov relativa a $x$ ?

Un resultado famoso en la teoría algorítmica de la aleatoriedad es que $A_{\omega}$ es contable. De hecho, para cualquier conjunto $E$ que tiene un subconjunto recursivo, $A_E$ debe ser contable. Entonces una pregunta natural es ¿puede $A_E$ ser incontable?

Wolfgang y yo (Wolfgang Merkle y Liang Yu, Being low along a sequence and elsewhere, The Journal of Symbolic Logic, Volume 84, Issue 2 June 2019 , pp. 497-516.) construimos algunas $E$ para que $A_E$ incontable. La prueba es por Mathias forzando juntos Shoenfield absolutos.