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 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 descriptiva de conjuntos efectiva . ^[1]

El foco central de la teoría hiperaritmética son los conjuntos de números naturales conocidos como conjuntos hiperaritméticos . Hay tres formas equivalentes de definir esta clase de conjuntos; El estudio de las relaciones entre estas diferentes definiciones es una motivación 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 se puede definir mediante una fórmula de aritmética de segundo orden con sólo 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 mediante una fórmula de aritmética de segundo orden con sólo cuantificadores de conjuntos universales y ningún otro cuantificador de conjuntos. Un conjunto es si es ambos 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 se pueden definir mediante saltos de Turing infinitamente iterados . Esta segunda definición también muestra que los conjuntos hiperaritméticos se pueden clasificar 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 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 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 es una notación para λ + 1; ${\displaystyle \langle 1,n\rangle }$
• Supongamos 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 se puede definir tomando uniones efectivas en todos los niveles en lugar de sólo notaciones para ordinales límite. ^[2]

Sólo hay un número contable de notaciones ordinales, ya que cada notación es un número natural; así hay un ordinal contable que es el supremo de todos los ordinales que tienen notación. Este ordinal se conoce como ordinal Church-Kleene y se denota . Tenga en cuenta que este ordinal todavía es contable, siendo el símbolo sólo 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 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 uno . 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 secuencia 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 sólo de δ , no de la notación particular utilizada, y por lo tanto está bien definido. al 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 iterados de Turing. Un conjunto X de números naturales se clasifica en el nivel δ de la jerarquía hiperaritmética, para , si X es reducible de Turing a . Siempre habrá al menos tal δ 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.

Denotemos el ésimo nivel de la jerarquía construible y sea el mapa de un miembro de la O de Kleene al ordinal que representa. Un subconjunto de es hiperaritmético si y sólo si es miembro de . Un subconjunto de es definible mediante una fórmula si y solo si su imagen debajo es -definible en , donde proviene 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 recursividad en tipos superiores.

Una tercera caracterización de los conjuntos hiperaritméticos, debida a Kleene, utiliza funcionales computables de tipo superior . El funcional 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 un 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 en relación con . ${\displaystyle {}^{2}E}$

Ejemplo: el conjunto de verdad de la aritmética

Todo conjunto aritmético es hiperaritmético, pero existen muchos otros conjuntos hiperaritméticos. Un ejemplo de un conjunto hiperaritmético y 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 , por lo que no ocupa un lugar alto en la jerarquía hiperaritmética, aunque no es aritméticamente definible mediante 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 integridad también son fundamentales para la teoría. Un conjunto de números naturales es completo si está en el nivel de la jerarquía analítica y todo conjunto de números naturales es reducible en muchos uno a él. La definición de un subconjunto completo del espacio de Baire ( ) es similar. Se completan varios conjuntos asociados con la teoría hiperaritmética : ${\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 tal 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 ordinales recursivos . ${\displaystyle \phi _{e}(x,y)}$
• El conjunto de elementos del espacio de Baire que son 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 límites se derivan de estos resultados de integridad. Para cualquier conjunto S de notaciones ordinales, existe tal que cada elemento de S sea una notación para un ordinal menor que . Para cualquier subconjunto T del espacio de Baire que consta únicamente de funciones características de buenos ordenamientos, 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 }$

Hiperaritmeticidad e hipergrados relativizados.

La definición de 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 cambia de modo que se permite que la enumeración computable de una secuencia de notaciones ordinales utilice X como oráculo. Se denota el conjunto de números que son notaciones ordinales relativas a X. Se denota el supremo de los ordinales representados en ; 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 puede relativizarse 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 sólo si existe un tal que X sea reducible a Turing . Si y entonces la notación se utiliza para indicar que X e Y son hiperaritméticamente equivalentes . Ésta 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 es equivalente 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 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 recursividad α , 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 las funciones recursivas y la 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 recursividad 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 jerarquía hiperaritmética , Elsevier. ISBN 0-444-50072-3 

Citas

1. Teoría de la computabilidad de conjuntos hiperaritméticos
2. SG Simpson, La jerarquía basada en el operador de salto, páginas 268-269. El Simposio Kleene (Holanda Septentrional, 1980)
3. CJ Ash, J. Knight, Estructuras computables y 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 automorfismo 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 de YouTube