Teoría hiperaritmética

En la teoría de la computabilidad , la teoría hiperaritmética es una generalización de la computabilidad de Turing . Tiene estrechas conexiones con la definibilidad en la aritmética de segundo orden y con sistemas débiles de teoría de conjuntos , como la teoría de conjuntos de Kripke-Platek . Es una herramienta importante en la teoría de conjuntos descriptiva efectiva . ^{[ 1 ]}

El eje central de la teoría hiperaritmética son los conjuntos de números naturales conocidos como conjuntos hiperaritméticos . Existen tres formas equivalentes de definir esta clase de conjuntos; el estudio de las relaciones entre estas diferentes definiciones constituye una de las motivaciones para el estudio de la teoría hiperaritmética.

La primera definición de los conjuntos hiperaritméticos utiliza la jerarquía analítica . Un conjunto de números naturales se clasifica en el nivel${\displaystyle \Sigma _{1}^{1}}$de esta jerarquía si es definible por una fórmula de aritmética de segundo orden con solo cuantificadores de conjuntos existenciales y ningún otro cuantificador de conjuntos. Un conjunto se clasifica en el nivel${\displaystyle \Pi _{1}^{1}}$de la jerarquía analítica si es definible por una fórmula de aritmética de segundo orden con solo cuantificadores de conjuntos universales y ningún otro cuantificador de conjuntos. Un conjunto es${\displaystyle \Delta _ {1}^{1}}$si es ambos${\displaystyle \Sigma _{1}^{1}}$y${\displaystyle \Pi _{1}^{1}}$. Los conjuntos hiperaritméticos son exactamente los${\displaystyle \Delta _ {1}^{1}}$conjuntos.

La definición de conjuntos hiperaritméticos como${\displaystyle \Delta _ {1}^{1}}$No depende directamente de los resultados de computabilidad. Una segunda definición equivalente muestra que los conjuntos hiperaritméticos pueden definirse mediante saltos de Turing iterados infinitamente . Esta segunda definición también muestra que los conjuntos hiperaritméticos pueden clasificarse en una jerarquía que extiende la jerarquía aritmética ; los conjuntos hiperaritméticos son precisamente los conjuntos a los que se les asigna un rango en esta jerarquía.

Cada nivel de la jerarquía hiperaritmética se indexa mediante un número ordinal contable (ordinal), pero no todos los ordinales contables corresponden a un nivel de la jerarquía. Los ordinales utilizados por la jerarquía son aquellos con una notación ordinal , que es una descripción concreta y efectiva del ordinal.

Una notación ordinal es una descripción efectiva de un ordinal contable mediante un número natural. Se requiere un sistema de notaciones ordinales para definir la jerarquía hiperaritmética. La propiedad fundamental que debe tener una notación ordinal es que describe el ordinal en términos de ordinales más pequeños de manera efectiva. La siguiente definición inductiva es típica; utiliza una función de emparejamiento.${\displaystyle \langle \cdot ,\cdot \rangle }$.

• El número 0 es una notación para el ordinal 0.
• Si n es una notación para un ordinal λ entonces${\displaystyle \langle 1,n\rangle }$es una notación para λ + 1;
• Supongamos que δ es un ordinal límite . Una notación para δ es un número de la forma${\displaystyle \langle 2,e\rangle }$donde e es el índice de una función computable total.${\displaystyle \phi _{e}}$de tal manera que para cada n ,${\displaystyle \phi _{e}(n)}$es una notación para un ordinal λ _n menor que δ y δ es el supremo del conjunto${\displaystyle \{\lambda _{n}\mid n\in \mathbb {N} \}}$.

Esto también puede definirse tomando uniones efectivas en todos los niveles en lugar de solo notaciones para ordinales límite. ^{[ 2 ]}

