Jerarquía analítica

En lógica matemática y teoría descriptiva de conjuntos , la jerarquía analítica es una extensión de la jerarquía aritmética . La jerarquía analítica de fórmulas incluye fórmulas en el lenguaje de la aritmética de segundo orden , que pueden tener cuantificadores sobre el conjunto de números naturales ,${\displaystyle \mathbb {N} }$y sobre funciones de${\displaystyle \mathbb {N} }$a${\displaystyle \mathbb {N} }$La jerarquía analítica de conjuntos clasifica los conjuntos según las fórmulas que se pueden usar para definirlos; es la versión simplificada de la jerarquía proyectiva .

La notación${\displaystyle \Sigma _{0}^{1}=\Pi _{0}^{1}=\Delta _{0}^{1}}$ Indica la clase de fórmulas en el lenguaje de la aritmética de segundo orden con cuantificadores numéricos pero sin cuantificadores de conjuntos. Este lenguaje no contiene parámetros de conjuntos. Las letras griegas aquí son símbolos en letra clara , que indican la elección del lenguaje. Cada símbolo en negrita correspondiente denota la clase de fórmulas correspondiente en el lenguaje extendido con un parámetro para cada número real ; consulte la jerarquía proyectiva para obtener más detalles.

Una fórmula en el lenguaje de la aritmética de segundo orden se define como${\displaystyle \Sigma _{n+1}^{1}}$si es lógicamente equivalente a una fórmula de la forma${\displaystyle \exists X_{1}\cdots \exists X_{k}\psi }$dónde${\displaystyle \psi }$es${\displaystyle \Pi _{n}^{1}}$. Una fórmula se define como${\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 }$dónde${\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}$.

Kuratowski y Tarski demostraron en 1931 que toda fórmula en el lenguaje de la aritmética de segundo orden tiene una forma normal prenexa , ^{[ 1 ]} y por lo tanto es${\displaystyle \Sigma _{n}^{1}}$o${\displaystyle \Pi _{n}^{1}}$para algunos${\displaystyle n}$. Debido a que se pueden agregar cuantificadores sin sentido a cualquier fórmula, una vez que se le da la clasificación a una fórmula,${\displaystyle \Sigma _{n}^{1}}$o${\displaystyle \Pi _{n}^{1}}$para algunos${\displaystyle n}$Se le asignarán las clasificaciones${\displaystyle \Sigma _{m}^{1}}$y${\displaystyle \Pi _{m}^{1}}$a pesar de${\displaystyle m}$más que${\displaystyle n}$.

A un conjunto de números naturales se le asigna la clasificación${\displaystyle \Sigma _{n}^{1}}$si es definible por un${\displaystyle \Sigma _{n}^{1}}$fórmula (con una variable numérica libre y ninguna variable de conjunto libre). Al conjunto se le asigna la clasificación${\displaystyle \Pi _{n}^{1}}$si es definible por un${\displaystyle \Pi _{n}^{1}}$fórmula. Si el conjunto es ambos${\displaystyle \Sigma _{n}^{1}}$y${\displaystyle \Pi _{n}^{1}}$Luego se le otorga la clasificación adicional${\displaystyle \Delta _ {n}^{1}}$.

El${\displaystyle \Delta _ {1}^{1}}$Los conjuntos se denominan hiperaritméticos . La teoría hiperaritmética proporciona una clasificación alternativa de estos conjuntos mediante funcionales computables iterados .

La jerarquía analítica puede definirse en cualquier espacio polaco efectivo ; la definición es particularmente sencilla para los espacios de Cantor y Baire, ya que se ajustan al lenguaje de la aritmética ordinaria de segundo orden. El espacio de Cantor es el conjunto de todas las sucesiones infinitas de 0 y 1; el espacio de Baire es el conjunto de todas las sucesiones infinitas de números naturales. Ambos son espacios polacos .

La axiomatización ordinaria de la aritmética de segundo orden utiliza un lenguaje basado en conjuntos en el que los cuantificadores de conjunto pueden verse naturalmente como cuantificadores sobre el espacio de Cantor. A un subconjunto del espacio de Cantor se le asigna la clasificación${\displaystyle \Sigma _{n}^{1}}$si es definible por un${\displaystyle \Sigma _{n}^{1}}$fórmula (con una variable de conjunto libre y ninguna variable numérica libre). Al conjunto se le asigna la clasificación${\displaystyle \Pi _{n}^{1}}$si es definible por un${\displaystyle \Pi _{n}^{1}}$fórmula. Si el conjunto es ambos${\displaystyle \Sigma _{n}^{1}}$y${\displaystyle \Pi _{n}^{1}}$Luego se le otorga la clasificación adicional${\displaystyle \Delta _ {n}^{1}}$.

Un subconjunto del espacio de Baire tiene un subconjunto correspondiente del espacio de Cantor bajo el mapa que toma cada función de${\displaystyle \omega }$a${\displaystyle \omega }$a la función característica de su gráfica. A un subconjunto del espacio de Baire se le da la clasificación${\displaystyle \Sigma _{n}^{1}}$,${\displaystyle \Pi _{n}^{1}}$, o${\displaystyle \Delta _ {n}^{1}}$Si y solo si el subconjunto correspondiente del espacio de Cantor tiene la misma clasificación. Una definición equivalente de la jerarquía analítica en el espacio de Baire se obtiene definiendo la jerarquía analítica de fórmulas mediante una versión funcional de la aritmética de segundo orden; entonces, la jerarquía analítica en subconjuntos del espacio de Cantor puede definirse a partir de la jerarquía en el espacio de Baire. Esta definición alternativa proporciona exactamente las mismas clasificaciones que la primera definición.

