計算可能性の性質
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/05/28 14:33 UTC 版)
上記で論じたように、タルスキの定理によれば Th( N {\displaystyle {\mathcal {N}}} ) は算術的に定義不可能である。ポストの定理の系によって Th( N {\displaystyle {\mathcal {N}}} ) のチューリング次数は 0ω となり、そのため Th( N {\displaystyle {\mathcal {N}}} ) は決定可能でも帰納的可算でもない。 Th( N {\displaystyle {\mathcal {N}}} ) は半順序のシグネチャにおいて、帰納的可算チューリング次数の理論 Th( R {\displaystyle {\mathcal {R}}} ) と密接な関係がある。とくに、以下のような S および T が存在する: 一階算術のシグネチャにおけるそれぞれの文 φ について、S(φ) が Th( R {\displaystyle {\mathcal {R}}} ) に属するとき、かつそのときに限り φ は Th( N {\displaystyle {\mathcal {N}}} ) に属する。 半順序のシグネチャにおけるそれぞれの文 ψ について、T(ψ) が Th( N {\displaystyle {\mathcal {N}}} ) に属するとき、かつそのときに限り ψ は Th( R {\displaystyle {\mathcal {R}}} ) に属する。
※この「計算可能性の性質」の解説は、「真の算術」の解説の一部です。
「計算可能性の性質」を含む「真の算術」の記事については、「真の算術」の概要を参照ください。
- 計算可能性の性質のページへのリンク