Solo hay una cantidad numerable de notaciones ordinales, ya que cada notación es un número natural; por lo tanto, hay un ordinal numerable que es el supremo de todos los ordinales que tienen una notación. Este ordinal se conoce como el ordinal Church-Kleene y se denota${\displaystyle \omega _ {1}^{CK}}$. Nótese que este ordinal sigue siendo contable, siendo el símbolo solo una analogía con el primer ordinal no contable,${\displaystyle \omega _{1}}$El conjunto de todos los números naturales que son notaciones ordinales se denota${\displaystyle {\mathcal {O}}}$y llamado Kleene's${\displaystyle {\mathcal {O}}}$.

Las notaciones ordinales se utilizan para definir saltos de Turing iterados. Los conjuntos de números naturales utilizados para definir la jerarquía son${\displaystyle 0^{(\delta )}}$para cada${\displaystyle \delta <\omega _ {1}^{CK}}$.${\displaystyle 0^{(\delta )}}$a veces también se denota${\displaystyle H(\delta )}$, ^{[ 3 ]} o${\displaystyle H_{e}}$para una notación${\displaystyle e}$para${\displaystyle \delta }$. ^{[ 2 ]} Supongamos que δ tiene la notación e . Estos conjuntos fueron definidos por primera vez por Davis (1950) y Mostowski (1951). ^{[ 2 ]} El conjunto${\displaystyle 0^{(\delta )}}$se define usando e de la siguiente manera.

