Teoría hiperaritmética

En 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 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 foco 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 es una de las motivaciones para el estudio de la teoría hiperaritmética.

Conjuntos hiperaritméticos y definibilidad

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 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 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 si es tanto y . Los conjuntos hiperaritméticos son exactamente los conjuntos. ${\displaystyle \Sigma _{1}^{1}}$ ${\displaystyle \Pi _{1}^{1}}$ ${\displaystyle \Delta _{1}^{1}}$ ${\displaystyle \Sigma _{1}^{1}}$ ${\displaystyle \Pi _{1}^{1}}$ ${\displaystyle \Delta _{1}^{1}}$

Conjuntos hiperaritméticos y saltos de Turing iterados: la jerarquía hiperaritmética

La definición de conjuntos hiperaritméticos no depende directamente de los resultados de computabilidad. Una segunda definición equivalente muestra que los conjuntos hiperaritméticos pueden definirse utilizando saltos de Turing infinitamente iterados . 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 exactamente los conjuntos a los que se les asigna un rango en esta jerarquía. ${\displaystyle \Delta _{1}^{1}}$

Cada nivel de la jerarquía hiperaritmética está indexado por 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 eficaz 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 describa el ordinal en términos de ordinales más pequeños de una manera eficaz. 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 es una notación para λ + 1; ${\displaystyle \langle 1,n\rangle }$
• Supóngase que δ es un ordinal límite . Una notación para δ es un número de la forma , donde e es el índice de una función computable total tal que para cada n , es una notación para un ordinal λ _n menor que δ y δ es el sup del conjunto . ${\displaystyle \langle 2,e\rangle }$ ${\displaystyle \phi _{e}}$ ${\displaystyle \phi _{e}(n)}$ ${\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 un número contable de notaciones ordinales, ya que cada notación es un número natural; por lo tanto, hay un ordinal contable que es el supremo de todos los ordinales que tienen una notación. Este ordinal se conoce como ordinal de Church-Kleene y se denota . Nótese que este ordinal sigue siendo contable, ya que el símbolo es solo una analogía con el primer ordinal incontable, . El conjunto de todos los números naturales que son notaciones ordinales se denota y se llama ordinal de Kleene . ${\displaystyle \omega _{1}^{CK}}$ ${\displaystyle \omega _{1}}$ ${\displaystyle {\mathcal {O}}}$ ${\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 para cada . a veces también se denota , ^[3] o para una notación para . ^[2] Supongamos que δ tiene notación e . Estos conjuntos fueron definidos por primera vez por Davis (1950) y Mostowski (1951). ^[2] El conjunto se define utilizando e de la siguiente manera. ${\displaystyle 0^{(\delta )}}$ ${\displaystyle \delta <\omega _{1}^{CK}}$ ${\displaystyle 0^{(\delta )}}$ ${\displaystyle H(\delta )}$ ${\displaystyle H_{e}}$ ${\displaystyle e}$ ${\displaystyle \delta }$ ${\displaystyle 0^{(\delta )}}$

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

Aunque la construcción de 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 depende solo de δ , no de la notación particular utilizada, y por lo tanto está bien definido hasta el grado de Turing. ^[2] ${\displaystyle 0^{(\delta )}}$ ${\displaystyle 0^{(\delta )}}$ ${\displaystyle 0^{(\delta )}}$

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 , si X es reducible por Turing a . Siempre habrá un mínimo de tales δ si lo hay; es este mínimo δ el que mide el nivel de incomputabilidad de X . ${\displaystyle \delta <\omega _{1}^{CK}}$ ${\displaystyle 0^{(\delta )}}$

Conjuntos hiperaritméticos y constructibilidad

Sea , el nivel n de la jerarquía construible , y sea , la función de un miembro de la O de Kleene al ordinal que representa. Un subconjunto de es hiperaritmético si y solo si es un miembro de . Un subconjunto de es definible por una fórmula si y solo si su imagen bajo es -definible en , donde es de la jerarquía de fórmulas de Lévy. ^[4] ${\displaystyle L_{\alpha }}$ ${\displaystyle \alpha }$ ${\displaystyle n:{\mathcal {O}}\to \omega _{1}^{CK}}$ ${\displaystyle \mathbb {N} }$ ${\displaystyle L_{\omega _{1}^{CK}}}$ ${\displaystyle \mathbb {N} }$ ${\displaystyle \Pi _{1}^{1}}$ ${\displaystyle n}$ ${\displaystyle \Sigma _{1}}$ ${\displaystyle L_{\omega _{1}^{CK}}}$ ${\displaystyle \Sigma _{1}}$

Conjuntos hiperaritméticos y recursión en tipos superiores

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

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

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

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

Ejemplo: el conjunto de verdad de la aritmética

Todo conjunto aritmético es hiperaritmético, pero hay 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 . El conjunto T es equivalente de Turing al conjunto , y por lo tanto no ocupa un lugar alto en la jerarquía hiperaritmética, aunque no es definible aritméticamente por el teorema de indefinibilidad de Tarski . ${\displaystyle \mathbb {N} }$ ${\displaystyle 0^{(\omega )}}$

Resultados fundamentales

Los resultados fundamentales de la teoría hiperaritmética muestran que las tres definiciones anteriores definen la misma colección de conjuntos de números naturales. Estas equivalencias se deben a Kleene.

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

• Kleene , el conjunto de números naturales que son notaciones para números ordinales ${\displaystyle {\mathcal {O}}}$
• El conjunto de números naturales e tales que la función computable calcula la función característica de un buen ordenamiento de los números naturales. Estos son los índices de los ordinales recursivos . ${\displaystyle \phi _{e}(x,y)}$
• 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} })}$

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

