Una estratificación de predicados y fórmulas sobre los números naturales según el patrón y número de alternancias de cuantificadores de primer orden; las clases Σ_n, Π_n y Δ_n clasifican la definibilidad y decidibilidad en aritmética de primer orden.

Principio

Medir la complejidad de una fórmula por su cuantificador principal y el número de alternancias existenciales/universales; esta medida sintáctica se correlaciona con propiedades de computabilidad y de reducibilidad entre conjuntos de naturales.

Demostración

Una fórmula de la forma ∃x∀y R(x,y) (con R decidible) pertenece a Σ_2; la clase Σ_1 corresponde a las fórmulas existenciales cuyas extensiones son exactamente los conjuntos recursivamente enumerables, mientras que Π_1 corresponde a descripciones universales (co-r.e.).

Aplicación incorrecta

Tratar la jerarquía aritmética como una medida de complejidad temporal o espacial práctica, o confundir sus niveles Σ/Π con jerarquías de complejidad sobre estructuras finitas, conduce a errores sobre lo que la jerarquía representa.

Consecuencia

Una aplicación correcta permite enunciar con precisión la decidibilidad, la completitud de problemas para niveles dados y qué tipos de reducciones u acceso a oráculos se requieren para decidir predicados.

Inversión

Invertir el patrón del cuantificador líder mueve entre clases duales (Σ_n ↔ Π_n); esto intercambia la complejidad existencial y universal y a menudo cambia el carácter de decidibilidad (r.e. ↔ co-r.e.).

Límite

Se aplica a la aritmética de primer orden sobre N y a fórmulas aritméticamente definibles; excluye lógicas de orden superior, jerarquías de análisis y clases de complejidad definidas por recursos en estructuras finitas.

Tensión semántica

Hay tensión con la jerarquía analítica y con jerarquías de complejidad (por ejemplo, la jerarquía polinómica): estratificaciones aparentemente semejantes difieren en dominio y en los recursos computacionales que formalizan.

Síntesis

La jerarquía aritmética organiza la definibilidad aritmética por alternancia de cuantificadores de modo que la forma sintáctica predice propiedades de computabilidad y decidibilidad, delimitando r.e., co-r.e. y niveles superiores.