Jerarquía analítica

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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 jerarquía analítica de las fórmulas[editar]

La notación \Sigma^1_0 = \Pi^1_0 = \Delta^1_0 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 \Sigma^1_{n+1} si es lógicamente equivalente a una fórmula del tipo \exists X_1\cdots \exists X_k \psi donde \psi es \Pi^1_{n}. Se define una fórmula \Pi^1_{n+1} si es lógicamente equivalente a una fórmula de la forma \forall  X_1\cdots \forall X_k \psi donde \psi es \Sigma^1_{n}. Esta definición inductiva define las clases \Sigma^1_n y \Pi^1_n para cada número natural n.

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

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

La jerarquía analítica de series de números naturales[editar]

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

Propiedades[editar]

Para cada n tenemos la siguiente contención estricta:

\Pi^1_n \subset \Sigma^1_{n+1},
\Pi^1_n \subset \Pi^1_{n+1},
\Sigma^1_n \subset \Pi^1_{n+1},
\Sigma^1_n \subset \Sigma^1_{n+1}.

A un conjunto que se encuentra en \Sigma^1_n para alguna n se le llama analítico.

Enlaces externos[editar]

Referencias[editar]

Bibliografía[editar]

  • Rogers, H. (1967). Theory of recursive functions and effective computability. McGraw-Hill. 
  • Kechris, A. (1995). Classical Descriptive (Graduate Texts in Mathematics 156 edición). Springer. ISBN 0-387-94374-9.