Jerarquía analítica

En lógica matemática y teoría descriptiva de conjuntos, la jerarquía analítica es un análogo de alto nivel de la jerarquía aritmética. Por lo tanto constituye la clasificación de los conjuntos mediante las fórmulas que los definen.

La jerarquía analítica es importante en teoría de la demostración y aritmética de segundo orden, entre otros campos.

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:

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

---