Jerarquía de Lévy

En teoría de conjuntos y lógica matemática , la jerarquía de Lévy , introducida por Azriel Lévy en 1965, es una jerarquía de fórmulas en el lenguaje formal de la teoría de conjuntos de Zermelo-Fraenkel , que normalmente se denomina simplemente el lenguaje de la teoría de conjuntos. Esto es análogo a la jerarquía aritmética , que proporciona una clasificación similar para las oraciones del lenguaje de la aritmética .

Definiciones

En el lenguaje de la teoría de conjuntos, las fórmulas atómicas tienen la forma x = y o x ∈ y, que representan predicados de igualdad y pertenencia al conjunto , respectivamente.

El primer nivel de la jerarquía de Lévy se define como aquel que contiene únicamente fórmulas sin cuantificadores ilimitados y se denota por . ^[1] Los siguientes niveles se dan al encontrar una fórmula en forma normal prenex que sea demostrablemente equivalente sobre ZFC y contar el número de cambios de cuantificadores : ^{[2] p. 184} ${\displaystyle \Delta _{0}=\Sigma _{0}=\Pi _{0}}$

Una fórmula se llama: ^{[1] [3]} ${\displaystyle A}$

• ${\displaystyle \Sigma _{i+1}}$Si es equivalente a en ZFC, donde es ${\displaystyle A}$ ${\displaystyle \exists x_{1}...\exists x_{n}B}$ ${\displaystyle B}$ ${\displaystyle \Pi _{i}}$
• ${\displaystyle \Pi _{i+1}}$Si es equivalente a en ZFC, donde es ${\displaystyle A}$ ${\displaystyle \forall x_{1}...\forall x_{n}B}$ ${\displaystyle B}$ ${\displaystyle \Sigma _{i}}$
• Si una fórmula tiene tanto una forma como una forma, se llama . ${\displaystyle \Sigma _{i}}$ ${\displaystyle \Pi _{i}}$ ${\displaystyle \Delta _{i}}$

Como una fórmula puede tener varias fórmulas equivalentes diferentes en forma normal prenex, puede pertenecer a varios niveles diferentes de la jerarquía. En este caso, el nivel más bajo posible es el nivel de la fórmula. ^{[ cita requerida ]}

La notación original de Lévy se debía (resp. ) a la equivalencia lógica demostrable, ^[4] estrictamente hablando, los niveles anteriores deberían denominarse (resp. ) para especificar la teoría en la que se lleva a cabo la equivalencia, sin embargo, suele quedar claro a partir del contexto. ^{[5] pp. 441–442} Pohlers ha definido en particular semánticamente, en la que una fórmula está " en una estructura ". ^[6] ${\displaystyle \Sigma _{i}^{\mathsf {ZFC}}}$ ${\displaystyle \Pi _{i}^{\mathsf {ZFC}}}$ ${\displaystyle \Sigma _{i}^{\mathsf {ZFC}}}$ ${\displaystyle \Pi _{i}^{\mathsf {ZFC}}}$ ${\displaystyle \Delta _{1}}$ ${\displaystyle \Delta _{1}}$ ${\displaystyle M}$

La jerarquía de Lévy se define a veces para otras teorías S . En este caso y por sí mismas se refieren solo a fórmulas que comienzan con una secuencia de cuantificadores con como máximo i −1 alternancias, ^{[ cita requerida ]} y y se refieren a fórmulas equivalentes a y fórmulas en el lenguaje de la teoría S . Por lo tanto, estrictamente hablando, los niveles y de la jerarquía de Lévy para ZFC definida anteriormente deberían denotarse por y . ${\displaystyle \Sigma _{i}}$ ${\displaystyle \Pi _{i}}$ ${\displaystyle \Sigma _{i}^{S}}$ ${\displaystyle \Pi _{i}^{S}}$ ${\displaystyle \Sigma _{i}}$ ${\displaystyle \Pi _{i}}$ ${\displaystyle \Sigma _{i}}$ ${\displaystyle \Pi _{i}}$ ${\displaystyle \Sigma _{i}^{ZFC}}$ ${\displaystyle \Pi _{i}^{ZFC}}$