• Si δ = 0 entonces${\displaystyle 0^{(\delta )}=0}$es el conjunto vacío.
• Si δ = λ + 1 entonces${\displaystyle 0^{(\delta )}}$es el salto de Turing de${\displaystyle 0^{(\lambda )}}$Los conjuntos${\displaystyle 0^{(1)}}$y${\displaystyle 0^{(2)}}$son${\displaystyle 0'}$y${\displaystyle 0''}$, respectivamente.
• Si δ es un ordinal límite, sea${\displaystyle \langle \lambda _{n}\mid n\in \mathbb {N} \rangle }$Sea la secuencia de ordinales menores que δ dada por la notación e . El conjunto${\displaystyle 0^{(\delta )}}$viene dado por la regla${\displaystyle 0^{(\delta )}=\{\langle n,i\rangle \mid i\in 0^{(\lambda _{n})}\}}$Esta es la unión efectiva de los conjuntos .${\displaystyle 0^{(\lambda _{n})}}$.

Aunque la construcción de${\displaystyle 0^{(\delta )}}$depende de tener una notación fija para δ , y cada ordinal infinito tiene muchas notaciones, un teorema de Clifford Spector muestra que el grado de Turing de${\displaystyle 0^{(\delta )}}$depende únicamente de δ , no de la notación particular utilizada, y por lo tanto${\displaystyle 0^{(\delta )}}$está bien definido hasta el grado de Turing. ^{[ 2 ]}

La jerarquía hiperaritmética se define a partir de estos saltos de Turing iterados. Un conjunto X de números naturales se clasifica en el nivel δ de la jerarquía hiperaritmética, para${\displaystyle \delta <\omega _{1}^{CK}}$, si X es Turing reducible a${\displaystyle 0^{(\delta )}}$. Siempre habrá un mínimo de δ si existe alguno; es este mínimo δ el que mide el nivel de incomputabilidad de X.

Dejar${\displaystyle L_{\alpha }}$denotan el${\displaystyle \alpha }$nivel n de la jerarquía constructible , y dejemos${\displaystyle n:{\mathcal {O}}\to \omega _{1}^{CK}}$sea ​​el mapa de un miembro de la O de Kleene al ordinal que representa. Un subconjunto de${\displaystyle \mathbb {N} }$es hiperaritmético si y solo si es miembro de${\displaystyle L_{\omega _{1}^{CK}}}$. Un subconjunto de${\displaystyle \mathbb {N} }$es definible por un${\displaystyle \Pi _{1}^{1}}$fórmula si y solo si su imagen está debajo${\displaystyle n}$es${\displaystyle \Sigma _{1}}$-definible en${\displaystyle L_{\omega _{1}^{CK}}}$, dónde${\displaystyle \Sigma _{1}}$es de la jerarquía de fórmulas de Lévy. ^{[ 4 ]}

El teorema de Spector-Gandy establece que un subconjunto${\displaystyle x}$de${\displaystyle \mathbb {N} }$es definible por un${\displaystyle \Pi _{1}^{1}}$fórmula si y solo si hay una${\displaystyle \Sigma _{1}}$fórmula${\displaystyle \phi (u)}$de tal manera que${\displaystyle n\in x}$si y solo si${\displaystyle L_{\omega _{1}^{CK}}\vDash \phi (n)}$. ^{[ 5 ] Teorema 3.7.1}

Una tercera caracterización de los conjuntos hiperaritméticos, debida a Kleene, utiliza funcionales computables de tipo superior . El funcional de tipo 2${\displaystyle {}^{2}E\colon \mathbb {N} ^{\mathbb {N} }\to \mathbb {N} }$Se define por las siguientes reglas:

${\displaystyle {}^{2}E(f)=1\quad }$si existe un i tal que f ( i ) > 0,

${\displaystyle {}^{2}E(f)=0\quad }$si no existe ningún i tal que f ( i ) > 0.

Utilizando una definición precisa de computabilidad relativa a un funcional de tipo 2, Kleene demostró que un conjunto de números naturales es hiperaritmético si y solo si es computable en relación con${\displaystyle {}^{2}E}$.

Todo conjunto aritmético es hiperaritmético, pero existen muchos otros conjuntos hiperaritméticos. Un ejemplo de un conjunto hiperaritmético no aritmético es el conjunto T de números de Gödel de fórmulas de la aritmética de Peano que son verdaderas en los números naturales estándar.${\displaystyle \mathbb {N} }$El conjunto T es Turing equivalente al conjunto${\displaystyle 0^{(\omega )}}$y por lo tanto no ocupa un lugar alto en la jerarquía hiperaritmética, aunque no es aritméticamente definible por el teorema de indefinibilidad de Tarski .

Los resultados fundamentales de la teoría hiperaritmética demuestran que las tres definiciones anteriores definen la misma colección de conjuntos de números naturales. Estas equivalencias se deben a Kleene. Otra caracterización la proporciona el teorema de Suslin-Kleene .

Los resultados de completitud también son fundamentales para la teoría. Un conjunto de números naturales es${\displaystyle \Pi _{1}^{1}}$completo si está en el nivel${\displaystyle \Pi _{1}^{1}}$de la jerarquía analítica y cada${\displaystyle \Pi _{1}^{1}}$un conjunto de números naturales es reducible a él mediante la regla de muchos a uno . La definición de un${\displaystyle \Pi _{1}^{1}}$subconjunto completo del espacio de Baire (${\displaystyle \mathbb {N} ^{\mathbb {N} }}$) es similar. Varios conjuntos asociados con la teoría hiperaritmética son${\displaystyle \Pi _{1}^{1}}$completo:

• Kleene's${\displaystyle {\mathcal {O}}}$, el conjunto de números naturales que son notaciones para números ordinales
• El conjunto de números naturales e tales que la función computable${\displaystyle \phi _{e}\colon \mathbb {N} ^{2}\to 2}$Calcula la función característica de un buen ordenamiento de los números naturales. Estos son los índices de los ordinales recursivos .
• El conjunto de elementos del espacio de Baire que son las funciones características de un buen ordenamiento de los números naturales (utilizando un isomorfismo efectivo)${\displaystyle \mathbb {N} ^{\mathbb {N} }\cong \mathbb {N} ^{\mathbb {N} \times \mathbb {N} })}$.

Resultados conocidos como${\displaystyle \Sigma _{1}^{1}}$Los límites se derivan de estos resultados de completitud. Para cualquier${\displaystyle \Sigma _{1}^{1}}$conjunto S de notaciones ordinales, hay un${\displaystyle \alpha <\omega _{1}^{CK}}$de tal manera que cada elemento de S es una notación para un ordinal menor que${\displaystyle \alpha }$. Para cualquier${\displaystyle \Sigma _{1}^{1}}$subconjunto T del espacio de Baire que consta únicamente de funciones características de buenos ordenamientos, existe un${\displaystyle \alpha <\omega _{1}^{CK}}$de tal manera que cada ordinal representado en T sea menor que${\displaystyle \alpha }$.

