真の算術

数理論理学において、真の算術 (英: true arithmetic) とは一階ペアノ算術の(言語)における自然数の(理論) Th(${\displaystyle {\mathcal {N}}}$) のことである^[1]。タルスキの定義不可能性定理はこの理論が算術的に定義不可能であることを示している。

定義

ペアノ算術のシグネチャには加法、乗法および後者関数の関数記号、「等しい」と「より小さい」の関係記号、および0の定数記号が含まれる。このシグネチャにおける論理式は一階述語論理の通常のやり方で構築される。一階述語論理の言語はこのシグネチャにおけるすべての論理式からなる。

(構造) ${\displaystyle {\mathcal {N}}}$  はペアノ算術のモデルであり、以下のように定義される:

• 議論領域は自然数の集合 ${\displaystyle \mathbb {N} }$  である。
• 記号0は数0と解釈される。
• 関数記号は ${\displaystyle \mathbb {N} }$  上での通常の算術演算と解釈される。
• 「等しい」と「より小さい」の関係記号は ${\displaystyle \mathbb {N} }$  上での通常の等値および順序関係と解釈される。

この構造は一階算術の(標準モデル)もしくは(意図した解釈)として知られる。

一階算術の言語における(文)は、いま定義した構造において真であるとき ${\displaystyle {\mathcal {N}}}$  において真であるという。表記法 ${\displaystyle {\mathcal {N}}\models \varphi }$  は、文 φ が ${\displaystyle {\mathcal {N}}}$  において真であることを示すために使われる。

真の算術は一階算術の言語における文のうち ${\displaystyle {\mathcal {N}}}$  において真であるものすべての集合 Th(${\displaystyle {\mathcal {N}}}$ ) である。この集合は構造 ${\displaystyle {\mathcal {N}}}$  の (完全な) 理論と同値である^[2]。

算術の定義不可能性

真の算術での中心的な結果は、アルフレト・タルスキ (1936) の定義不可能性定理である。この定理は集合 Th(${\displaystyle {\mathcal {N}}}$ ) が算術的に定義可能でないと述べる。これは一階算術のシグネチャに以下のような「万能論理式」 ${\displaystyle \varphi (x)}$  が存在しないという意味である: このシグネチャにおける任意の文 ${\displaystyle \theta }$  に対して、

