レヴィ階層

集合論と数理論理学において、 1965年にアズリエル・レヴィによって導入されたレヴィ階層は、ツェルメロ＝フレンケル集合論（ZFC）の形式言語における論理式の階層であり、一般に単に集合論の言語と呼ばれている。これは、算術の言語における文を同様に分類する算術階層と類似している。

集合論の用語では、原子式はx = y または x ∈ y の形式で表され、それぞれ等号と集合への所属を示す述語を表します。

レヴィ階層の第1レベルは、無制限の量化子を持たない式のみを含むものとして定義され、次のように表される。${\displaystyle \Delta _{0}=\Sigma _{0}=\Pi _{0}}$^{[ 1 ]}次のレベルは、 ZFC上で証明可能な同値性を持つ前置標準形の式を見つけ^、量化子の交替の数を数えることによって与えられる。^{[ 2 ] p.184} 

公式${\displaystyle A}$は次のように呼ばれます: ^{[ 1 ] [ 3 ]}

• $\displaystyle \Sigma _{i+1}}$もし${\displaystyle A}$と同等${\displaystyle \exists x_{1}...\exists x_{n}B}$ZFCでは、${\displaystyle B}$は$\displaystyle \Pi _{i}}$
• $\displaystyle \Pi _{i+1}}$もし${\displaystyle A}$と同等${\displaystyle \forall x_{1}...\forall x_{n}B}$ZFCでは、${\displaystyle B}$は$\displaystyle \Sigma _{i}}$
• 式が両方とも$\displaystyle \Sigma _{i}}$そして$\displaystyle \Pi _{i}}$形式、それは$\displaystyle \Delta _{i}}$。

数式は前置正規形において複数の異なる等価な数式を持つ可能性があるため、階層構造の複数の異なるレベルに属する可能性があります。この場合、最も低いレベルは数式自体のレベルとなります。

レヴィのオリジナルの記譜法は$\displaystyle \Sigma _{i}^{\mathsf {ZFC}}}$（それぞれ${\displaystyle \Pi _{i}^{\mathsf {ZFC}}}$）証明可能な論理的等価性により、^{[ 4 ]}厳密に言えば上記のレベルは次のように呼ばれるべきである。$\displaystyle \Sigma _{i}^{\mathsf {ZFC}}}$（それぞれ${\displaystyle \Pi _{i}^{\mathsf {ZFC}}}$）等価性が実施される理論を具体的に示すためであるが、通常は文脈から明らかである。^{[ 5 ] 441-442頁} ポーラーズは次のように定義している。$\displaystyle \Delta _{1}}$特に意味論的に、式は「$\displaystyle \Delta _{1}}$構造物の中で${\displaystyle M}$「. ^{[ 6 ]}

レヴィ階層は、他の理論Sに対しても定義されることがある。この場合$\displaystyle \Sigma _{i}}$そして$\displaystyle \Pi _{i}}$それ自体は、最大でi −1 回の交替を持つ量化子のシーケンスで始まる式のみを指し、$\displaystyle \Sigma _{i}^{S}}$そして $\displaystyle \Pi _{i}^{S}}$等価な式を参照する$\displaystyle \Sigma _{i}}$そして$\displaystyle \Pi _{i}}$理論Sの言語における数式。厳密に言えば、レベルは$\displaystyle \Sigma _{i}}$そして$\displaystyle \Pi _{i}}$上記で定義したZFCのレヴィ階層のは、で表す必要がある。 $\displaystyle \Sigma _{i}^{\mathsf {ZFC}}}$そして ${\displaystyle \Pi _{i}^{\mathsf {ZFC}}}$。

させて${\displaystyle n\geq 1}$レヴィ階層は以下の性質を持つ^{。[ 2 ] p.184} 

• もし${\displaystyle \phi }$は$\displaystyle \Sigma _{n}}$、 それから${\displaystyle \lnot \phi }$は$\displaystyle \Pi _{n}}$。
• もし${\displaystyle \phi }$は$\displaystyle \Pi _{n}}$、 それから${\displaystyle \lnot \phi }$は$\displaystyle \Sigma _{n}}$。
• もし${\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}}$。
• もし${\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}}$。
• もし${\displaystyle \phi }$は$\displaystyle \Sigma _{n}}$そして${\displaystyle \psi }$は$\displaystyle \Pi _{n}}$、 それから${\displaystyle \phi \implies \psi }$は$\displaystyle \Pi _{n}}$。
• もし${\displaystyle \phi }$は$\displaystyle \Pi _{n}}$そして${\displaystyle \psi }$は$\displaystyle \Sigma _{n}}$、 それから${\displaystyle \phi \implies \psi }$は$\displaystyle \Sigma _{n}}$。

 デブリン著、 29ページ

• 算術階層
• 絶対

• Devlin, Keith J. (1984).構成可能性. 数理論理学の展望. ベルリン: Springer-Verlag . pp. 27–30 . Zbl 0542.03029 .  
• Jech, Thomas (2003).集合論. Springer Monographs in Mathematics (Third Millennium  ed.). ベルリン、ニューヨーク: Springer-Verlag . p.  183. ISBN 978-3-540-44085-7. Zbl 1007.03002 . 
• 金森 章弘(2006) 「レヴィと集合論」。純粋論理と応用論理の年代記。140 ( 1–3 ): 233–252 .土井: 10.1016/j.apal.2005.09.009。Zbl 1089.03004。 
• レヴィ、アズリエル（1965）。集合論における公式の階層構造。Mem. Am. Math. Soc. Vol.  57. Zbl 0202.30502。