La definición de${\displaystyle {\mathcal {O}}}$puede relativizarse a un conjunto X de números naturales: en la definición de una notación ordinal, la cláusula para ordinales límite se modifica de modo que la enumeración computable de una secuencia de notaciones ordinales pueda usar X como oráculo. El conjunto de números que son notaciones ordinales relativas a X se denota${\displaystyle {\mathcal {O}}^{X}}$. El supremo de los ordinales representados en${\displaystyle {\mathcal {O}}^{X}}$se denota${\displaystyle \omega _{1}^{X}}$; este es un ordinal contable no menor que${\displaystyle \omega _{1}^{CK}}$.

La definición de${\displaystyle 0^{(\delta )}}$también puede relativizarse a un conjunto arbitrario${\displaystyle X}$de números naturales. El único cambio en la definición es que${\displaystyle X^{(0)}}$se define como X en lugar del conjunto vacío, de modo que${\displaystyle X^{(1)}=X'}$es el salto de Turing de X , y así sucesivamente. En lugar de terminar en${\displaystyle \omega _{1}^{CK}}$La jerarquía relativa a X recorre todos los ordinales menores que${\displaystyle \omega _{1}^{X}}$.

La jerarquía hiperaritmética relativizada se utiliza para definir la reducibilidad hiperaritmética . Dados los conjuntos X e Y , decimos:${\displaystyle X\leq _{\text{HYP}}Y}$si y solo si hay una${\displaystyle \delta <\omega _{1}^{Y}}$de tal manera que X sea Turing reducible a${\displaystyle Y^{(\delta )}}$. Si${\displaystyle X\leq _{\text{HYP}}Y}$y${\displaystyle Y\leq _{\text{HYP}}X}$luego la notación${\displaystyle X\equiv _{\text{HYP}}Y}$Se utiliza para indicar que X e Y son hiperaritméticamente equivalentes . Esta es una relación de equivalencia más general que la equivalencia de Turing ; por ejemplo, todo conjunto de números naturales es hiperaritméticamente equivalente a su salto de Turing , pero no Turing equivalente a su salto de Turing. Las clases de equivalencia de la equivalencia hiperaritmética se conocen como hipergrados .

La función que toma un conjunto X para${\displaystyle {\mathcal {O}}^{X}}$Se conoce como hipersalto por analogía con el salto de Turing. Se han establecido muchas propiedades del hipersalto y de los hipergrados. En particular, se sabe que el problema de Post para los hipergrados tiene una respuesta positiva: para cada conjunto X de números naturales existe un conjunto Y de números naturales tal que${\displaystyle X<_{\text{HYP}}Y<_{\text{HYP}}{\mathcal {O}}^{X}}$.

La teoría hiperaritmética se generaliza mediante la teoría de la α -recursión , que es el estudio de subconjuntos definibles de ordinales admisibles . La teoría hiperaritmética es el caso especial en el que α es${\displaystyle \omega _{1}^{CK}}$.

• H. Rogers , Jr., 1967. La teoría de las funciones recursivas y la computabilidad efectiva , segunda edición, 1987, MIT Press. ISBN 0-262-68052-1(tapa blanda), ISBN 0-07-053522-1
• G. Sacks , 1990. Teoría de la recursión superior , Springer-Verlag. ISBN 3-540-19305-7
• S. Simpson , 1999. Subsistemas de aritmética de segundo orden , Springer-Verlag.
• CJ Ash, JF Knight , 2000. Estructuras computables y la jerarquía hiperaritmética , Elsevier. ISBN 0-444-50072-3

• Teoría descriptiva de conjuntos . Apuntes de David Marker, Universidad de Illinois en Chicago. 2002.
• Lógica Matemática II . Apuntes de Dag Normann, Universidad de Oslo. 2005.
• Antonio Montalbán: Universidad de California, Berkeley y creador de contenido para YouTube.