La Jerarquía Aritmética
La jerarquía aritmética clasifica conjuntos de números naturales por el número de cuantificadores alternos necesarios para definirlos, vinculando la complejidad lógica con grados de incomputabilidad.
Definition
La jerarquía aritmética estratifica los conjuntos definibles en la aritmética de primer orden contando las alternancias de cuantificadores no acotados delante de una matriz computable, con los conjuntos sigma-n definidos por un bloque que comienza con un cuantificador existencial y los conjuntos pi-n por uno que comienza con un cuantificador universal.
Scope
Este tema abarca la clasificación de conjuntos definibles en los niveles sigma, pi y delta mediante la alternancia de cuantificadores sobre relaciones computables, el teorema de Post que relaciona la jerarquía con el problema de la parada iterado y los saltos de Turing, la estrictez de la jerarquía y su extensión a la jerarquía analítica.
Core questions
- ¿Cómo mide la alternancia de cuantificadores la complejidad de un conjunto?
- ¿Cómo se relacionan entre sí las clases sigma, pi y delta en cada nivel?
- ¿Cómo se corresponde la jerarquía con la iteración del problema de la parada?
- ¿Por qué la jerarquía es estricta, con cada nivel propiamente más grande que el anterior?
Key theories
- Clasificación de cuantificadores
- Un conjunto es sigma-n si es definible por n bloques de cuantificadores alternos que comienzan existencialmente sobre una relación computable, y pi-n si comienzan universalmente; los conjuntos computablemente enumerables son exactamente los conjuntos sigma-uno.
- Teorema de Post
- Un conjunto es sigma-(n+1) exactamente cuando es computablemente enumerable relativo al n-ésimo salto de Turing, vinculando los niveles de la jerarquía con problemas de la parada relativizados iterados.
- Estrictez de la jerarquía
- Cada salto de Turing es estrictamente más complejo que el anterior, por lo que cada nivel de la jerarquía aritmética contiene propiamente los niveles inferiores y la jerarquía no colapsa.
Clinical relevance
La jerarquía aritmética es el criterio estándar para la complejidad de los problemas definibles en lógica y ciencias de la computación: localiza problemas como la totalidad, la finitud y la cofinitud de conjuntos computables en niveles precisos, y enmarca el límite entre lo que es computablemente enumerable y lo que requiere recursos no computables más potentes.
History
Kleene y Mostowski introdujeron independientemente la jerarquía aritmética alrededor de 1943, clasificando conjuntos por la complejidad de los cuantificadores sobre predicados computables. El teorema de Post conectó la jerarquía con el salto de Turing, unificando las perspectivas basadas en la definibilidad y en la computabilidad, y el marco se extendió posteriormente hacia arriba en la jerarquía analítica.
Key figures
- Stephen Cole Kleene
- Andrzej Mostowski
- Emil Post
Related topics
Seminal works
- rogers1987
- soare1987
- cutland1980
Frequently asked questions
- ¿Qué significa un nivel superior en la jerarquía?
- Más cuantificadores alternos significan una definición más compleja y, según el teorema de Post, un problema que requiere más iteraciones del problema de la parada para decidirse. Los conjuntos más altos en la jerarquía son estrictamente menos accesibles a la computación que los que están por debajo de ellos.
- ¿Dónde se sitúan los conjuntos computablemente enumerables?
- Ocupan el nivel sigma-uno, definibles por un único cuantificador existencial sobre una relación computable. Sus complementos ocupan el nivel pi-uno, y los conjuntos que son ambos, los conjuntos delta-uno, son exactamente los conjuntos computables.