Ejemplos

Σ0=Π0=Δ0Fórmulas y conceptos

• x = {y, z} ^{[7] pág. 14}
• x ⊆ y ^[8]
• x es un conjunto transitivo ^[8]
• x es un ordinal , x es un ordinal límite , x es un ordinal sucesor ^[8]
• x es un ordinal finito ^[8]
• El primer ordinal infinito ω ^[8]
• x es un par ordenado. La primera entrada del par ordenado x es a . La segunda entrada del par ordenado x es b ^{[7] p. 14}
• f es una función. x es el dominio/rango de la función f . y es el valor de f en x ^{[7] p. 14}
• El producto cartesiano de dos conjuntos.
• x es la unión de y ^[8]
• x es un miembro del nivel α de la L de Gödel ^[9]
• R es una relación con dominio/rango/campo a ^{[7] p. 14}

Δ1-Fórmulas y conceptos

• x es una relación bien fundada en y ^[10]
• x es finito ^{[4] p.15}
• Suma y multiplicación ordinal y exponenciación ^[11]
• El rango (con respecto al universo construible de Gödel ) de un conjunto ^{[7] p. 61}
• El cierre transitivo de un conjunto.
• La relación de especificabilidad Sp(A) para un conjunto A. ^[12]

Σ1-Fórmulas y conceptos

• x es contable .
• | X |≤| Y |, | X |=| Y |.
• x es construible.
• g es la restricción de la función f a a ^{[7] p. 23}
• g es la imagen de f en a ^{[7] p. 23}
• b es el ordinal sucesor de a ^{[7] p. 23}
• rango( x ) ^{[7] pág. 29}
• El colapso de Mostowski de ^{[7] p. 29} ${\displaystyle (x,\in )}$

P1-Fórmulas y conceptos

• x es un cardenal
• x es un cardinal regular
• x es un cardinal límite
• x es un cardenal inaccesible .
• x es el conjunto potencia de y

Δ2-Fórmulas y conceptos

• κ es γ - supercompacto

Σ2-Fórmulas y conceptos

• La hipótesis del continuo
• Existe un cardenal inaccesible
• Existe un cardinal medible
• κ es un cardenal n - enorme

P2-Fórmulas y conceptos

• El axioma de elección ^[13]
• La hipótesis del continuo generalizado ^[13]
• El axioma de constructibilidad : V = L ^[13]

Δ3-Fórmulas y conceptos

Σ3-Fórmulas y conceptos

• Existe un cardenal supercompacto

P3-Fórmulas y conceptos

• κ es un cardinal extensible

Σ4-Fórmulas y conceptos

• Existe un cardenal extensible

Propiedades

Sea . La jerarquía de Lévy tiene las siguientes propiedades: ^{[2] p. 184} ${\displaystyle n\geq 1}$

