En la teoría de la recursividad , 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 eficaz .
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 conjuntos hiperaritméticos utiliza la jerarquía analítica . Un conjunto de números naturales se clasifica a nivelde esta jerarquía si se puede definir mediante una fórmula de aritmética de segundo orden con solo cuantificadores de conjuntos existenciales y ningún otro conjunto de cuantificadores. Un conjunto se clasifica a nivelde la jerarquía analítica si se puede definir mediante una fórmula de aritmética de segundo orden con solo cuantificadores de conjuntos universales y ningún otro conjunto de cuantificadores. Un conjunto es si es ambos y . Los conjuntos hiperaritméticos son exactamente los conjuntos.
Conjuntos hiperaritméticos y saltos de Turing iterados: la jerarquía hiperaritmética
La definición de conjuntos hiperaritméticos como no depende directamente de los resultados de computabilidad. Una segunda definición equivalente muestra que los conjuntos hiperaritméticos se pueden definir usando 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.
Cada nivel de la jerarquía hiperaritmética corresponde a un número ordinal contable (ordinal), pero no todos los ordinales contables corresponden a un nivel de la jerarquía. Los ordinales usados 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 por 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 pequeños de una manera eficaz. La siguiente definición inductiva es típica; usa una función de emparejamiento .
- El número 0 es una notación del ordinal 0.
- Si n es una notación para un ordinal λ entonces es una notación para λ + 1;
- Suponga 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 totaltal que para cada n ,es una notación para un ordinal λ n menor que δ y δ es el sup del conjunto.
Sólo hay muchas notaciones ordinales contables, ya que cada notación es un número natural; por 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. Tenga en cuenta que este ordinal todavía es contable, 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 denotay llamó a Kleene's.
Las notaciones ordinales se utilizan para definir saltos de Turing iterados. Estos son conjuntos de números naturales denotados para cada . Suponga que δ tiene la notación e . El conjuntose define usando e de la siguiente manera.
- Si δ = 0 entonces es el conjunto vacío.
- Si δ = λ + 1 entonces es el salto de Turing de . Las notaciones y se utilizan comúnmente para y , respectivamente.
- Si δ es un ordinal límite, sea ser la secuencia de ordinales menor que δ dada por la notación e . El conjunto está dado por la regla . Esta es la unión efectiva de los conjuntos..
Aunque la construcción de depende de tener una notación fija para δ, y cada ordinal infinito tiene muchas notaciones, un teorema de 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.
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, por, si X es Turing reducible a. Siempre habrá al menos tal δ si lo hay; esto es lo menos δ que mide el nivel de incomputabilidad de X .
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 está definido por las siguientes reglas:
- si hay una i tal que f ( i )> 0,
- si no hay una 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 .
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 los 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 Turing equivalente al conjunto, por lo que no es alto en la jerarquía hiperaritmética, aunque no es definible aritméticamente por el teorema de indefinibilidad de Tarski .
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 escompletar si está a nivelde la jerarquía analítica y cadaconjunto de números naturales es muchos-uno reducible a él. La definición de un subconjunto completo del espacio de Baire () es similar. Varios conjuntos asociados con la teoría hiperaritmética son completo:
- De Kleene , 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 computablecalcula la función característica de un buen ordenamiento de los números naturales. Estos son los índices de 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.
Resultados conocidos como los límites se derivan de estos resultados de completitud. Para cualquierconjunto S de notaciones ordinales, hay untal que cada elemento de S es una notación para un ordinal menor que. Para cualquier subconjunto T del espacio de Baire que consta solo de funciones características de ordenamiento de pozos, hay untal que cada ordinal representado en T es menor que.
Hiperaritmeticidad e hipergrados relativizados
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 los ordinales límite se cambia para que la enumeración computable de una secuencia de notaciones ordinales pueda usar X como un oráculo. El conjunto de números que son notaciones ordinales relativas a X se denota. El supremo de ordinales representados en se denota ; este es un ordinal contable no menor que.
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 quese define como X en lugar del conjunto vacío, de modo quees el salto de Turing de X , y así sucesivamente. En lugar de terminar enla jerarquía relativa a X pasa por todos los ordinales menos de.
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 Turing reducible a. Si y luego 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 .
La función que toma un conjunto X parase conoce como el hiper salto por analogía con el salto de Turing. Se han establecido muchas propiedades del hipersalto e 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 hay un conjunto Y de números naturales tal que.
Generalizaciones
La teoría hiperaritmética se generaliza mediante la teoría de recursividad α , que es el estudio de subconjuntos definibles de ordinales admisibles . La teoría hiperaritmética es el caso especial en el que α es.
Relación con otras jerarquías
Lightface | Negrita | ||
Σ0 0 = Π0 0 = Δ0 0 (a veces lo mismo que Δ0 1) | Σ0 0= Π0 0= Δ0 0 (si está definido) | ||
Δ0 1= recursivo | Δ0 1= abierto | ||
Σ0 1= recursivamente enumerable | Π0 1 = recursivamente enumerable | Σ0 1= G = abierto | Π0 1= F = cerrado |
Δ0 2 | Δ0 2 | ||
Σ0 2 | Π0 2 | Σ0 2= F σ | Π0 2= G δ |
Δ0 3 | Δ0 3 | ||
Σ0 3 | Π0 3 | Σ0 3= G δσ | Π0 3= F σδ |
⋮ | ⋮ | ||
Σ0 <ω = Π0 <ω = Δ0 <ω = Σ1 0 = Π1 0 = Δ1 0= aritmético | Σ0 <ω= Π0 <ω= Δ0 <ω= Σ1 0= Π1 0= Δ1 0 = aritmética en negrita | ||
⋮ | ⋮ | ||
Δ0 α(α recursivo ) | Δ0 α(α contable ) | ||
Σ0 α | Π0 α | Σ0 α | Π0 α |
⋮ | ⋮ | ||
Σ0 ωCK 1 = Π0 ωCK 1 = Δ0 ωCK 1 = Δ1 1= hiperaritmético | Σ0 ω 1= Π0 ω 1= Δ0 ω 1= Δ1 1= B = Borel | ||
Σ1 1 = analítica de cara clara | Π1 1 = coanalítico de cara clara | Σ1 1= A = analítico | Π1 1= CA = coanalítico |
Δ1 2 | Δ1 2 | ||
Σ1 2 | Π1 2 | Σ1 2 = PCA | Π1 2 = CPCA |
Δ1 3 | Δ1 3 | ||
Σ1 3 | Π1 3 | Σ1 3 = PCPCA | Π1 3 = CPCPCA |
⋮ | ⋮ | ||
Σ1 <ω = Π1 <ω = Δ1 <ω = Σ2 0 = Π2 0 = Δ2 0= analítico | Σ1 <ω= Π1 <ω= Δ1 <ω= Σ2 0= Π2 0= Δ2 0= P = proyectiva | ||
⋮ | ⋮ |
Referencias
- H. Rogers, Jr., 1967. The Theory of Recursive Functions and Effective Computability , 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 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 la jerarquía hiperaritmética , Elsevier. ISBN 0-444-50072-3
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.