Jerarquía aritmética
La jerarquía aritmética, o jerarquía de Kleene clasifica ciertos conjuntos basándose en la complejidad de las fórmulas que los definen.
Todo conjunto que recibe una clasificación es llamado aritmético.
La jerarquía aritmética es importante en la teoría de recursión, teoría de conjuntos descriptivos eficientes, y el estudio de teorías formales tales como aritmética de Peano.
El algoritmo de Tarski-Kuratowski da una forma fácil de obtener un límite superior sobre las clasificaciones que se asignan a una fórmula y al conjunto que la misma define.
La jerarquía aritmética asigna clasificaciones a las fórmulas en el lenguaje de axiomas de Peano (aritmética de primer orden).
para números naturales n. Las letras griegas son aquí símbolos sin resaltar, que indica que las fórmulas no contienen parámetros de conjunto.
se definen en forma inductiva para todo número natural n utilizando las siguientes reglas: Sea un conjunto X definido por la fórmula φ(n) en el lenguaje de aritmética de Peano si
Un conjunto es definible mediante aritmética de primer orden si el mismo es definido por alguna fórmula en el lenguaje de la aritmética de Peano.
es: X es aritméticamente reducible a Y La relación
definida por la regla es una relación de equivalencia.
Las clases de equivalencia de esta relación son llamadas los grados aritméticos; los mismos se encuentran parcialmente ordenados en
El espacio de Cantor, expresado por
Notar que elementos del espacio de Cantor pueden ser identificados con conjuntos de enteros y elementos del espacio de Baire con funciones de enteros en enteros.
A un subconjunto del espacio de Cantor se le asigna la clasificación
si es definible por una fórmula del tipo
Al conjunto se le asigna la clasificación
si es definible por una fórmula del tipo
entonces se le da la clasificación adicional
el conjunto de todas las cadenas binarias que no son todos 0 (o en forma equivalente el conjunto de todos los conjuntos de enteros no vacíos).
Es de destacar que si bien ambos elementos del espacio de Cantor (que son conjuntos de enteros) y subconjuntos del espacio de Cantor son clasificados en jerarquías aritméticas, estas no poseen la misma jerarquía.
De hecho las relaciones entre estas dos jerarquías son interesantes y no triviales.
del espacio de Cantor en general no son los mismos elementos
del espacio de Cantor.
Sin embargo, numerosos resultados interesantes relacionan estas dos jerarquías.
Existen dos maneras en que se puede clasificar en la jerarquía aritmética un subconjunto del espacio de Baire.
Una definición similar se utiliza para definir la jerarquía aritmética en potencias cartesianas finitas del espacio de Baire o espacio de Cantor, utilizando fórmulas con varias variables libres.
La jerarquía aritmética puede ser definida en todo espacio polaco efectivo; la definición es particularmente simple para espacios de Cantor y de Baire porque ellos se ajustan al lenguaje de la ordinario de la aritmética de segundo orden.
en letras negritas es la unión de
para todos los conjuntos de enteros Y.
Notar que la jerarquía en negritas es la jerarquía estándar de los conjuntos de Borel.
