相対化算術的階層
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/05/20 04:36 UTC 版)
集合 X が 集合 Y に対して再帰的相対性を持つということを、Y を一種の神託機械として X を求められることと定義すると、これを算術的階層全体に拡張し、Y に対して X が Σ n 0 {\displaystyle \Sigma _{n}^{0}} 、 Δ n 0 {\displaystyle \Delta _{n}^{0}} 、 Π n 0 {\displaystyle \Pi _{n}^{0}} であるということをそれぞれ Σ n 0 , Y {\displaystyle \Sigma _{n}^{0,Y}} 、 Δ n 0 , Y {\displaystyle \Delta _{n}^{0,Y}} 、 Π n 0 , Y {\displaystyle \Pi _{n}^{0,Y}} と記述する。このために、整数の集合Y を固定し、ペアノ算術の言語に Y のメンバーシップ述語を追加する。X が Σ n 0 , Y {\displaystyle \Sigma _{n}^{0,Y}} に属するとは、この拡張された言語で書かれた Σ n 0 {\displaystyle \Sigma _{n}^{0}} の式で定義されることを意味する。言い換えれば、X が Σ n 0 , Y {\displaystyle \Sigma _{n}^{0,Y}} に属するとは、その中でY に属するかどうかの質問が許されている Σ n 0 {\displaystyle \Sigma _{n}^{0}} に属する論理式で定義されることを意味する。 例えば、Y を整数の集合とする。X は、ある Y の元で割り切れる数の集合とする。すると X は式 ϕ ( n ) = ∃ m ∃ t ( Y ( m ) ∧ m × t = n ) {\displaystyle \phi (n)=\exists m\exists t(Y(m)\land m\times t=n)} で定義されるので、X は Σ 1 0 , Y {\displaystyle \Sigma _{1}^{0,Y}} に属することになる（実際には、2つの量化子を n で制限できるので Δ 0 0 , Y {\displaystyle \Delta _{0}^{0,Y}} に属する）。
※この「相対化算術的階層」の解説は、「算術的階層」の解説の一部です。
「相対化算術的階層」を含む「算術的階層」の記事については、「算術的階層」の概要を参照ください。
- 相対化算術的階層のページへのリンク
