Jerarquía de Levy

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 lenguaje de teoría de conjuntos. Esto es análogo a la jerarquía aritmética , que proporciona una clasificación similar para oraciones del lenguaje aritmético .

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 a conjuntos , respectivamente.

El primer nivel de la jerarquía de Lévy se define como que contiene sólo fórmulas sin cuantificadores ilimitados y se denota por . ^[1] Los siguientes niveles se obtienen encontrando una fórmula en forma normal prenex que sea demostrablemente equivalente a ZFC y contando 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 una forma y 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 prenexa, 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 necesaria ]}

La notación original de Lévy era (resp. ) debido a la equivalencia lógica demostrable, ^[4] estrictamente hablando, los niveles anteriores deben denominarse (resp. ) para especificar la teoría en la que se lleva a cabo la equivalencia, sin embargo, generalmente queda claro a partir de contexto. ^{[5] págs. 441–442} Pohlers definió en particular semánticamente qué 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 a veces se define para otras teorías S. En este caso y por sí mismos se refieren solo a fórmulas que comienzan con una secuencia de cuantificadores con como máximo i −1 alternancias, ^{[ cita necesaria ]} y y se refieren a fórmulas equivalentes a y fórmulas en el lenguaje de la teoría S. Así, estrictamente hablando, los niveles y de la jerarquía de Lévy para ZFC definidos 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 =Δ 0 fó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 contable ω ^[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 α ésimo de 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 sobre y ^[10]
• x es finito ^{[4] p.15}
• Suma , multiplicación y exponenciación ordinales ^[11]
• El rango (con respecto al universo construible de Gödel ) de un conjunto ^{[7] p. 61}
• La clausura transitiva de un conjunto.

Σ 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 )}$

Π 1 -fórmulas y conceptos

• x es un cardenal
• x es un cardenal regular
• x es un límite cardinal
• x es un cardenal inaccesible .
• x es el conjunto de potencias 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 cardenal mensurable
• κ es un n - cardenal enorme

Π 2 -fórmulas y conceptos

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

Δ 3 -fórmulas y conceptos

Σ 3 -fórmulas y conceptos

• existe un cardenal supercompacto

Π 3 -fórmulas y conceptos

• κ es un cardenal extensible

Σ 4 -fórmulas y conceptos

• existe un cardenal extensible

Propiedades

Dejar . 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

Ver también

• Jerarquía aritmética
• Totalidad

Referencias

• Devlin, Keith J. (1984). Constructibilidad . Perspectivas en lógica matemática. Berlín: Springer-Verlag . págs. 27–30. Zbl  0542.03029.
• Jech, Thomas (2003). Teoría de conjuntos . Monografías de Springer en Matemáticas (edición del Tercer Milenio). Berlín, Nueva York: Springer-Verlag . pag. 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 . Memoria. Soy. Matemáticas. Soc. vol. 57. Zbl  0202.30502.

Citas

1. Walicki, Michal (2012). Lógica Matemática , pág. 225. World Scientific Publishing Co. Pte. Limitado. ISBN 9789814343862​ 
2. T. Jech, 'Teoría de conjuntos: edición del tercer milenio, revisada y ampliada'. Monografías de Springer en Matemáticas (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, "Cardenales indescriptibles e incrustaciones elementales". Revista de lógica simbólica vol. 56, edición. 2 (1991), págs.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 para graduados (págs. 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: introducción a los cardenales grandes (p.83). Consultado el 1 de julio de 2022.
12. Azriel Lévy, "Sobre la complejidad lógica de varios axiomas de la teoría de conjuntos" (1971). Apareciendo en Teoría de conjuntos axiomática: Actas de simposios en matemáticas puras, vol. 13 parte 1 , págs.219--230