数式の算術的階層
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/05/20 04:36 UTC 版)
算術的階層では、ペアノ算術の言語で書かれた式を分類する。階層は自然数 n を使って、 Σ n 0 {\displaystyle \Sigma _{n}^{0}} および Π n 0 {\displaystyle \Pi _{n}^{0}} と記される。ここでのギリシア文字は細活字(lightface)であり、式に集合パラメータが含まれないことを示している。 式 ϕ {\displaystyle \phi } が有界量化子しか含まない式と論理的に等価であれば、 ϕ {\displaystyle \phi } は階層 Σ 0 0 {\displaystyle \Sigma _{0}^{0}} と Π 0 0 {\displaystyle \Pi _{0}^{0}} に相当する。 階層 Σ n 0 {\displaystyle \Sigma _{n}^{0}} と Π n 0 {\displaystyle \Pi _{n}^{0}} は、全ての自然数 n について以下のように帰納的に定義される。 ψ {\displaystyle \psi } が Π n 0 {\displaystyle \Pi _{n}^{0}} であるとき、 ∃ n 1 ⋯ ∃ n k ψ {\displaystyle \exists n_{1}\cdots \exists n_{k}\psi } という形式と論理的に等価な式 ϕ {\displaystyle \phi } は、階層 Σ n + 1 0 {\displaystyle \Sigma _{n+1}^{0}} に相当する。 ψ {\displaystyle \psi } が Σ n 0 {\displaystyle \Sigma _{n}^{0}} であるとき、 ∀ n l ⋯ ∀ n k ψ {\displaystyle \forall n_{l}\cdots \forall n_{k}\psi } という形式と論理的に等価な式 ϕ {\displaystyle \phi } は、階層 Π n + 1 0 {\displaystyle \Pi _{n+1}^{0}} に相当する。 あらゆる式は等価な冠頭標準形に変換できるため、集合量化子のないあらゆる式は少なくとも1つの階層に分類される。意味のない量化子を式に追加することが可能なため、 Σ n 0 {\displaystyle \Sigma _{n}^{0}} または Π n 0 {\displaystyle \Pi _{n}^{0}} に分類された式は、n より大きいあらゆる m について Σ m 0 {\displaystyle \Sigma _{m}^{0}} と Π m 0 {\displaystyle \Pi _{m}^{0}} にも分類可能である。従って、最も重要な分類は最小の n に対応する階層であり、他の分類はそこから決定可能である。
※この「数式の算術的階層」の解説は、「算術的階層」の解説の一部です。
「数式の算術的階層」を含む「算術的階層」の記事については、「算術的階層」の概要を参照ください。
- 数式の算術的階層のページへのリンク
