From Wikipedia, the free encyclopedia
In
set theory and
mathematical logic , the Lévy hierarchy , introduced by
Azriel Lévy in 1965, is a hierarchy of formulas in the
formal language of the
Zermelo–Fraenkel set theory , which is typically called just the language of set theory. This is analogous to the
arithmetical hierarchy , which provides a similar classification for sentences of the language of
arithmetic .
Definitions
In the language of set theory,
atomic formulas are of the form x = y or x ∈ y, standing for
equality and
set membership predicates, respectively.
The first level of the Lévy hierarchy is defined as containing only formulas with no unbounded quantifiers and is denoted by
Δ
0
=
Σ
0
=
Π
0
{\displaystyle \Delta _{0}=\Sigma _{0}=\Pi _{0}}
.
[1] The next levels are given by finding a formula in
prenex normal form which is provably equivalent over ZFC, and counting the number of changes of
quantifiers :
[2] p. 184
A formula
A
{\displaystyle A}
is called:
[1]
[3]
Σ
i
+
1
{\displaystyle \Sigma _{i+1}}
if
A
{\displaystyle A}
is equivalent to
∃
x
1
.
.
.
∃
x
n
B
{\displaystyle \exists x_{1}...\exists x_{n}B}
in ZFC, where
B
{\displaystyle B}
is
Π
i
{\displaystyle \Pi _{i}}
Π
i
+
1
{\displaystyle \Pi _{i+1}}
if
A
{\displaystyle A}
is equivalent to
∀
x
1
.
.
.
∀
x
n
B
{\displaystyle \forall x_{1}...\forall x_{n}B}
in ZFC, where
B
{\displaystyle B}
is
Σ
i
{\displaystyle \Sigma _{i}}
If a formula has both a
Σ
i
{\displaystyle \Sigma _{i}}
form and a
Π
i
{\displaystyle \Pi _{i}}
form, it is called
Δ
i
{\displaystyle \Delta _{i}}
.
As a formula might have several different equivalent formulas in prenex normal form, it might belong to several different levels of the hierarchy. In this case, the lowest possible level is the level of the formula.[
citation needed ]
Lévy's original notation was
Σ
i
Z
F
C
{\displaystyle \Sigma _{i}^{\mathsf {ZFC}}}
(resp.
Π
i
Z
F
C
{\displaystyle \Pi _{i}^{\mathsf {ZFC}}}
) due to the provable logical equivalence,
[4] strictly speaking the above levels should be referred to as
Σ
i
Z
F
C
{\displaystyle \Sigma _{i}^{\mathsf {ZFC}}}
(resp.
Π
i
Z
F
C
{\displaystyle \Pi _{i}^{\mathsf {ZFC}}}
) to specify the theory in which the equivalence is carried out, however it is usually clear from context.
[5] pp. 441–442 Pohlers has defined
Δ
1
{\displaystyle \Delta _{1}}
in particular semantically, in which a formula is "
Δ
1
{\displaystyle \Delta _{1}}
in a structure
M
{\displaystyle M}
".
[6]
The Lévy hierarchy is sometimes defined for other theories S . In this case
Σ
i
{\displaystyle \Sigma _{i}}
and
Π
i
{\displaystyle \Pi _{i}}
by themselves refer only to formulas that start with a sequence of quantifiers with at most i −1 alternations,[
citation needed ] and
Σ
i
S
{\displaystyle \Sigma _{i}^{S}}
and
Π
i
S
{\displaystyle \Pi _{i}^{S}}
refer to formulas equivalent to
Σ
i
{\displaystyle \Sigma _{i}}
and
Π
i
{\displaystyle \Pi _{i}}
formulas in the language of the theory S . So strictly speaking the levels
Σ
i
{\displaystyle \Sigma _{i}}
and
Π
i
{\displaystyle \Pi _{i}}
of the Lévy hierarchy for ZFC defined above should be denoted by
Σ
i
Z
F
C
{\displaystyle \Sigma _{i}^{ZFC}}
and
Π
i
Z
F
C
{\displaystyle \Pi _{i}^{ZFC}}
.
Examples
Σ0 =Π0 =Δ0 formulas and concepts
Δ1 -formulas and concepts
Σ1 -formulas and concepts
x is
countable .
|X |≤|Y |, |X |=|Y |.
x is constructible.
g is the restriction of the function f to a
[7] p. 23
g is the image of f on a
[7] p. 23
b is the successor ordinal of a
[7] p. 23
rank(x )
[7] p. 29
The
Mostowski collapse of
(
x
,
∈
)
{\displaystyle (x,\in )}
[7] p. 29
Π1 -formulas and concepts
Δ2 -formulas and concepts
Σ2 -formulas and concepts
Π2 -formulas and concepts
Δ3 -formulas and concepts
Σ3 -formulas and concepts
Π3 -formulas and concepts
Σ4 -formulas and concepts
Properties
Let
n
≥
1
{\displaystyle n\geq 1}
. The Lévy hierarchy has the following properties:
[2] p. 184
If
ϕ
{\displaystyle \phi }
is
Σ
n
{\displaystyle \Sigma _{n}}
, then
¬
ϕ
{\displaystyle \lnot \phi }
is
Π
n
{\displaystyle \Pi _{n}}
.
If
ϕ
{\displaystyle \phi }
is
Π
n
{\displaystyle \Pi _{n}}
, then
¬
ϕ
{\displaystyle \lnot \phi }
is
Σ
n
{\displaystyle \Sigma _{n}}
.
If
ϕ
{\displaystyle \phi }
and
ψ
{\displaystyle \psi }
are
Σ
n
{\displaystyle \Sigma _{n}}
, then
∃
x
ϕ
{\displaystyle \exists x\phi }
,
ϕ
∧
ψ
{\displaystyle \phi \land \psi }
,
ϕ
∨
ψ
{\displaystyle \phi \lor \psi }
,
∃
(
x
∈
z
)
ϕ
{\displaystyle \exists (x\in z)\phi }
, and
∀
(
x
∈
z
)
ϕ
{\displaystyle \forall (x\in z)\phi }
are all
Σ
n
{\displaystyle \Sigma _{n}}
.
If
ϕ
{\displaystyle \phi }
and
ψ
{\displaystyle \psi }
are
Π
n
{\displaystyle \Pi _{n}}
, then
∀
x
ϕ
{\displaystyle \forall x\phi }
,
ϕ
∧
ψ
{\displaystyle \phi \land \psi }
,
ϕ
∨
ψ
{\displaystyle \phi \lor \psi }
,
∃
(
x
∈
z
)
ϕ
{\displaystyle \exists (x\in z)\phi }
, and
∀
(
x
∈
z
)
ϕ
{\displaystyle \forall (x\in z)\phi }
are all
Π
n
{\displaystyle \Pi _{n}}
.
If
ϕ
{\displaystyle \phi }
is
Σ
n
{\displaystyle \Sigma _{n}}
and
ψ
{\displaystyle \psi }
is
Π
n
{\displaystyle \Pi _{n}}
, then
ϕ
⟹
ψ
{\displaystyle \phi \implies \psi }
is
Π
n
{\displaystyle \Pi _{n}}
.
If
ϕ
{\displaystyle \phi }
is
Π
n
{\displaystyle \Pi _{n}}
and
ψ
{\displaystyle \psi }
is
Σ
n
{\displaystyle \Sigma _{n}}
, then
ϕ
⟹
ψ
{\displaystyle \phi \implies \psi }
is
Σ
n
{\displaystyle \Sigma _{n}}
.
Devlin p. 29
See also
References
Citations
^
a
b Walicki, Michal (2012). Mathematical Logic , p. 225. World Scientific Publishing Co. Pte. Ltd.
ISBN
9789814343862
^
a
b T. Jech, 'Set Theory: The Third Millennium Edition, revised and expanded'. Springer Monographs in Mathematics (2006). ISBN 3-540-44085-2.
^ J. Baeten,
Filters and ultrafilters over definable subsets over admissible ordinals (1986). p.10
^
a
b A. Lévy, 'A hierarchy of formulas in set theory' (1965), second edition
^ K. Hauser, "Indescribable cardinals and elementary embeddings". Journal of Symbolic Logic vol. 56, iss. 2 (1991), pp.439--457.
^ W. Pohlers, Proof Theory: The First Step into Impredicativity (2009) (p.245)
^
a
b
c
d
e
f
g
h
i
j
Jon Barwise , Admissible Sets and Structures . Perspectives in Mathematical Logic (1975)
^
a
b
c
d
e
f D. Monk 2011,
Graduate Set Theory (pp.168--170). Archived 2011-12-06
^ W. A. R. Weiss,
An Introduction to Set Theory (chapter 13). Accessed 2022-12-01
^ K. J. Williams,
Minimum models of second-order set theories (2019, p.4). Accessed 2022 July 25.
^ F. R. Drake, Set Theory: An Introduction to Large Cardinals (p.83). Accessed 1 July 2022.
^
a
b
c Azriel Lévy, "On the logical complexity of several axioms of set theory" (1971). Appearing in Axiomatic Set Theory: Proceedings of Symposia in Pure Mathematics, vol. 13 part 1 , pp.219--230