Teoría descriptiva de conjuntos efectiva

rama de las matemáticas

La teoría descriptiva de conjuntos eficaz es la rama de la teoría descriptiva de conjuntos que se ocupa de conjuntos de reales que tienen definiciones de caras claras ; es decir, definiciones que no requieren un parámetro real arbitrario (Moschovakis 1980). Así, la teoría descriptiva de conjuntos eficaz combina la teoría descriptiva de conjuntos con la teoría de la recursividad .

Construcciones

Espacio polaco efectivo

Un espacio polaco efectivo es un espacio métrico separable completo que tiene una presentación computable. Estos espacios se estudian tanto en la teoría descriptiva de conjuntos eficaz 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. Todo conjunto que recibe una clasificación se denomina "aritmético".

Más formalmente, 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 y para números naturales n (incluido 0). Las letras griegas aquí son símbolos claros , 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 sólo 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 todo 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 está , 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 está , 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, ​​Galeno (1985). Aspectos recursivos de la teoría descriptiva de conjuntos. Prensa de la Universidad de Oxford. págs. 124–38. ISBN 978-0-19-503602-2. SEÑOR  0786122.
• Moschovakis, Yiannis N. (1980). Teoría descriptiva de conjuntos . Holanda del Norte. ISBN 0-444-70199-0.Segunda edición disponible en línea