レヴィ階層

レヴィ階層と呼ばれる\(\Sigma_n\)と\(\Pi_n\)で表される集合論の論理式の階層は、\(n\)について帰納的に次のように定義される:

1. もし\(\phi\)が非有界な量化子を持たない一階集合論の論理式と同値であるなら、\(\phi\)は\(\Pi_0\)かつ\(\Sigma_0\)である。
2. もし\(\phi\)が\(\Pi_n\)であるような論理式\(\psi\)とある変数記号\(x_0, x_1, x_2, \ldots, x_k\)について\(\exists x_0 \exists x_1 \exists x_2 \cdots\exists x_k \psi\)と同値であるなら、\(\phi\)は\(\Sigma_{n+1}\)である。
3. もし\(\phi\)が\(\Sigma_n\)であるような論理式\(\psi\)とある変数記号\(x_0, x_1, x_2, \ldots, x_k\)について\(\forall x_0 \forall x_1 \forall x_2...\forall x_k \psi\)と同値であるなら、\(\phi\)は\(\Pi_{n+1}\)である。

読者はレヴィ階層と同じく\(\Sigma_n\)と\(\Pi_n\)で表される算術の論理式の階層である算術的階層と混乱しないように気を付けなければならない。

もしある論理式が\(\Sigma_n\)でも\(\Pi_n\)であるなら、それは\(\Delta_n\)とも呼ばれる。\(\Sigma_0\)と\(\Pi_0\)と\(\Delta_0\)は全て等価であり、多くの基本的な集合論的概念を表すのに十分であることに注意せよ。

例

• \(x\)を変数記号とすると、\(\exists x(x=x)\)は\(\Sigma_1\)論理式である。
• \(x,y\)をメタに相異なる変数記号とすると、\(\exists(x\in y)(x=x)\)は\(y\)が自由変数である\(\Sigma_0\)論理式である。
• \(\chi(x_0,x_1,x_2,x_3,x_4,x_5)\)を6個の自由変数を持つ一階集合論の論理式とすると、\(\forall x_0\forall x_1\exists x_2\exists x_3\exists x_4\forall(x_5\in x_2)\chi(x_0,x_1,x_2,x_3,x_4,x_5)\)は\(\Pi_2\)論理式である。