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 .

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]}${\estilo de visualización A}$

• ${\displaystyle \Sigma _{i+1}}$Si es equivalente a en ZFC, donde es${\estilo de visualización A}$${\displaystyle \existe x_{1}...\existe x_{n}B}$${\estilo de visualización B}$${\displaystyle \Pi_{i}}$
• ${\displaystyle \Pi _{i+1}}$Si es equivalente a en ZFC, donde es${\estilo de visualización A}$${\displaystyle \para todo x_{1}...\para todo x_{n}B}$${\estilo de visualización 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}}$${\estilo de visualización 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}}$$Estilo de visualización: Sigma-i$$Estilo de visualización: Pi _{i}^{S}}$${\displaystyle \Sigma _{i}}$${\displaystyle \Pi_{i}}$${\displaystyle \Sigma _{i}}$${\displaystyle \Pi_{i}}$$Estilo de visualización: Sigma-i-ZFC$${\displaystyle \Pi _{i}^{ZFC}}$

• 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}

• 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]

• 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,\en )}$

• 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

• κ es γ - supercompacto

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

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

• Existe un cardenal supercompacto

• κ es un cardinal extensible

• Existe un cardenal extensible

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

• Si es , entonces es .${\estilo de visualización \phi}$${\displaystyle \Sigma__{n}}$${\displaystyle \lno \phi}$${\displaystyle \Pi_{n}}$
• Si es , entonces es .${\estilo de visualización \phi}$${\displaystyle \Pi_{n}}$${\displaystyle \lno \phi}$${\displaystyle \Sigma__{n}}$
• Si y son , entonces , , , y son todos .${\estilo de visualización \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

• Jerarquía aritmética
• Totalidad

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