真の算術

数理論理学において、真の算術とは、自然数の算術に関するすべての真の一階述語の集合である。^{[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 \varphi}$${\displaystyle {\mathcal {N}}.}$

真の算術は、第一階算術の言語で、Th( )と書かれる、において真であるすべての文の集合として定義される。この集合は、構造の（完全な）理論と同義である。^[2]${\displaystyle {\mathcal {N}}}$${\displaystyle {\mathcal {N}}}$${\displaystyle {\mathcal {N}}}$

真の算術に関する中心的な結果は、アルフレッド・タルスキ（1936）の定義不可能定理である。これは、集合Th( )は算術的に定義できないことを述べている。これは、この言語の すべての文θに対して、${\displaystyle {\mathcal {N}}}$${\displaystyle \varphi (x)}$

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

ここで、θという文の標準的なゲーデル数の数値を示します。 ${\displaystyle {\underline {\#(\theta )}}}$

ポストの定理は、算術階層を用いてTh( )${\displaystyle {\mathcal {N}}}$の定義可能性とチューリング次数の関係を示す、定義不可能定理のより明確なバージョンです。各自然数nに対して、Th _n ( ) を算術階層で以下の文のみで構成されるTh( ) の部分集合とします。ポストの定理は、各nに対して、Th _n ( )は算術的に定義可能ですが、 よりも高い複雑度の式によってのみ定義可能であることを示しています。したがって、単一の式でTh( )を定義することはできません。 ${\displaystyle {\mathcal {N}}}$${\displaystyle {\mathcal {N}}}$${\displaystyle \Sigma _{n}^{0}}$${\displaystyle {\mathcal {N}}}$${\displaystyle \Sigma _{n}^{0}}$${\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( )のチューリング次数は0 ^(ω)であることが証明され、したがってTh( ) は決定可能でも再帰的に列挙可能でも ありません。 ${\displaystyle {\mathcal {N}}}$${\displaystyle {\mathcal {N}}}$

Th( ) は、${\displaystyle {\mathcal {N}}}$半順序のシグネチャにおいて、再帰的に列挙可能なチューリング次数の理論Th( )${\displaystyle {\mathcal {R}}}$と密接に関連している。^[3]特に、次のような計算可能な関数SとTが存在する。

• 1階算術のシグネチャ内の各文φについて、 S ( φ ) がTh ( )に含ま れる場合のみ、φは Th( )に含まれる。${\displaystyle {\mathcal {N}}}$${\displaystyle {\mathcal {R}}}$
• 半順序のシグネチャ内の各文ψについて、 T ( ψ ) が Th ( )にある場合のみ、ψはTh( )${\displaystyle {\mathcal {R}}}$にあります 。${\displaystyle {\mathcal {N}}}$

真の算術は不安定な理論であり、したがって各非可算基数に対するモデルも存在します。空集合には連続した多くの型があるため、真の算術にも 可算モデルがあります。理論は完全であるため、そのモデルはすべて基本的に同等です。 ${\displaystyle 2^{\kappa }}$${\displaystyle \kappa }$${\displaystyle 2^{\aleph _{0}}}$

2 階算術の真の理論は、2 階算術の言語で、2 階算術の標準モデルが満たすすべての文で構成されます。2 階算術の標準モデルの 1 階部分は構造で、2 階部分は のすべてのサブセットで構成されます。 ${\displaystyle {\mathcal {N}}}$${\displaystyle \mathbb {N} }$

第一階算術の真の理論Th( )${\displaystyle {\mathcal {N}}}$は第二階算術の真の理論のサブセットであり、Th( ) は${\displaystyle {\mathcal {N}}}$第二階算術で定義可能です。しかし、ポストの定理を解析階層に一般化すると、第二階算術の真の理論は第二階算術の単一の式では定義できないことがわかります。

シンプソン(1977)は、第二階算術の真の理論は、半順序のシグネチャにおいて、すべてのチューリング次数の半順序の理論で計算可能に解釈可能であり、その逆もまた同様であることを示した。

• ブーロス、ジョージ、バージェス、ジョン P.、ジェフリー、リチャード C. (2002)、計算可能性と論理(第 4 版)、ケンブリッジ大学出版局、ISBN 978-0-521-00758-0。
• Bovykin, Andrey; Kaye, Richard (2001)、「算術モデルの順序型について」、Zhang, Yi (編)、『論理と代数』、Contemporary Mathematics、vol. 302、American Mathematical Society、pp. 275–285、ISBN 978-0-8218-2984-4。
• ショア、リチャード(2011)、「再帰的に列挙可能な次数」、グリフォー、ER (編)、計算可能性理論ハンドブック、論理学と数学の基礎研究、第 140 巻、ノースホランド (1999 年出版)、pp. 169–197、ISBN 978-0-444-54701-9。
• シンプソン、スティーブン G. (1977)、「再帰的不解性の度合いの第一階理論」、数学年報、第 2 シリーズ、105 (1)、数学年報: 121–139、doi :10.2307/1971028、ISSN  0003-486X、JSTOR  1971028、MR  0432435
• タルスキ、アルフレッド(1936)、「形式化された言語における真理の概念」。英語訳「形式化された言語における真理の概念」は、コーコラン、J. 編 (1983)、論理、意味論、メタ数学: 1923 年から 1938 年までの論文(第 2 版)、Hackett Publishing Company, Inc.、ISBNに掲載されています。 978-0-915144-75-4

• ワイスタイン、エリック W.「算術」。MathWorld。
• Weisstein、Eric W.「ペアノ算術」。MathWorld。
• Weisstein, Eric W.「タルスキーの定理」。MathWorld。