${\displaystyle {\mathcal {N}}\models \theta \qquad }$  if and only if ${\displaystyle {\mathcal {N}}\models \varphi ({\underline {\#(\theta )}}).}$ 

ここで ${\displaystyle {\underline {\#(\theta )}}}$  は文 ${\displaystyle \theta }$  の正規ゲーデル数の数字である。

ポストの定理は定義不可能性定理のよりシャープなバージョンであり、算術的階層を使って Th(${\displaystyle {\mathcal {N}}}$ ) の定義可能性とチューリング次数の間の関係を示す。自然数 n ごとに、算術的階層における ${\displaystyle \Sigma _{n}^{0}}$  以下の文のみからなる Th(${\displaystyle {\mathcal {N}}}$ ) の部分集合を Th_n(${\displaystyle {\mathcal {N}}}$ ) とする。ポストの定理によって、n ごとに、Th_n(${\displaystyle {\mathcal {N}}}$ ) は算術的に定義可能であるが、${\displaystyle \Sigma _{n}^{0}}$  より複雑性が高い論理式によってのみ可能であることが示される。したがって単一の論理式で Th(${\displaystyle {\mathcal {N}}}$ ) を定義することはできない。なぜならば

${\displaystyle {\mbox{Th}}({\mathcal {N}})=\bigcup _{n\in \mathbb {N} }{\mbox{Th}}_{n}({\mathcal {N}})}$ 

だが、いかなる単一の論理式も任意の大きな n に対して Th_n(${\displaystyle {\mathcal {N}}}$ ) を定義できないからである。

計算可能性の性質

上記で論じたように、タルスキの定理によれば Th(${\displaystyle {\mathcal {N}}}$ ) は算術的に定義不可能である。ポストの定理の系によって Th(${\displaystyle {\mathcal {N}}}$ ) のチューリング次数は 0^ω となり、そのため Th(${\displaystyle {\mathcal {N}}}$ ) は決定可能でも帰納的可算でもない。

Th(${\displaystyle {\mathcal {N}}}$ ) は半順序のシグネチャにおいて、帰納的可算チューリング次数の理論 Th(${\displaystyle {\mathcal {R}}}$ ) と密接な関係がある^[3]。とくに、以下のような S および T が存在する:

• 一階算術のシグネチャにおけるそれぞれの文 φ について、S(φ) が Th(${\displaystyle {\mathcal {R}}}$ ) に属するとき、かつそのときに限り φ は Th(${\displaystyle {\mathcal {N}}}$ ) に属する。
• 半順序のシグネチャにおけるそれぞれの文 ψ について、T(ψ) が Th(${\displaystyle {\mathcal {N}}}$ ) に属するとき、かつそのときに限り ψ は Th(${\displaystyle {\mathcal {R}}}$ ) に属する。

モデル理論的性質

真の算術は(不安定な理論)であり、そのため非可算濃度 ${\displaystyle \kappa }$  ごとに ${\displaystyle 2^{\kappa }}$  個のモデルを持つ。この理論は(完全)なので、そのすべてのモデルは(初等的同値)である。

二階算術の真の理論

二階算術の真の理論は(二階算術)の言語において二階算術の標準モデルによって充足されるすべての文からなる。二階算術の標準モデルはその一階部分が構造 ${\displaystyle {\mathcal {N}}}$  であり、その二階部分が ${\displaystyle \mathbb {N} }$  のすべての部分集合からなる。

一階算術の真の理論 Th(${\displaystyle {\mathcal {N}}}$ ) は二階算術の真の理論の部分集合であり、Th(${\displaystyle {\mathcal {N}}}$ ) は二階算術で定義可能である。しかし、ポストの定理の(解析的階層)への一般化により、二階算術の真の理論は二階算術のいかなる単一の論理式によっても定義可能でないことが示される。

Simpson (1977) は二階算術の真の理論は、半順序のシグネチャにおいて、すべてのチューリング次数の半順序の理論と計算可能な解釈が可能であり、その逆も成り立つことを示した。

脚注

[脚注の使い方]

1. ^ Boolos, Burgess & Jeffrey 2002, p. 295
2. ^ theories associated with a structureを参照。
3. ^ Shore 2011, p. 184

参考文献

• Boolos, George; Burgess, John P.; Jeffrey, Richard C. (2002), Computability and logic (4th ed.), Cambridge University Press, ISBN (978-0-521-00758-0) .
• Bovykin, Andrey; Kaye, Richard (2001), “On order-types of models of arithmetic”, in Zhang, Yi, Logic and algebra, Contemporary Mathematics, 302, American Mathematical Society, pp. 275–285, ISBN (978-0-8218-2984-4) .
• Shore, Richard (2011), “The recursively enumerable degrees”, in Griffor, Edward R., Handbook of Computability Theory, Studies in Logic and the Foundations of Mathematics, 140, North-Holland, 1999, pp. 169–197, ISBN (978-0-444-54701-9) .
• Simpson, Stephen G. (1977), “First-order theory of the degrees of recursive unsolvability”, Annals of Mathematics. Second Series (Annals of Mathematics) 105 (1): 121–139, doi:10.2307/1971028, ISSN 0003-486X, MR0432435, http://jstor.org/stable/1971028 
• Tarksi, Alfred (1936), "Der Wahrheitsbegriff in den formalisierten Sprachen". An English translation "The Concept of Truth in Formalized Languages" appears in Corcoran, J., ed. (1983), Logic, Semantics and Metamathematics: Papers from 1923 to 1938 (2nd ed.), Hackett Publishing Company, Inc., ISBN (978-0-915144-75-4) 

外部リンク

• Weisstein, Eric W. "Arithmetic". MathWorld (英語).
• Weisstein, Eric W. "Peano Arithmetic". MathWorld (英語).
• Weisstein, Eric W. "Tarski's Theorem". MathWorld (英語).