数理論理学において、真の算術 () とは一階ペアノ算術の言語における自然数の理論 Th(formula_1) のことである (Boolos, Burgess, and Jeffrey 2002:295)。タルスキの定義不可能性定理はこの理論が算術的に定義不可能であることを示している。ペアノ算術のシグネチャには加法、乗法および後者関数の関数記号、「等しい」と「より小さい」の関係記号、および0の定数記号が含まれる。このシグネチャにおける (整) 論理式は一階述語論理の通常のやり方で構築される。一階述語論理の言語はこのシグネチャにおけるすべての整論理式からなる。 構造 formula_1 はペアノ算術のモデルであり、以下のように定義される:この構造は一階算術の標準モデルもしくは意図した解釈として知られる。一階算術の言語における文は、いま定義した構造において真であるとき formula_1 において真であるという。表記法 formula_7 は、文 φ が formula_1 において真であることを示すために使われる。真の算術は一階算術の言語における文のうち formula_1 において真であるものすべての集合 である。この集合は構造 formula_1 の (完全な) 理論と同値である (を参照)。真の算術での中心的な結果は、アルフレト・タルスキ (1936) の定義不可能性定理である。この定理は集合 が算術的に定義可能でないと述べる。これは一階算術のシグネチャに以下のような「万能論理式」 formula_11 が存在しないという意味である: このシグネチャにおける任意の文 formula_12 に対して、ここで formula_15 は文 "formula_12" の正規ゲーデル数の数字である。ポストの定理は定義不可能性定理のよりシャープなバージョンであり、算術的階層を使って の定義可能性とチューリング次数の間の関係を示す。自然数 "n" ごとに、算術的階層における formula_17 以下の文のみからなる の部分集合を とする。ポストの定理によって、"n" ごとに、 は算術的に定義可能であるが、formula_17 より複雑性が高い論理式によってのみ可能であることが示される。したがって単一の論理式で を定義することはできない。なぜならばだが、いかなる単一の論理式も任意の大きな "n" に対して を定義できないからである。上記で論じたように、タルスキの定理によれば は算術的に定義不可能である。ポストの定理の系によって のチューリング次数は 0 となり、そのため は決定可能でも帰納的可算でもない。真の算術は不安定な理論であり、そのため非可算濃度 formula_20 ごとに formula_21 個のモデルを持つ。この理論は完全なので、そのすべてのモデルは初等的同値である。二階算術の真の理論は二階算術の言語において二階算術の標準モデルによって充足されるすべての文からなる。二階算術の標準モデルはその一階部分が構造 formula_1 であり、その二階部分が formula_3 のすべての部分集合からなる。一階算術の真の理論 は二階算術の真の理論の部分集合であり、 は二階算術で定義可能である。しかし、ポストの定理の解析的階層への一般化により、二階算術の真の理論は二階算術のいかなる単一の論理式によっても定義可能でないことが示される。Simpson (1977) は二階算術の真の理論は、半順序のシグネチャにおいて、すべてのチューリング次数の半順序の理論と計算可能な解釈が可能であり、"その逆も成り立つ"ことを示した。

出典:wikipedia