Cualquier oráculo de parada no estándar más fuerte que $\mathbb N$ ?

Question

Sea $M$ sea algún modelo de PA. Sea $H_M$ sea el conjunto de códigos de las máquinas de Turing estándar $X$ tal que $M \models X \text{ halts}$ . Por ejemplo, $H_\mathbb N$ corresponde al oráculo de parada regular (donde $\mathbb N$ es el modelo estándar).

Mi pregunta es, ¿hay algún modelo $M$ tal que $H_M$ es estrictamente más fuerte que $H_\mathbb N$ como Grado de Turing ?

Answer 1

Sí, de hecho, $H_M$ puede ser arbitrariamente complicado. Es un ejercicio divertido encontrar infinitas independiente sentencias existenciales: es decir, combinando sentencias y números de Godel como de costumbre se encuentra una secuencia computable $(\theta_i)_{i\in\mathbb{N}}$ de $\Sigma_1$ -en el lenguaje de la aritmética tal que para todo $S\subseteq\mathbb{N}$ la teoría $$T_S:=PA\cup\{\theta_i: i\in S\}\cup\{\neg \theta_j: j\not\in S\}$$ es coherente.

Ahora bien, como la secuencia $(\theta_i)_{i\in\omega}$ es computable, si $M\models T_S$ podemos recuperar $S$ computablemente a partir de $H_M$ Eso es, $S\le_TH_M$ . Y esto funciona para cualquier $S\subseteq\mathbb{N}$ por lo que el conjunto de grados de Turing de conjuntos de la forma $H_M$ es cofinal en el conjunto de grados de Turing.

---

Yendo un poco más allá, no es difícil demostrar que lo siguiente es equivalente para una licenciatura d :

• d es el grado de $H_M$ para algunos $M\models PA$ .

• d calcula una terminación de cada teoría computable consistente $T$ .

Es decir, los grados de $H_M$ s son exactamente los Títulos de AP . Una dirección es fácil: si d calcula una terminación de cada teoría computable $T$ Toma $T$ para ser PA y extraer de la terminación calculada $\hat{T}$ el conjunto $\{e:$ " $\varphi_e(e)\downarrow$ " $\in \hat{T}\}$ .

La otra dirección se lo piensa un momento. Queremos utilizar $H_M$ para construir una terminación de alguna teoría computable consistente $T$ pero tenemos que tener cuidado: $M$ podría pensar que $T$ ¡es incoherente! Así que tenemos que tener cuidado con la forma en que hacemos malabarismos con las consideraciones internas y externas aquí. Lo que hacemos es lo siguiente: repasamos una a una las frases de nuestro idioma y añadimos la frase que estamos considerando a la terminación que estamos construyendo si $H_M$ piensa que su negación añadiría una contradicción estrictamente más corta que cualquier contradicción que añada.

Por el Teorema de la base baja existen modelos $M$ donde $H_M$ es baja. Tenga en cuenta que esta es la parte difícil: hacer $H_M$ complicado era sólo una construcción directa, pero haciendo $H_M$ simple requiere un verdadero esfuerzo.

---

EDIT: Probablemente ya lo sepas, pero sólo para otros lectores: una idea algo relevante aquí es la de la sistema estándar . (En realidad, esto debería ser un comentario a la respuesta, pero es demasiado largo).

Para $M\models$ PA y $a\in M$ decimos que $a$ códigos un conjunto $X$ de números naturales estándar si para todos los $i$ tenemos $$p_i\vert a\iff i\in X,$$ donde $p_i$ denota el $i$ el primero. Sea $SS(M)$ denotan el conjunto de conjuntos de números naturales estándar codificados por elementos de $M$ .

Si $M$ es estándar, $SS(M)$ es sólo el conjunto de conjuntos finitos. Si $M$ no es estándar, sin embargo, ocurre algo genial: mediante un argumento de desbordamiento, el conjunto $SS(M)$ ¡resulta ser un conjunto Scott! Un conjunto de Scott es una familia de conjuntos de números naturales que es cerrada bajo unión y reducibilidad de Turing y tal que para cada árbol infinito $T\subseteq 2^{<\omega}$ en el conjunto, hay un camino a través de $T$ en el set. En particular, cada conjunto de Scott contiene un grado PA, y los conjuntos de Scott pueden caracterizarse alternativamente como ideales de Turing tales que para cada conjunto en el ideal, hay en el ideal un conjunto de grado PA relativo al conjunto original - por lo que están relacionados en cierto sentido con la versión "relativizada" de su pregunta. (Otro dato interesante es que si $M_0$ es un segmento inicial no estándar de $M$ que satisface PA, entonces $SS(M_0)=SS(M)$ .)

Un problema natural en este punto es si cada conjunto de Scott es el sistema estándar de algún modelo de AP. Scott demostró que cada conjunto contable de Scott es el sistema estándar de algún modelo contable de PA; más tarde, Knight y Nadel extendieron esto a los conjuntos de Scott de cardinalidad $\omega_1$ resolviendo así el problema bajo el supuesto de CH. El problema general, sin embargo, sigue abierto (y véase este reciente artículo de Gitman para ver algunos avances interesantes relacionados con el forzamiento).

Por cierto, también podemos hablar de sistemas estándar relativos a no modelos estándar de AP: si $M, N$ son modelos arbitrarios de PA con $M\subsetneq_{end}N$ podemos seguir hablando de elementos de $N$ subconjuntos de codificación de $M$ y la resultante " $M$ -sistema estándar" $SS_M(N)$ . El mismo argumento de desbordamiento que en el caso estándar muestra que $(M, SS_M(N))\models$ WKL. Que yo sepa, estos sistemas estándar generalizados no están bien estudiados, pero El libro de Kossak y Schmerl contiene información al respecto (especialmente el capítulo 7).