算術の定義不可能性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/05/28 14:33 UTC 版)
真の算術での中心的な結果は、アルフレト・タルスキ (1936) の定義不可能性定理である。この定理は集合 Th( N {\displaystyle {\mathcal {N}}} ) が算術的に定義可能でないと述べる。これは一階算術のシグネチャに以下のような「万能論理式」 φ ( x ) {\displaystyle \varphi (x)} が存在しないという意味である: このシグネチャにおける任意の文 θ {\displaystyle \theta } に対して、 N ⊨ θ {\displaystyle {\mathcal {N}}\models \theta \qquad } if and only if N ⊨ φ ( # ( θ ) _ ) . {\displaystyle {\mathcal {N}}\models \varphi ({\underline {\#(\theta )}}).} ここで # ( θ ) _ {\displaystyle {\underline {\#(\theta )}}} は文 θ {\displaystyle \theta } の正規ゲーデル数の数字である。 ポストの定理は定義不可能性定理のよりシャープなバージョンであり、算術的階層を使って Th( N {\displaystyle {\mathcal {N}}} ) の定義可能性とチューリング次数の間の関係を示す。自然数 n ごとに、算術的階層における Σ n 0 {\displaystyle \Sigma _{n}^{0}} 以下の文のみからなる Th( N {\displaystyle {\mathcal {N}}} ) の部分集合を Thn( N {\displaystyle {\mathcal {N}}} ) とする。ポストの定理によって、n ごとに、Thn( N {\displaystyle {\mathcal {N}}} ) は算術的に定義可能であるが、 Σ n 0 {\displaystyle \Sigma _{n}^{0}} より複雑性が高い論理式によってのみ可能であることが示される。したがって単一の論理式で Th( N {\displaystyle {\mathcal {N}}} ) を定義することはできない。なぜならば Th ( N ) = ⋃ n ∈ N Th n ( N ) {\displaystyle {\mbox{Th}}({\mathcal {N}})=\bigcup _{n\in \mathbb {N} }{\mbox{Th}}_{n}({\mathcal {N}})} だが、いかなる単一の論理式も任意の大きな n に対して Thn( N {\displaystyle {\mathcal {N}}} ) を定義できないからである。
※この「算術の定義不可能性」の解説は、「真の算術」の解説の一部です。
「算術の定義不可能性」を含む「真の算術」の記事については、「真の算術」の概要を参照ください。
- 算術の定義不可能性のページへのリンク
