En lógica matemática y teoría descriptiva de conjuntos , la jerarquía analítica es una extensión de la jerarquía aritmética . La jerarquía analítica de fórmulas incluye fórmulas en el lenguaje de la aritmética de segundo orden , que pueden tener cuantificadores tanto sobre el conjunto de números naturales ,, y sobre funciones de a . La jerarquía analítica de conjuntos clasifica los conjuntos por las fórmulas que se pueden utilizar para definirlos; es la versión lightface de la jerarquía proyectiva .
La jerarquía analítica de fórmulas
La notación indica la clase de fórmulas en el lenguaje de la aritmética de segundo orden sin cuantificadores establecidos. Este idioma no contiene parámetros establecidos. Las letras griegas aquí son símbolos de cara clara , que indican esta elección de idioma. Cada símbolo en negrita correspondiente denota la clase correspondiente de fórmulas en el lenguaje extendido con un parámetro para cada real ; ver jerarquía proyectiva para más detalles.
Una fórmula en el lenguaje de la aritmética de segundo orden se define como si es lógicamente equivalente a una fórmula de la forma dónde es . Una fórmula se define como si es lógicamente equivalente a una fórmula de la forma dónde es . Esta definición inductiva define las clases y por cada número natural .
Debido a que cada fórmula tiene una forma normal prenex , cada fórmula en el lenguaje de la aritmética de segundo orden es o para algunos . Debido a que se pueden agregar cuantificadores sin sentido a cualquier fórmula, una vez que se le da a una fórmula la clasificación o para algunos se le darán las clasificaciones y para todos mas grande que .
La jerarquía analítica de conjuntos de números naturales.
A un conjunto de números naturales se le asigna la clasificación. si es definible por un fórmula. Al conjunto se le asigna la clasificación si es definible por un fórmula. Si el conjunto es a la vez y entonces se le da la clasificación adicional .
La los conjuntos se denominan hiperaritméticos . La teoría hiperaritmética proporciona una clasificación alternativa de estos conjuntos por medio de funcionales computables iterados .
La jerarquía analítica en subconjuntos del espacio de Cantor y Baire
La jerarquía analítica se puede definir en cualquier espacio polaco efectivo ; la definición es particularmente simple para el espacio de Cantor y Baire porque encajan con el lenguaje de la aritmética ordinaria de segundo orden. El espacio de Cantor es el conjunto de todas las secuencias infinitas de 0 y 1; El espacio de Baire es el conjunto de todas las secuencias infinitas de números naturales. Ambos son espacios polacos .
La axiomatización ordinaria de la aritmética de segundo orden utiliza un lenguaje basado en conjuntos en el que los cuantificadores de conjuntos pueden verse naturalmente como cuantificadores en el espacio de Cantor. A un subconjunto del espacio de Cantor se le asigna la clasificación si es definible por un fórmula. Al conjunto se le asigna la clasificación si es definible por un fórmula. Si el conjunto es a la vez y entonces se le da la clasificación adicional .
Un subconjunto del espacio de Baire tiene un subconjunto correspondiente del espacio de Cantor debajo del mapa que toma cada función de a a la función característica de su gráfico. A un subconjunto del espacio de Baire se le da la clasificación, , o si y solo si el subconjunto correspondiente del espacio de Cantor tiene la misma clasificación. Se da una definición equivalente de la jerarquía analítica en el espacio de Baire definiendo la jerarquía analítica de fórmulas utilizando una versión funcional de la aritmética de segundo orden; entonces la jerarquía analítica en subconjuntos del espacio de Cantor se puede definir a partir de la jerarquía en el espacio de Baire. Esta definición alternativa da exactamente las mismas clasificaciones que la primera definición.
Dado que el espacio de Cantor es homeomorfo para cualquier poder cartesiano finito de sí mismo, y el espacio de Baire es homeomórfico para cualquier poder cartesiano finito de sí mismo, la jerarquía analítica se aplica igualmente bien al poder cartesiano finito de uno de estos espacios. Una extensión similar es posible para los poderes contables y para los productos de los poderes del espacio de Cantor y los poderes del espacio de Baire.
Extensiones
Como es el caso de la jerarquía aritmética , se puede definir una versión relativizada de la jerarquía analítica. El lenguaje se extiende para añadir un conjunto de símbolos constante A . Una fórmula en el lenguaje extendido se define inductivamente como o utilizando la misma definición inductiva que la anterior. Dado un conjunto, un conjunto se define como si es definible por un fórmula en la que el símbolo se interpreta como ; definiciones similares para y solicitar. Los conjuntos que son o , para cualquier parámetro Y , se clasifican en la jerarquía proyectiva .
Ejemplos de
- El conjunto de todos los números naturales que son índices de ordinales computables es un establecer que no es .
- El conjunto de elementos del espacio de Cantor que son las funciones características de los ordenamientos de pozos es un establecer que no es . De hecho, este conjunto no es para cualquier elemento del espacio Baire.
- Si se cumple el axioma de constructibilidad, entonces hay un subconjunto del producto del espacio de Baire consigo mismo que esy es el gráfico de un ordenamiento correcto del espacio de Baire. Si el axioma es válido, también hay un Bien ordenado del espacio Cantor.
Propiedades
Para cada tenemos las siguientes contenciones estrictas:
- ,
- ,
- ,
- .
Un conjunto que está en para algunos n se dice que es analítico . Se requiere cuidado para distinguir este uso del término conjunto analítico que tiene un significado diferente.
Mesa
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 | ||
⋮ | ⋮ |
Ver también
Referencias
- Rogers, H. (1967). Teoría de funciones recursivas y computabilidad efectiva . McGraw-Hill.
- Kechris, A. (1995). Teoría Clásica Descriptiva de Conjuntos (Textos de Posgrado en Matemáticas 156 ed.). Saltador. ISBN 0-387-94374-9.
- Jerarquía analítica en PlanetMath .