Hiperaritmética relativizada e hipergrados

La definición de se puede relativizar 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 cambia de modo que se permite que la enumeración computable de una secuencia de notaciones ordinales utilice X como oráculo. El conjunto de números que son notaciones ordinales relativas a X se denota . El supremo de los ordinales representados en se denota ; este es un ordinal contable no menor que . ${\displaystyle {\mathcal {O}}}$ ${\displaystyle {\mathcal {O}}^{X}}$ ${\displaystyle {\mathcal {O}}^{X}}$ ${\displaystyle \omega _{1}^{X}}$ ${\displaystyle \omega _{1}^{CK}}$

La definición de también se puede relativizar a un conjunto arbitrario de números naturales. El único cambio en la definición es que se define como X en lugar del conjunto vacío, por lo que es el salto de Turing de X , y así sucesivamente. En lugar de terminar en la jerarquía relativa a X recorre todos los ordinales menores que . ${\displaystyle 0^{(\delta )}}$ ${\displaystyle X}$ ${\displaystyle X^{(0)}}$ ${\displaystyle X^{(1)}=X'}$ ${\displaystyle \omega _{1}^{CK}}$ ${\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 si y solo si hay un tal que X es reducible por Turing a . Si y entonces se utiliza la notación para indicar que X e Y son hiperaritméticamente equivalentes . Esta es una relación de equivalencia más burda que la equivalencia de Turing ; por ejemplo, cada conjunto de números naturales es hiperaritméticamente equivalente a su salto de Turing pero no equivalente por Turing a su salto de Turing. Las clases de equivalencia de equivalencia hiperaritmética se conocen como hipergrados . ${\displaystyle X\leq _{\text{HYP}}Y}$ ${\displaystyle \delta <\omega _{1}^{Y}}$ ${\displaystyle Y^{(\delta )}}$ ${\displaystyle X\leq _{\text{HYP}}Y}$ ${\displaystyle Y\leq _{\text{HYP}}X}$ ${\displaystyle X\equiv _{\text{HYP}}Y}$

La función que lleva un conjunto X a 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 {\mathcal {O}}^{X}}$ ${\displaystyle X<_{\text{HYP}}Y<_{\text{HYP}}{\mathcal {O}}^{X}}$

Generalizaciones

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}}$

Relación con otras jerarquías

Esta caja:

• vista
• hablar
• editar

Referencias

• H. Rogers , Jr., 1967. La teoría de funciones recursivas y computabilidad efectiva , segunda edición, 1987, MIT Press. ISBN  0-262-68052-1 (libro de bolsillo), 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 

Citas

1. Teoría de computabilidad de conjuntos hiperaritméticos
2. SG Simpson, La jerarquía basada en el operador de salto, págs. 268-269. El simposio de Kleene (Holanda del Norte, 1980)
3. CJ Ash, J. Knight, Estructuras computables y la jerarquía hiperaritmética (Estudios de lógica y fundamentos de las matemáticas, 2000), cap. 5
4. D. Natingga, Teorema de incrustación para el grupo de automorfismos de los grados de enumeración α (p.27), tesis doctoral, Universidad de Leeds, 2019.

Enlaces externos

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