Dado que el espacio de Cantor es homeomorfo a cualquier potencia cartesiana finita de sí mismo, y el espacio de Baire también lo es, la jerarquía analítica se aplica igualmente bien a potencias cartesianas finitas de cualquiera de estos espacios. Una extensión similar es posible para potencias numerables y para productos de potencias del espacio de Cantor y potencias del espacio de Baire.

Como ocurre con la jerarquía aritmética , se puede definir una versión relativizada de la jerarquía analítica. El lenguaje se extiende para añadir un símbolo de conjunto constante A. Una fórmula en el lenguaje extendido se define inductivamente como:${\displaystyle \Sigma _{n}^{1,A}}$o${\displaystyle \Pi _{n}^{1,A}}$utilizando la misma definición inductiva que la anterior. Dado un conjunto${\displaystyle Y}$, un conjunto se define como${\displaystyle \Sigma _{n}^{1,Y}}$si es definible por un${\displaystyle \Sigma _{n}^{1,A}}$fórmula en la que el símbolo${\displaystyle A}$se interpreta como${\displaystyle Y}$; definiciones similares para${\displaystyle \Pi _{n}^{1,Y}}$y${\displaystyle \Delta _{n}^{1,Y}}$aplicar. Los conjuntos que son${\displaystyle \Sigma _{n}^{1,Y}}$o${\displaystyle \Pi _{n}^{1,Y}}$, para cualquier parámetro Y , se clasifican en la jerarquía proyectiva y a menudo se denotan con letras griegas en negrita para indicar el uso de parámetros. ^{[ 2 ]}

• Para una relación${\displaystyle \prec }$en${\displaystyle \mathbb {N} ^{2}}$, la declaración "${\displaystyle \prec }$es un buen orden en${\displaystyle \mathbb {N} }$" es${\displaystyle \Pi _{1}^{1}}$(No confundir con el caso general de relaciones bien fundadas en conjuntos, véase jerarquía de Lévy ) .
• El conjunto de todos los números naturales que son índices de ordinales computables es un${\displaystyle \Pi _{1}^{1}}$conjunto que no es${\displaystyle \Sigma _{1}^{1}}$.
  • Estos conjuntos son exactamente los${\displaystyle \omega _{1}^{CK}}$-subconjuntos recursivamente enumerables de${\displaystyle \omega }$[ Bar75, pág. 168 ] 
• Una función${\displaystyle f:\mathbb {N} \to \mathbb {N} }$es definible por el formalismo de Herbrand de 1931 de sistemas de ecuaciones si y solo si${\displaystyle f}$es hiperaritmético. ^{[ 3 ]}
• El conjunto de funciones continuas${\displaystyle f:[0,1]\to \mathbb {[} 0,1]}$que tienen la propiedad de valor medio no es inferior a${\displaystyle \Delta _{2}^{1}}$en la jerarquía. ^{[ 4 ]}
• El conjunto de elementos del espacio de Cantor que son las funciones características de los buenos ordenamientos de${\displaystyle \omega }$es un${\displaystyle \Pi _{1}^{1}}$conjunto que no es${\displaystyle \Sigma _{1}^{1}}$De hecho, este conjunto no es${\displaystyle \Sigma _{1}^{1,Y}}$para cualquier elemento${\displaystyle Y}$del espacio de Baire.
• Si se cumple el axioma de constructibilidad , entonces existe un subconjunto del producto del espacio de Baire consigo mismo que es${\displaystyle \Delta _{2}^{1}}$y es la gráfica de un buen ordenamiento del espacio de Baire. Si el axioma se cumple, entonces también hay un${\displaystyle \Delta _{2}^{1}}$Buena organización del espacio de Cantor.

Para cada${\displaystyle n}$Tenemos las siguientes medidas de contención estrictas:

${\displaystyle \Pi _{n}^{1}\subset \Sigma _{n+1}^{1}}$,

${\displaystyle \Pi _{n}^{1}\subset \Pi _{n+1}^{1}}$,

${\displaystyle \Sigma _{n}^{1}\subset \Pi _{n+1}^{1}}$,

${\displaystyle \Sigma _{n}^{1}\subset \Sigma _{n+1}^{1}}$.

Un conjunto que está en${\displaystyle \Sigma _{n}^{1}}$para algún n se dice que es analítico . Es necesario tener cuidado de distinguir este uso del término conjunto analítico , que tiene un significado diferente, a saber:${\displaystyle {\boldsymbol {\Sigma }}_{1}^{1}}$. ^{[ 5 ]}

• Jerarquía aritmética
• Jerarquía de Lévy

• Rogers, H. (1967). Teoría de las funciones recursivas y la computabilidad efectiva . McGraw-Hill.
• Kechris, A. (1995). Teoría clásica descriptiva de conjuntos (Textos de posgrado en matemáticas, 156.ª  ed.). Springer. ISBN 0-387-94374-9.

• Jerarquía analítica en PlanetMath .