Jerarquía analítica

Concepto de lógica matemática y teoría de conjuntos.

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 tanto sobre el conjunto de números naturales , como sobre funciones desde hasta . La jerarquía analítica de conjuntos clasifica los conjuntos según las fórmulas que se pueden utilizar para definirlos; es la versión lightface de la jerarquía proyectiva . ${\displaystyle \mathbb {N} }$ ${\displaystyle \mathbb {N} }$ ${\displaystyle \mathbb {N} }$

La jerarquía analítica de las fórmulas.

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

Una fórmula en el lenguaje de la aritmética de segundo orden se define como si es lógicamente equivalente a una fórmula de la forma donde es . Una fórmula se define como si es lógicamente equivalente a una fórmula de la forma donde es . Esta definición inductiva define las clases y para todo número natural . ${\displaystyle \Sigma _{n+1}^{1}}$ ${\displaystyle \exists X_{1}\cdots \exists X_{k}\psi }$ ${\displaystyle \psi }$ ${\displaystyle \Pi _{n}^{1}}$ ${\displaystyle \Pi _{n+1}^{1}}$ ${\displaystyle \forall X_{1}\cdots \forall X_{k}\psi }$ ${\displaystyle \psi }$ ${\displaystyle \Sigma _{n}^{1}}$ ${\displaystyle \Sigma _{n}^{1}}$ ${\displaystyle \Pi _{n}^{1}}$ ${\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 o para algunos . Debido a que se pueden agregar cuantificadores sin sentido a cualquier fórmula, una vez que a una fórmula se le da la clasificación o para algunas se le darán las clasificaciones y para todas mayores que . ${\displaystyle \Sigma _{n}^{1}}$ ${\displaystyle \Pi _{n}^{1}}$ ${\displaystyle n}$ ${\displaystyle \Sigma _{n}^{1}}$ ${\displaystyle \Pi _{n}^{1}}$ ${\displaystyle n}$ ${\displaystyle \Sigma _{m}^{1}}$ ${\displaystyle \Pi _{m}^{1}}$ ${\displaystyle m}$ ${\displaystyle n}$

La jerarquía analítica de conjuntos de números naturales.

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

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

La jerarquía analítica en subconjuntos del espacio de Cantor y Baire.

La jerarquía analítica se puede definir en cualquier espacio polaco efectivo ; la definición es particularmente simple para el espacio de Cantor y Baire porque encaja con el lenguaje de la aritmética ordinaria de segundo orden. El espacio de Cantor es el conjunto de todas las secuencias 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, naturalmente, se puede considerar que los cuantificadores de conjuntos cuantifican el espacio de Cantor. A un subconjunto del espacio de Cantor se le asigna la clasificación si se puede definir mediante una fórmula (con una variable de conjunto libre y sin variables numéricas libres). Al conjunto se le asigna la clasificación si es definible mediante una fórmula. Si el conjunto es ambos y entonces se le da la clasificación adicional . ${\displaystyle \Sigma _{n}^{1}}$ ${\displaystyle \Sigma _{n}^{1}}$ ${\displaystyle \Pi _{n}^{1}}$ ${\displaystyle \Pi _{n}^{1}}$ ${\displaystyle \Sigma _{n}^{1}}$ ${\displaystyle \Pi _{n}^{1}}$ ${\displaystyle \Delta _{n}^{1}}$

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

Debido a que el espacio de Cantor es homeomorfo a cualquier potencia cartesiana finita de sí mismo, y el espacio de Baire es homeomorfo a cualquier potencia cartesiana finita de sí mismo, la jerarquía analítica se aplica igualmente bien a las potencias cartesianas finitas de uno de estos espacios. Es posible una extensión similar para potencias contables y para productos de potencias del espacio de Cantor y potencias del espacio de Baire.

Extensiones

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

Ejemplos

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

Propiedades

Para cada uno tenemos las siguientes contenciones estrictas: ${\displaystyle n}$

${\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 corresponde a algún n se dice que es analítico . Es necesario tener cuidado para distinguir este uso del término conjunto analítico , que tiene un significado diferente, a saber . ^[5] ${\displaystyle \Sigma _{n}^{1}}$ ${\displaystyle {\boldsymbol {\Sigma }}_{1}^{1}}$

Mesa

Esta caja:

• vista
• hablar
• editar

Ver también

• Jerarquía aritmética
• Jerarquía de Levy

Referencias

1. P. Odifreddi , Teoría clásica de la recursión (1989), p.378. Holanda Septentrional, 0-444-87295-7
2. PD Welch, "Sistemas débiles de determinación y definiciones aritméticas cuasi-inductivas" (versión borrador de 2010, p. 3). Consultado el 31 de julio de 2022.
3. P. Odifreddi, Teoría clásica de la recursión (1989), p.33. Holanda Septentrional, 0-444-87295-7
4. Quintanilla, M. (2022). "Los números del reino en los modelos internos de la teoría de conjuntos". arXiv : 2206.10754 [matemáticas.LO].
5. T. Jech , "El feliz nuevo mundo de la determinación" (descarga en PDF). Reseña de libro, Boletín de la Sociedad Estadounidense de Matemáticas , vol. 5, número 3, noviembre de 1981 (págs. 339--349).

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

• Jerarquía analítica en PlanetMath .