自然数の集合の算術的階層
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2020/05/20 04:36 UTC 版)
「算術的階層」の記事における「自然数の集合の算術的階層」の解説
ペアノ算術の言語で書かれた式 φ(n) で、集合 X が n ∈ X ↔ N ⊨ ϕ ( n ) {\displaystyle n\in X\leftrightarrow \mathbb {N} \models \phi (n)} のように定義されるとする。これはつまり、X の元が φ を満足する数ということを意味している。集合が一階算術で定義可能であるとは、ペアノ算術の言語で書かれた式で定義されることに他ならない。 一階算術で定義可能な自然数の集合 X は、 n {\displaystyle n} を自然数としたときの階層 Σ n 0 {\displaystyle \Sigma _{n}^{0}} 、 Π n 0 {\displaystyle \Pi _{n}^{0}} 、 Δ n 0 {\displaystyle \Delta _{n}^{0}} に以下のように分類される。X が Σ n 0 {\displaystyle \Sigma _{n}^{0}} に属する式で定義可能なら、 X {\displaystyle X} は階層 Σ n 0 {\displaystyle \Sigma _{n}^{0}} に分類される。X が Π n 0 {\displaystyle \Pi _{n}^{0}} に属する式で定義可能なら、 X {\displaystyle X} は階層 Π n 0 {\displaystyle \Pi _{n}^{0}} に分類される。 X {\displaystyle X} が Σ n 0 {\displaystyle \Sigma _{n}^{0}} にも Π n 0 {\displaystyle \Pi _{n}^{0}} にも属するなら、 X {\displaystyle X} は追加の階層 Δ n 0 {\displaystyle \Delta _{n}^{0}} に分類される。 なお、 Δ n 0 {\displaystyle \Delta _{n}^{0}} に属する式と言った場合、ほとんど意味をなさない。これはつまり、先頭の量化子が存在量化子か全称量化子の式を意味する。従って Δ n 0 {\displaystyle \Delta _{n}^{0}} に属する集合は Δ n 0 {\displaystyle \Delta _{n}^{0}} に属する式で定義されるのではなく、 Σ n 0 {\displaystyle \Sigma _{n}^{0}} に属する式と Π n 0 {\displaystyle \Pi _{n}^{0}} に属する式の両方で定義される集合である。 自然数の有限な直積集合の算術的階層の定義には並列定義が使われる。1つの自由変項の式の代わりに k 個の自由変項の式を使い、k-タプルの自然数の集合についての算術的階層を定義する。
※この「自然数の集合の算術的階層」の解説は、「算術的階層」の解説の一部です。
「自然数の集合の算術的階層」を含む「算術的階層」の記事については、「算術的階層」の概要を参照ください。
- 自然数の集合の算術的階層のページへのリンク