Teoría de conjuntos descriptiva eficaz

Un espacio polaco efectivo es un espacio métrico separable completo que tiene una presentación computable . Dichos espacios se estudian tanto en la teoría descriptiva de conjuntos efectiva como en el análisis constructivo . En particular, ejemplos estándar de espacios polacos como la recta real , el conjunto de Cantor y el espacio de Baire son todos espacios polacos efectivos.

La jerarquía aritmética , también conocida como jerarquía de Kleene - Mostowski, clasifica ciertos conjuntos según la complejidad de las fórmulas que los definen. Cualquier conjunto que recibe una clasificación se denomina "aritmético".

De manera más formal, la jerarquía aritmética asigna clasificaciones a las fórmulas en el lenguaje de la aritmética de primer orden . Las clasificaciones se denotan${\displaystyle \Sigma _{n}^{0}}$y${\displaystyle \Pi _{n}^{0}}$para números naturales n (incluido el 0). Las letras griegas que aparecen aquí son símbolos de letra clara , lo que indica que las fórmulas no contienen parámetros fijos.

Si una fórmula${\displaystyle \phi }$es lógicamente equivalente a una fórmula con solo cuantificadores acotados entonces${\displaystyle \phi }$se le asignan las clasificaciones${\displaystyle \Sigma _{0}^{0}}$y${\displaystyle \Pi _{0}^{0}}$.

Las clasificaciones${\displaystyle \Sigma _{n}^{0}}$y${\displaystyle \Pi _{n}^{0}}$se definen inductivamente para cada número natural n utilizando las siguientes reglas:

• Si${\displaystyle \phi }$es lógicamente equivalente a una fórmula de la forma${\displaystyle \exists n_{1}\exists n_{2}\cdots \exists n_{k}\psi }$, dónde${\displaystyle \psi }$es${\displaystyle \Pi _{n}^{0}}$, entonces${\displaystyle \phi }$se le asigna la clasificación${\displaystyle \Sigma _{n+1}^{0}}$.
• Si${\displaystyle \phi }$es lógicamente equivalente a una fórmula de la forma${\displaystyle \forall n_{1}\forall n_{2}\cdots \forall n_{k}\psi }$, dónde${\displaystyle \psi }$es${\displaystyle \Sigma _{n}^{0}}$, entonces${\displaystyle \phi }$se le asigna la clasificación${\displaystyle \Pi _{n+1}^{0}}$.