Teoría de conjuntos descriptivos eficaz

Rama de las matemáticas

La teoría de conjuntos descriptivos efectiva es la rama de la teoría de conjuntos descriptivos que se ocupa de conjuntos de números reales que tienen definiciones de cara clara ; es decir, definiciones que no requieren un parámetro real arbitrario (Moschovakis 1980). Por lo tanto, la teoría de conjuntos descriptivos efectiva combina la teoría de conjuntos descriptivos con la teoría de la recursión .

Construcciones

Espacio polaco 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 de conjuntos descriptivos efectivos como en el análisis constructivo . En particular, los ejemplos estándar de espacios polacos como la línea real , el conjunto de Cantor y el espacio de Baire son todos espacios polacos efectivos.

Jerarquía aritmética

La jerarquía aritmética , jerarquía aritmética o jerarquía de Kleene - Mostowski clasifica determinados conjuntos en función de la complejidad de las fórmulas que los definen. Cualquier conjunto que reciba 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 como y para los números naturales n (incluido el 0). Las letras griegas aquí son símbolos de letras claras , lo que indica que las fórmulas no contienen parámetros establecidos. ${\displaystyle \Sigma _{n}^{0}}$ ${\displaystyle \Pi _{n}^{0}}$

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

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

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

Referencias

• Mansfield, Richard; Weitkamp, ​​Galen (1985). Aspectos recursivos de la teoría descriptiva de conjuntos. Oxford University Press. pp. 124–38. ISBN 978-0-19-503602-2.Sr. 0786122  .
• Moschovakis, Yiannis N. (1980). Teoría de conjuntos descriptivos . Holanda Septentrional. ISBN 0-444-70199-0.Segunda edición disponible en línea