Jerarquía analítica

La notación ${\displaystyle \Sigma _{0}^{1}=\Pi _{0}^{1}=\Delta _{0}^{1}}$ indica la clase de fórmulas en el lenguaje de aritmética de segundo orden sin conjunto de cuantificadores. Este lenguaje no contiene parámetros de conjunto. Las letras griegas aquí son símbolos, que indican esta elección de lenguaje. Cada símbolo en negritas representa 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 aritmética de segundo orden se define mediante ${\displaystyle \Sigma _{n+1}^{1}}$ si es lógicamente equivalente a una fórmula del tipo ${\displaystyle \exists X_{1}\cdots \exists X_{k}\psi }$ donde ${\displaystyle \psi }$ es ${\displaystyle \Pi _{n}^{1}}$. Se define una fórmula ${\displaystyle \Pi _{n+1}^{1}}$ si es lógicamente equivalente a una fórmula de la forma ${\displaystyle \forall X_{1}\cdots \forall X_{k}\psi }$ donde ${\displaystyle \psi }$ es ${\displaystyle \Sigma _{n}^{1}}$. Esta definición inductiva define las clases ${\displaystyle \Sigma _{n}^{1}}$ y ${\displaystyle \Pi _{n}^{1}}$ para cada número natural ${\displaystyle n}$.

Como cada fórmula tiene una forma normal prenexa, cada fórmula en el lenguaje de la aritmética de segundo orden es ${\displaystyle \Sigma _{n}^{1}}$ o ${\displaystyle \Pi _{n}^{1}}$ para algún ${\displaystyle n}$. Como se pueden agregar cuantificadores sin sentido a cualquier fórmula, una vez que una fórmula recibe la clasificación ${\displaystyle \Sigma _{n}^{1}}$ o ${\displaystyle \Pi _{n}^{1}}$ para algún ${\displaystyle n}$ se le asignarán las clasificaciones ${\displaystyle \Sigma _{m}^{1}}$ y ${\displaystyle \Pi _{m}^{1}}$ para todo ${\displaystyle m}$ mayor que ${\displaystyle n}$.

Notar que muy rara vez tiene sentido referirse a la fórmula ${\displaystyle \Delta _{n}^{1}}$ ; el primer cuantificador de una fórmula es o bien existencial o universal.

Una serie de números es asignado a la clasificación ${\displaystyle \Sigma _{n}^{1}}$ si se puede definir por la fórmula ${\displaystyle \Sigma _{n}^{1}}$. Al conjunto se le asigna la clasificación ${\displaystyle \Pi _{n}^{1}}$ si se puede definir por la fórmula ${\displaystyle \Pi _{n}^{1}}$. Si el conjunto es a la vez ${\displaystyle \Sigma _{n}^{1}}$ y ${\displaystyle \Pi _{n}^{1}}$ se le dará la clasificación adicional ${\displaystyle \Delta _{n}^{1}}$.

Para cada n tenemos la siguiente contención estricta:

${\displaystyle \Pi _{n}^{1}\subset \Sigma _{n+1}^{1}}$,

${\displaystyle \Pi _{n}^{1}\subset \Pi _{n+1}^{1}}$,

${\displaystyle \Sigma _{n}^{1}\subset \Pi _{n+1}^{1}}$,

${\displaystyle \Sigma _{n}^{1}\subset \Sigma _{n+1}^{1}}$.

A un conjunto que se encuentra en ${\displaystyle \Sigma _{n}^{1}}$ para alguna n se le llama analítico.

• PlanetMath page