• Si es , entonces es . ${\displaystyle \phi }$ ${\displaystyle \Sigma _{n}}$ ${\displaystyle \lnot \phi }$ ${\displaystyle \Pi _{n}}$
• Si es , entonces es . ${\displaystyle \phi }$ ${\displaystyle \Pi _{n}}$ ${\displaystyle \lnot \phi }$ ${\displaystyle \Sigma _{n}}$
• Si y son , entonces , , , y son todos . ${\displaystyle \phi }$ ${\displaystyle \psi }$ ${\displaystyle \Sigma _{n}}$ ${\displaystyle \exists x\phi }$ ${\displaystyle \phi \land \psi }$ ${\displaystyle \phi \lor \psi }$ ${\displaystyle \exists (x\in z)\phi }$ ${\displaystyle \forall (x\in z)\phi }$ ${\displaystyle \Sigma _{n}}$
• Si y son , entonces , , , y son todos . ${\displaystyle \phi }$ ${\displaystyle \psi }$ ${\displaystyle \Pi _{n}}$ ${\displaystyle \forall x\phi }$ ${\displaystyle \phi \land \psi }$ ${\displaystyle \phi \lor \psi }$ ${\displaystyle \exists (x\in z)\phi }$ ${\displaystyle \forall (x\in z)\phi }$ ${\displaystyle \Pi _{n}}$
• Si es y es , entonces es . ${\displaystyle \phi }$ ${\displaystyle \Sigma _{n}}$ ${\displaystyle \psi }$ ${\displaystyle \Pi _{n}}$ ${\displaystyle \phi \implies \psi }$ ${\displaystyle \Pi _{n}}$
• Si es y es , entonces es . ${\displaystyle \phi }$ ${\displaystyle \Pi _{n}}$ ${\displaystyle \psi }$ ${\displaystyle \Sigma _{n}}$ ${\displaystyle \phi \implies \psi }$ ${\displaystyle \Sigma _{n}}$

Devlin pág. 29

Véase también

• Jerarquía aritmética
• Totalidad

Referencias

• Devlin, Keith J. (1984). Constructibilidad . Perspectivas en lógica matemática. Berlín: Springer-Verlag . pp. 27–30. Zbl  0542.03029.
• Jech, Thomas (2003). Teoría de conjuntos . Springer Monographs in Mathematics (edición del tercer milenio). Berlín, Nueva York: Springer-Verlag . pág. 183. ISBN. 978-3-540-44085-7.Zbl 1007.03002  .
• Kanamori, Akihiro (2006). "Levy y teoría de conjuntos". Anales de lógica pura y aplicada . 140 (1–3): 233–252. doi : 10.1016/j.apal.2005.09.009 . Zbl  1089.03004.
• Levy, Azriel (1965). Una jerarquía de fórmulas en la teoría de conjuntos . Mem. Am. Math. Soc. Vol. 57. Zbl  0202.30502.

Citas

1. Walicki, Michal (2012). Lógica matemática , pág. 225. World Scientific Publishing Co. Pte. Ltd. ISBN 9789814343862 
2. T. Jech, 'Teoría de conjuntos: edición del tercer milenio, revisada y ampliada'. Springer Monographs in Mathematics (2006). ISBN 3-540-44085-2.
3. J. Baeten, Filtros y ultrafiltros sobre subconjuntos definibles sobre ordinales admisibles (1986). p.10
4. A. Lévy, 'Una jerarquía de fórmulas en la teoría de conjuntos' (1965), segunda edición
5. K. Hauser, "Cardinales indescriptibles e incrustaciones elementales". Journal of Symbolic Logic vol. 56, núm. 2 (1991), pp.439--457.
6. W. Pohlers, Teoría de la prueba: el primer paso hacia la impredicatividad (2009) (p. 245)
7. Jon Barwise , Conjuntos y estructuras admisibles . Perspectivas en lógica matemática (1975)
8. D. Monk 2011, Teoría de conjuntos de graduados (pp.168--170). Archivado el 6 de diciembre de 2011
9. WAR Weiss, Introducción a la teoría de conjuntos (capítulo 13). Consultado el 1 de diciembre de 2022.
10. KJ Williams, Modelos mínimos de teorías de conjuntos de segundo orden (2019, p. 4). Consultado el 25 de julio de 2022.
11. FR Drake, Teoría de conjuntos: una introducción a los grandes cardinales (p. 83). Consultado el 1 de julio de 2022.
12. FR Drake, Set Theory: An Introduction to Large Cardinals (p. 127). Consultado el 4 de octubre de 2024.
13. Azriel Lévy, "Sobre la complejidad lógica de varios axiomas de la teoría de conjuntos" (1971). Publicado en Axiomatic Set Theory: Proceedings of Symposia in Pure Mathematics, vol. 13 parte 1 , pp.219--230