ペアノの公理

数理論理学において、ペアノの公理（/ p i ˈ ɑː n oʊ /、^[1] [peˈaːno] ）は、デデキント-ペアノ公理あるいはペアノ公準とも呼ばれ、19世紀イタリアの数学者ジュゼッペ・ペアノが提唱した自然数の公理である。これらの公理は、数論が無矛盾かつ完全であるかどうかという基本的な問題の研究を含む、多くのメタ数学的研究でほとんど変更されることなく使用されてきた。

ペアノ公理によって提供される算術の公理化は、一般にペアノ算術と呼ばれます。

算術を形式化することの重要性は、1860年代にヘルマン・グラスマンの研究が行われるまであまり認識されていませんでした。グラスマンは、算術における多くの事実は、後続演算と帰納法に関するより基本的な事実から導き出せることを示しました。 ^[2]^[3] 1881年、チャールズ・サンダース・パースは、自然数算術の公理化を提供しました。^[4]^[5] 1888年、リチャード・デデキントは、自然数算術の別の公理化を提案し、1889年、ペアノは、その簡略化されたバージョンを公理集として、著書『新しい方法による算術の原理』（ラテン語：Arithmetices principia, nova methodo exposita）で出版しました。

9 つのペアノ公理には、3 種類のステートメントが含まれています。最初の公理は、自然数の集合に少なくとも 1 つのメンバーが存在することを主張します。次の 4 つは、等式に関する一般的なステートメントです。現代の扱いでは、これらはペアノ公理の一部としてではなく、「基礎となる論理」の公理として扱われることがよくあります。^[6]次の 3 つの公理は、自然数に関する1 階のステートメントであり、後続の演算の基本特性を表現しています。9 番目の最後の公理は、自然数に対する数学的帰納法の原理の2 階のステートメントであり、この定式化は2 階算術に近くなります。より弱い 1 階のシステムは、加算と乗算の演算記号を明示的に追加し、2 階帰納法の公理を 1 階の公理スキーマに置き換えることによって得られます。ペアノ算術という用語は、この制限されたシステムを具体的に指定するために使用されることがあります。

歴史的な二次定式化

ペアノが公理を定式化した当時、数理論理学の言語はまだ初期段階にあった。公理を表現するために彼が考案した論理記法は普及しなかったが、集合の帰属を表す現代の記法（ペアノのεに由来する∈）の起源となった。ペアノは数学記号と論理記号を明確に区別していたが、これは数学ではまだ一般的ではなかった。このような区別は、1879年にゴットロープ・フレーゲが出版した『 Begriffsschrift』^{で初めて導入された。 [7]ペアノはフレーゲの研究を知らず、}ブールとシュレーダーの研究に基づいて独自に論理装置を作り直した。^[8]

ペアノの公理は、自然数の算術的性質を定義し、通常は集合 Nまたはとして表されます。公理の非論理記号は、定数記号 0 と単項関数記号Sで構成されます。 $\mathbb {N} .$

最初の公理は、定数 0 は自然数であると述べています。

0は自然数です。

ペアノの公理の元々の定式化では、「最初の」自然数として0ではなく1が使用されていましたが^[9]、Formulario mathematicoの公理にはゼロが含まれています。^[10]

次の4つの公理は等式関係を記述する。これらは等式を伴う一階述語論理において論理的に有効であるため、現代の扱いでは「ペアノ公理」の一部とはみなされない。^[8]

すべての自然数xに対して、x = xです。つまり、等式は反射的です。
すべての自然数xとyについて、x = yであれば、y = xです。つまり、等式は対称的です。
すべての自然数x、y、zについて、x = yかつy = zであれば、x = zです。つまり、等式は推移的です。
すべてのaとbについて、b が自然数でa = bであれば、aも自然数です。つまり、自然数は等式に関して閉じています。

残りの公理は、自然数の算術的性質を定義します。自然数は、単一値の「後続」関数 Sの下で閉じていると仮定されます。

任意の自然数nに対して、S ( n ) は自然数です。つまり、自然数はSに関して閉じています。
すべての自然数mとnに対して、S ( m ) = S ( n )ならば、m = nです。つまり、S は単射です。
すべての自然数nに対して、S ( n ) = 0は偽です。つまり、次の数が 0 である自然数は存在しません。

公理 1、6、7、8 は、自然数の直感的な概念の単項表現を定義します。つまり、数 1 はS (0)、2 はS ( S (0)) などと定義できます。ただし、自然数の概念がこれらの公理によって定義されていることを考慮すると、公理 1、6、7、8 は、後続関数が 0 以外のすべての自然数を生成することを意味しません。

各自然数は、後続数をゼロに十分な回数適用することによって得られるという直感的な概念には、帰納法の公理と呼ばれる追加の公理が必要です。

K が次のような集合である場合:
- 0はKにあり、
- 任意の自然数nに対して、nがKに属するということはS ( n )がKに属するということである。
すると、Kにはすべての自然数が含まれます。

帰納法の公理は、次の形式で表現されることもあります。

φが次のような単項述語である場合:
- φ (0) は真であり、
- あらゆる自然数nに対して、φ ( n ) が真であるということは、φ ( S ( n ) ) が真であることを意味する。
φ ( n ) はすべての自然数nに対して真である。

ペアノの元の定式化では、帰納法の公理は2階の公理である。現在では、この2階の原理をより弱い1階の帰納法のスキームに置き換えるのが一般的である。2階の定式化と1階の定式化には重要な違いがあり、これについては以下のセクション「1階理論としてのペアノ算術」で説明する。

算術演算と関係の定義

2階帰納法の公理を使用すると、公理を使用してN上の加算、乗算、および全（線形）順序を直接定義できます。ただし、 1階帰納法ではこれは不可能であり^[^要出典^{] 、加算と乗算は公理として追加されることがよくあります。それぞれの関数と関係は}集合論または2階論理で構築され、ペアノ公理を使用して一意であることが示されます。

追加

加算は、 2 つの自然数 ( Nの 2 つの要素) を別の自然数にマッピングする関数です。これは再帰的に次のように定義されます。

{\begin{aligned}a+0&=a,&{\textrm {(1)}}\\a+S(b)&=S(a+b).&{\textrm {(2)}}\end{aligned}}

例えば：

{\begin{aligned}a+1&=a+S(0)&{\mbox{定義により}}\\&=S(a+0)&{\mbox{使用 (2)}}\\&=S(a),&{\mbox{使用 (1)}}\\\\a+2&=a+S(1)&{\mbox{定義により}}\\&=S(a+1)&{\mbox{使用 (2)}}\\&=S(S(a))&{\mbox{使用 }}a+1=S(a)\\\\a+3&=a+S(2)&{\mbox{定義により}}\\&=S(a+2)&{\mbox{使用 (2)}}\\&=S(S(S(a)))&{\mbox{使用 }}a+2=S(S(a))\\{\text{など}}&\\\end{aligned}}

加法の可換性を証明するには、まずとをそれぞれについて帰納的に証明します。両方の結果を使用して、について帰納的に証明します。構造( N、 +)は単位元 0 を持つ可換モノイドです。また、( N、 +)は相殺マグマであるため、グループに埋め込むことができます。 N を埋め込む最小のグループは整数です。^[^要出典^] $0+b=b$ $S(a)+b=S(a+b)$ $b$ $a+b=b+a$ $b$

乗算

同様に、乗算は2 つの自然数を別の自然数にマッピングする関数です。加算を考えると、乗算は次のように再帰的に定義されます。

{\begin{aligned}a\cdot 0&=0,\\a\cdot S(b)&=a+(a\cdot b).\end{aligned}}

が乗法的正則であることは容易に分かります。 $S(0)$

a\cdot S(0)=a+(a\cdot 0)=a+0=a

が乗法左単位元でもあることを示すには、乗法の定義方法による帰納公理が必要です。 $S(0)$

$S(0)$ 0: の左恒等式です。 $S(0)\cdot 0=0$
がの左単位元(つまり)である場合、加法の可換性を用いると、は:の左単位元でもあります。 $S(0)$ $a$ $S(0)\cdot a=a$ $S(0)$ $S(a)$ $S(0)\cdot S(a)=S(0)+S(0)\cdot a=S(0)+a=a+S(0)=S(a+0)=S(a)$

したがって、帰納的公理により、はすべての自然数の乗法左単位元である。さらに、乗算は可換であり、加算に対して分配されることが示される^[14]。 $S(0)$

a\cdot (b+c)=(a\cdot b)+(a\cdot c)

。

したがって、は可換半環です。 $(\mathbb {N} ,+,0,\cdot ,S(0))$

不平等

自然数に対する通常の全順序関係 ≤ は、0 が自然数であると仮定して次のように定義できます。

すべてのa、b ∈ Nについて、a + c = bとなるc ∈ Nが存在する場合のみ、a ≤ bとなります。

この関係は加算と乗算に対して安定です。に対して、a ≤ bであれば、次のようになります。 $a,b,c\in \mathbb {N}$

a + c ≤ b + cであり、
a · c ≤ b · c。

したがって、構造( N , +, ·, 1, 0, ≤)は順序付き半環です。0 と 1 の間に自然数は存在しないため、離散的な順序付き半環です。

帰納法の公理は、順序関係「≤」を利用して、より強い仮説を使用する次の形式で表現されることがあります。

任意の述語 φに対して、

φ (0) は真であり、
任意のn ∈ Nに対して、k ≤ nとなる任意のk ∈ Nに対してφ ( k ) が真であれば、φ ( S ( n )) は真であり、
すると、すべてのn∈Nに対してφ ( n )は真となる。

この形式の帰納法公理は強い帰納法と呼ばれ、標準的な定式化の結果ですが、≤ 順序についての推論に適していることがよくあります。たとえば、自然数が整然としている( Nのすべての空でない部分集合には最小元がある) ことを示すには、次のように推論します。空でないX ⊆ Nが与えられ、Xには最小元がないものとします。

0 はNの最小の要素なので、 0 ∉ Xでなければなりません。
任意のn ∈ Nについて、すべてのk ≤ nに対してk ∉ Xと仮定します。するとS ( n ) ∉ Xとなり、そうでなければXの最小の要素になります。

したがって、強い帰納原理により、すべてのn ∈ Nに対して、n ∉ X です。したがって、X ∩ N = ∅であり、これはX がNの空でない部分集合であることと矛盾します。したがって、X には最小元があります。

モデル

ペアノ公理のモデルは、三つ組( N , 0, S )である。ここで、Nは (必然的に無限の) 集合、0 ∈ Nであり、S : N → N は上記の公理を満たす。デデキントは、1888 年の著書「数の性質と意味」 (ドイツ語: Was sind und was sollen die Zahlen?、つまり「数とは何か、そして数は何の役に立つのか?」) で、ペアノ公理の任意の 2 つのモデル (2 階帰納法公理を含む) は同型であることを証明した。特に、ペアノ公理の 2 つのモデル( N _A、 0 _A、S _A )と( N _B、 0 _B、S _B )が与えられた場合、次を満たす唯一の準同型写像 f : N _A → N _{Bが存在する。}

{\begin{aligned}f(0_{A})&=0_{B}\\f(S_{A}(n))&=S_{B}(f(n))\end{aligned}}

そしてそれは一対一です。これは、2 階のペアノ公理がカテゴリカルであることを意味します。(これは、以下のペアノ公理の 1 階の再定式化には当てはまりません。)

集合論モデル

ペアノの公理は、自然数の集合論的構成やZFなどの集合論の公理から導くことができる。^[15]ジョン・フォン・ノイマンによる自然数の標準的な構成は、 0を空集合∅として定義し、次のように定義される集合上の演算子sから始まる。

s(a)=a\cup \{a\}

自然数Nの集合は、空集合を含むsに関して閉じたすべての集合の共通部分として定義されます。各自然数は、それより小さい自然数の集合と (集合として) 等しくなります。

{\begin{aligned}0&=\emptyset \\1&=s(0)=s(\emptyset )=\emptyset \cup \{\emptyset \}=\{\emptyset \}=\{0\}\\2&=s(1)=s(\{0\})=\{0\}\cup \{\{0\}\}=\{0,\{0\}\}=\{0,1\}\\3&=s(2)=s(\{0,1\})=\{0,1\}\cup \{\{0,1\}\}=\{0,1,\{0,1\}\}=\{0,1,2\}\end{aligned}}

以下同様。集合Nと 0 および後続関数 s : N → N はペアノの公理を満たします。

ペアノ算術は、集合論のいくつかの弱い体系と等価である。 ^[16]そのような体系の1つは、無限公理をその否定に置き換えたZFCである。別のそのような体系は、一般集合論（外延性、空集合の存在、および随伴公理）で構成され、空集合に成立し、随伴に成立する性質が随伴に成立するときは常に随伴にも成立するという公理スキーマによって拡張されている。

圏論における解釈

ペアノの公理は圏論を使って理解することもできます。C を終端オブジェクト1 _Cを持つ圏とし、尖端単項系の圏US ₁ ( C ) を次のように定義します。

_{US 1} ( C )のオブジェクトは三つ組( X、 0 _X、S _X )です。ここで、X はCのオブジェクトであり、0 _X : 1 _C → XとS _X : X → XはC射です。
射φ : ( X , 0 _X , S _X ) → ( Y , 0 _Y , S _Y ) は、φ 0 _X = 0 _Yかつφ S _X = S _Y φを満たすC射φ : X → Yである。

このとき、 US ₁ ( C ) が初期オブジェクトを持つ場合、C はデデキント-ペアノ公理を満たすという。この初期オブジェクトはCの自然数オブジェクトとして知られている。( N , 0, S )がこの初期オブジェクトであり、( X , 0 _X , S _X )が他の任意のオブジェクトである場合、一意の写像u : ( N , 0, S ) → ( X , 0 _X , S _X )は次のようになる。

{\begin{aligned}u(0)&=0_{X},\\u(Sx)&=S_{X}(ux).\end{aligned}}

_{これはまさに 0 X}とS _Xの再帰的な定義です。

一貫性

ペアノ公理が最初に提案されたとき、バートランド・ラッセルらは、これらの公理が「自然数」の意味を暗黙的に定義していることに同意した。^[17] アンリ・ポアンカレはより慎重で、これらの公理は自然数が矛盾しない場合にのみ自然数を定義すると述べた。これらの公理のみから始めて 0 = 1 などの矛盾を導く証明がある場合、公理は矛盾しており、何も定義していない。^[18] 1900 年、デイヴィッド・ヒルベルトは、有限論的方法のみを使用してこれらの一貫性を証明する問題を、 23 の問題の2 番目として提起した。^[19] 1931 年、クルト・ゲーデルは、ペアノ算術が矛盾しない場合、そのような一貫性の証明はペアノ算術自体では形式化できないことを示す第 2 の不完全性定理を証明した。 ^[20]

ゲーデルの定理はペアノ算術の有限無矛盾性証明の可能性を排除すると広く主張されているが、これは有限無矛盾性証明が正確に何を意味するかに依存する。ゲーデル自身、ペアノ算術では形式化できない有限方法を使用することで、ペアノ算術またはより強いシステムの有限無矛盾性証明を与える可能性を指摘し、1958年にゲーデルは型理論を使用して算術の無矛盾性を証明する方法を発表しました。^[21] 1936年に、ゲルハルト・ゲンツェンは、ε ₀と呼ばれる順序数までの超限帰納法を使用して、ペアノの公理の無矛盾性を証明しました。^[22]ゲンツェンは次のように説明しています。「本論文の目的は、初等数論の無矛盾性を証明すること、またはむしろ、無矛盾性の問題を特定の基本原理に還元することです。」ゲンツェンの証明は有限主義的であると言える。なぜなら、超限順序数 ε _{0 は}有限オブジェクト（例えば、整数上の適切な順序を記述するチューリングマシンとして、またはより抽象的には、適切に線形に順序付けられた有限木で構成される）で符号化できるからである。ゲンツェンの証明がヒルベルトが想定した要件を満たしているかどうかは不明である。有限主義的証明が正確に何を意味するのかという一般に受け入れられている定義はなく、ヒルベルト自身も正確な定義を与えたことはない。

現代の数学者の大多数は、直感かゲンツェンの証明のような一貫性の証明の受け入れに頼って、ペアノの公理が一貫していると信じている。少数の哲学者と数学者（その中には超有限主義も主張する者もいる）は、公理を受け入れることは自然数の無限の集合を受け入れることと同じであるとして、ペアノの公理を拒否している。特に、加算（後続関数を含む）と乗算は完全であると想定されている。興味深いことに、ペアノの公理に似ているが、加算と乗算の代わりに減算と除算を持つ自己検証理論があり、加算と乗算の全体に対応する文の証明を避けるような方法で公理化されているが、それでもペアノの公理の真定理をすべて証明することができ、さらに、それ自身の一貫性を証明する（ヒルベルトスタイルの「0=1」の証明が存在しないと述べられる）一貫した理論に拡張することができる。^[23] $\Pi _{1}$

第一階理論としてのペアノ算術

第 9 公理 (帰納公理) を除くすべてのペアノ公理は、一階論理のステートメントです。^[24]加算と乗算の算術演算と順序関係も、一階公理を使用して定義できます。上記の帰納公理は、述語 (つまり、自然数ではなく自然数の集合)を量化するため、二階です。代わりに、帰納の一階公理スキーマを検討することもできます。このようなスキーマには、ペアノ算術の第一階言語で定義可能な述語ごとに 1 つの公理が含まれるため、二階公理よりも弱くなります。^[25]これが弱い理由は、第一階言語の述語の数は可算であるのに対し、自然数の集合の数は不可算であるためです。したがって、第一階言語で記述できない集合が存在します (実際、ほとんどの集合がこの特性を持っています)。

ペアノ算術の 1 階の公理化には、別の技術的な制限があります。2 階論理では、後続の演算から加算と乗算の演算を定義することができますが、1 階論理のより制限的な設定ではこれを行うことはできません。したがって、加算と乗算の演算はペアノ算術のシグネチャに直接含まれ、3 つの演算を相互に関連付ける公理が含まれます。

この目的には、ロビンソン算術の7つの公理のうち6つを含む次の公理のリスト（通常の等式公理とともに）で十分である：^[26]

$\forall x\ (0\neq S(x))$
$\forall x,y\ (S(x)=S(y)\Rightarrow x=y)$
$\forall x\ (x+0=x)$
$\forall x,y\ (x+S(y)=S(x+y))$
$\forall x\ (x\cdot 0=0)$
$\forall x,y\ (x\cdot S(y)=x\cdot y+x)$

ペアノ算術には、この数値公理のリストに加えて、再帰的に列挙可能で決定可能な公理の集合からなる帰納法図式が含まれている。ペアノ算術の言語における各式φ ( x , y ₁ , ..., y _k )について、 φの1階帰納法公理は次の文である。

\forall {\bar {y}}{\Bigg (}{\bigg (}\varphi (0,{\bar {y}})\land \forall x{\Big (}\varphi (x,{\bar {y}})\Rightarrow \varphi (S(x),{\bar {y}}){\Big )}{\bigg )}\Rightarrow \forall x\varphi (x,{\bar {y}}){\Bigg )}

ここで、はy ₁、...、y _kの略語です。 1 階帰納法スキーマには、1 階帰納法公理のすべてのインスタンスが含まれます。つまり、すべての式φに対する帰納法公理が含まれます。 ${\bar {y}}$

同等の公理化

ペアノ算術の上記の公理化では、ゼロと後続演算、加算、乗算演算の記号のみを持つシグネチャを使用しています。他にも多くの異なるが同等の公理化があります。そのような代替案の1つ^{[27]では、後続演算の代わりに順序関係記号と}離散的に順序付けられた半環の言語を使用しています（半環の公理1-7、順序の公理8-10、互換性に関する公理11-13、離散性の公理14-15）。

$\forall x,y,z\ ((x+y)+z=x+(y+z))$ つまり、加算は結合的です。
$\forall x,y\ (x+y=y+x)$ つまり、加算は可換である。
$\forall x,y,z\ ((x\cdot y)\cdot z=x\cdot (y\cdot z))$ つまり、乗算は結合的です。
$\forall x,y\ (x\cdot y=y\cdot x)$ つまり、乗算は可換である。
$\forall x,y,z\ (x\cdot (y+z)=(x\cdot y)+(x\cdot z))$ つまり、乗算は加算に対して分配されます。
$\forall x\ (x+0=x\land x\cdot 0=0)$ つまり、ゼロは加算の単位元であり、乗算の吸収元（実際には不要^[注3]）である。
$\forall x\ (x\cdot 1=x)$ つまり、1 は乗算の恒等式です。
$\forall x,y,z\ (x<y\land y<z\Rightarrow x<z)$ つまり、「<」演算子は推移的です。
$\forall x\ (\neg (x<x))$ つまり、「<」演算子は非反射的です。
$\forall x,y\ (x<y\lor x=y\lor y<x)$ つまり、順序付けは三分法を満たします。
$\forall x,y,z\ (x<y\Rightarrow x+z<y+z)$ つまり、同じ要素を追加しても順序は保持されます。
$\forall x,y,z\ (0<z\land x<y\Rightarrow x\cdot z<y\cdot z)$ つまり、同じ正の要素による乗算でも順序は保持されます。
$\forall x,y\ (x<y\Rightarrow \exists z\ (x+z=y))$ つまり、任意の 2 つの異なる要素が与えられた場合、大きい方の要素は小さい方の要素に別の要素を加えたものになります。
$0<1\land \forall x\ (x>0\Rightarrow x\geq 1)$ つまり、0 と 1 は別個であり、その間に要素はありません。言い換えると、0 は1 で覆われており、これらの数は離散的であることを示しています。
$\forall x\ (x\geq 0)$ つまり、ゼロは最小の要素です。

これらの公理によって定義される理論はPA ⁻として知られています。この理論も不完全であり、重要な特性の 1 つは、この理論を満たす任意の構造がと同型な初期セグメント ( によって順序付けられる) を持つことです。このセグメント内の要素は標準要素と呼ばれ、他の要素は非標準要素と呼ばれます。 $M$ $\leq$ $\mathbb {N}$

最後に、 1 階帰納法スキーマを追加することで、ペアノ算術PAが得られます。

決定不能性と不完全性

ゲーデルの不完全性定理によれば、 PAの理論は(矛盾がなければ) 不完全です。その結果、PAの標準モデルでは真であるが FOL 公理化の結果ではない一階述語論理(FOL) の文が存在します。ロビンソン算術などのより弱い公理を持つ理論では、本質的な不完全性がすでに生じています。

上記の不完全性の結果（ FOL に対するゲーデルの完全性定理による）と密接に関連して、与えられたFOL 文がペアノ算術の第一階公理化の結果であるかどうかを決定するアルゴリズムは存在しないということになります。したがって、 PA は決定不能理論の例です。ヒルベルトの第 10 問題に対する否定的な答えにより、PAの存在文に対してすでに決定不能性が生じています。この証明は、計算可能列挙可能なすべての集合がディオファントス集合であり、したがってPAの存在量化された式（自由変数を含む）によって定義可能であることを意味します。存在式よりも量指定子のランクが高い（量指定子の交替が多い） PAの式は表現力が豊かであり、算術階層の上位レベルの集合を定義します。

非標準モデル

通常の自然数はPAの公理を満たしますが、他のモデル（「非標準モデル」と呼ばれる）も存在します。コンパクト性定理は、非標準要素の存在が一階述語論理で排除できないことを意味します。^[28]上向きレーヴェンハイム-スコーレム定理は、すべての無限基数のPAの非標準モデルが存在することを示しています。これは、同型性を除いて1つのモデルしかない元の（2階）ペアノ公理には当てはまりません。^[29]これは、1階システムPAが2階ペアノ公理よりも弱い理由の1つを示しています。

ZFCなどの一階集合論内での証明として解釈される場合、PA に対するデデキントの圏論的証明は、集合論の各モデルが、同型性を除いてペアノ公理の一意のモデルを持ち、その集合論のモデル内に含まれる他のすべての PA モデルの初期セグメントとして埋め込まれることを示します。集合論の標準モデルでは、この PA の最小モデルが PA の標準モデルです。ただし、集合論の非標準モデルでは、PA の非標準モデルである可能性があります。この状況は、集合論のどの一階形式化でも避けることはできません。

可算な非標準モデルを明示的に構築できるかどうかを尋ねるのは自然なことです。答えはイエスです。1933年にSkolem がそのような非標準モデルの明示的な構築を提供したからです。一方、 1959 年に証明されたTennenbaum の定理は、加算または乗算のいずれかの演算が計算可能なPA の可算な非標準モデルは存在しないことを示しています。^[30]この結果は、PA の可算な非標準モデルの加算と乗算の演算を完全に明示的に記述することが難しいことを示しています。可算な非標準モデルの可能な順序型は 1 つだけです。ωを自然数の順序型、ζ を整数の順序型、η を有理数の順序型とすると、PA の任意の可算な非標準モデルの順序型はω + ζ · ηであり、これは自然数のコピーと、それに続く整数のコピーの稠密な線形順序として視覚化できます。

溢れ出る

非標準モデルMのカットとは、 Mの空でない部分集合Cであり、Cは下向きに閉じており ( x < yかつy ∈ C ⇒ x ∈ C )、C は後続に関して閉じている。適切なカットとは、 Mの適切な部分集合であるカットである。各非標準モデルには、標準的な自然数に対応するものを含め、多くの適切なカットがある。しかし、ペアノ算術の帰納法では、適切なカットを定義できない。アブラハム・ロビンソンによって最初に証明されたオーバースピル補題は、この事実を形式化している。

オーバースピル補題^[31] — M をPA の非標準モデルとし、 C をMの適切なカットとする。はMの要素の組であり、は算術言語の式であり、 ${\bar {a}}$ $\phi (x,{\bar {a}})$

M\vDash \phi (b,{\bar {a}})

すべてのb ∈ Cに対して。

すると、 MにはCのどの要素よりも大きいcが存在し、

M\vDash \phi (c,{\bar {a}}).

参照

注記

^ 0に対応する最も近いライトピースと、後続に対応する隣接ピース
^ 非連続集合は、0 要素を持つため公理 1 を満たし、2 ～ 5 は等式関係に影響を与えないため公理 6 と 8 を満たし、0 要素を除くすべてのピースに後続のピースがあるため公理 7 を満たし、2 つのドミノが同じピースによって倒れたり倒れたりすることはないため公理 7 を満たします。
^ " " は、他の公理 (一階述語論理) から次のように証明できます。まず、分配法則と加法的な恒等式によって。次に、公理 15 によって。の場合、同じ要素の加算と可換性により、つまり置換により、反射性と矛盾します。したがって、でなければなりません。 $\forall x\ (x\cdot 0=0)$ $x\cdot 0+x\cdot 0=x\cdot (0+0)=x\cdot 0=x\cdot 0+0$ $x\cdot 0=0\lor x\cdot 0>0$ $x\cdot 0>0$ $x\cdot 0+x\cdot 0>x\cdot 0+0$ $x\cdot 0+0>x\cdot 0+0$ $x\cdot 0=0$

参考文献

引用

^ 「ペアノ」。ランダムハウス・ウェブスター大辞典。
^ グラスマン 1861年。
^ Wang 1957、pp. 145、147、「ペアノ自身が認めているように、ペアノはグラスマンの研究を公理の発展に大いに活用した。グラスマンが本質的に、すべての整数の集合を、正の要素の各集合が最小の要素を持つ整列した整域を形成するという特徴付けをしたことは、あまり知られていない。[グラスマンの本]は、数を多かれ少なかれ公理的な基盤に置こうとした最初の真剣でかなり成功した試みだっただろう。」
^ ピアース 1881年。
^ シールド 1997.
^ ヴァン・ヘイジェノールト1967年、94ページ。
^ ヴァン・ヘイジェノールト 1967年、2ページ。
^ ab Van Heijenoort 1967、p. 83.
^ ペアノ 1889年、1ページ。
^ ペアノ1908年、27ページ。
^ マット・デヴォス、数学的帰納法、サイモンフレーザー大学
^ ジェラルド・コン・ディアス、数学的帰納法、2013年5月2日アーカイブ、ハーバード大学、Wayback Machine
^ Meseguer & Goguen 1986、セクション 2.3 (p. 464) および 4.1 (p. 471)。
^ 正式な証明については、例えばFile:Inductive proofs of properties of add, mult from recursive definitions.pdfを参照してください。
^ サップス 1960、ハッチャー 2014
^ Tarski & Givant 1987、セクション 7.6。
^ Fritz 1952、p. 137
「解釈」の実例として、ラッセル自身の「基数」の定義が挙げられます。この場合の解釈されない体系とは、数体系に関するペアノの公理であり、その 3 つの基本的な考え方と 5 つの公理があれば、自然数体系のすべての特性を導き出すのに十分であるとペアノは信じていました。実際、ラッセルは、ペアノの公理は、自然数の級数がその一例である形式のあらゆる数列を定義していると主張しています。 $x_{0},x_{1},x_{2},\ldots ,x_{n},\ldots$
^ Gray 2013, p. 133
そこでポアンカレは、論理主義が算術、より正確には順序数の算術を生み出すことができるかどうかを調べることにした。クーチュラは、ポアンカレはペアノの公理を数の定義として受け入れたと述べた。しかし、これではだめだ。公理は、例を見つけることで矛盾がないことを示すことはできないし、その含意の全体を調べることで矛盾がないことを示す試みには、クーチュラがそれらが含意すると信じていた数学的帰納法の原理そのものが必要になるだろう。なぜなら、（S&Mから削除されたさらなる一節によれば）原理を証明するために原理を仮定することは、それが真であれば自己矛盾ではないことを証明するだけであり、それでは何も言えないからである。あるいは、述べられた形式とは別の形式で原理を使用した場合、推論のステップ数が新しい定義に従って整数であることを示す必要があるが、これはできなかった (1905c、834)。
^ ヒルベルト 1902.
^ ゲーデル 1931.
^ ゲーデル 1958
^ ゲンツェン 1936
^ ウィラード 2001.
^ Partee、Ter Meulen & Wall 2012、215ページ。
^ ハルサニ（1983年）。
^ メンデルソン 1997、155ページ。
^ ケイ1991、16-18頁。
^ヘルメス 1973、VI.4.3、 ソラルフ・スコレムの定理を提示
^ ヘルメス1973、VI.3.1。
^ Kaye 1991、セクション11.3。
^ Kaye 1991、70ページ以降。

出典

デイビス、マーティン(1974)。計算可能性。バリー・ジェイコブスによる注釈。ニューヨーク大学クーラント数学研究所。

リチャード・デデキント（1888年）。シンドとソレンはザーレンでしたか？ [数字とは何ですか?また、数字は何でなければなりませんか? ] (PDF)。ビューeg 。2016 年7 月 4 日に取得。
- 英語訳2つ:
  - Beman、Wooster、Woodruff (1901)。数論に関するエッセイ(PDF)。Dover Publications。{{cite book}}: CS1 maint: multiple names: authors list (link)
  - エワルド、ウィリアム B. (1996)。カントからヒルベルトまで:数学の基礎の参考書。オックスフォード大学出版局。pp. 787–832。ISBN 978-0-19-853271-2。

フリッツ、チャールズ A. ジュニア (1952)。バートランドラッセルの外部世界構築。ニューヨーク、ヒューマニティーズプレス。

ゲンツェン、ゲルハルト(1936)。「Die Widerspruchsfreiheit der Reinen Zahlentheorie」。数学アンナレン。１１２．彼の 1969 年の作品集、ME Szabo 編: 132–213に英語翻訳で再版されています。土井：10.1007/bf01565428。S2CID 122719892。

ゲーデル、クルト(1931)。「正式な数学と教育システム、I」(PDF)。数学のためのモナトシェフ。３８．英語翻訳の詳細については、「プリンキピアマセマティカの形式的に決定不可能な命題と関連システムについて」を参照してください。: 173–198。土井：10.1007/bf01700692。S2CID 197663120。2018年 4 月 11 日のオリジナル(PDF)からアーカイブ。2013 年 10 月 31 日に取得。

ゲーデル、クルト(1958)。「Über eine bisher noch nicht benützte Erweiterung des finiten Standpunktes」。弁証法。12（3-4）。 1990 年に英語翻訳で再版されました。ゲーデル作品集、第 2 巻。ソロモン・フェフェルマン他編。オックスフォード大学出版局: 280–287。土井: 10.1111/j.1746-8361.1958.tb01464.x。

グラスマン、ヘルマン・ギュンター(1861)。 Lehrbuch der Arithmetik für höhere Lehranstalten。フェルラーク・フォン・テオド。 Ch.神父様エンスリン。

グレイ、ジェレミー(2013)。「エッセイスト」。アンリ・ポアンカレ：科学的伝記。プリンストン大学出版局。133 ページ。ISBN 978-0-691-15271-4。

Harsanyi, John C. (1983)。「数学、経験的事実、論理的必然性」。Hempel, Carl G.、Putnam, Hilary、Essler, Wilhelm K. (編)。方法論、認識論、科学哲学。pp. 167–192。doi :10.1007 / 978-94-015-7676-5_8。ISBN 978-90-481-8389-0. S2CID 121297669。

ハッチャー、ウィリアム S. (2014) [1982]. 数学の論理的基礎. エルゼビア. ISBN 978-1-4831-8963-5。いくつかの公理的集合論と圏理論からペアノ公理 ( Sと呼ばれる)を導出します。

ヘルメス、ハンス (1973)。『数学論理入門』。Hochschultext。Springer。ISBN 3-540-05819-2. ISSN 1431-4657.

ヒルベルト、デイヴィッド (1902)。「数学の問題」[数学の問題]。アメリカ数学会報。8 (10)。ウィントン、メイビー訳: 437–479。doi : 10.1090/ s0002-9904-1902-00923-3。

ケイ、リチャード（1991）。ペアノ算術のモデル。オックスフォード大学出版局。ISBN 0-19-853213-X。

Landau, Edmund (1965)。解析学の基礎。ペアノの公理から基本的な数体系を導き出す。英語/ドイツ語の語彙を含む。AMS Chelsea Publishing。ISBN 978-0-8284-0141-8。

メンデルソン、エリオット（1997年12月）[1979年12月]。『数理論理学入門（離散数学とその応用）』（第4版）。シュプリンガー。ISBN 978-0-412-80830-2。

Meseguer, José; Goguen, Joseph A. (1986 年 12 月)。「初期性、帰納法、および計算可能性」。Maurice Nivat および John C. Reynolds (編)。Algebraic Methods in Semantics (PDF) 。ケンブリッジ: Cambridge University Press。pp . 459–541。ISBN 978-0-521-26793-9。

パルティー、バーバラ;テル・ミューレン、アリス; ウォール、ロバート (2012)。言語学における数学的手法。シュプリンガー。ISBN 978-94-009-2213-6。

ペアノ、ジュゼッペ(1908)。 Formulario Mathematico (V 版)。トリノ、ボッカフレール、Ch.クラウゼン。 p. 27.

Peirce, C. S. (1881). 「数の論理について」.アメリカ数学ジャーナル. 4 (1): 85–95. doi :10.2307/2369151. JSTOR 2369151. MR 1507856.

シールズ、ポール (1997)。「3. パースの算術の公理化」。ハウザー、ネイサン、ロバーツ、ヴァン・エヴラ、ジェームズ (編)。チャールズ・サンダース・パースの論理学研究。インディアナ大学出版。pp. 43–52。ISBN 0-253-33020-3。

サップス、パトリック（1960）。公理的集合論。ドーバー出版。ISBN 0-486-61630-4。ZFCからペアノ公理を導出する

タルスキ、アルフレッド、ギヴァント、スティーブン（1987）。変数なしの集合論の形式化。AMSコロキウム出版。第41巻。アメリカ数学会。ISBN 978-0-8218-1041-5。

ヴァン・ヘイエノールト、ジャン（1967年）。『フレーゲからゲーデルまで：1879年から1931年までの数学論理学の原典』ハーバード大学出版局。ISBN 978-0-674-32449-7。
- 以下の 2 つの論文の翻訳と貴重な解説が含まれています。
  - デデキント、リチャード（1890）。ケファーシュタインへの手紙。100ページで、彼は1888年の公理を再度述べ、擁護している。98～103ページ。
  - ペアノ、ジュゼッペ(1889)。『算術の原理、新しい方法による』。ペアノが初めて公理を提示し、算術演算を再帰的に定義した論文の抜粋。Fratres Bocca。pp. 83–97。

Van Oosten、Jaap (1999 年 6 月)。「ペアノ算術入門 (ゲーデルの不完全性と非標準モデル)」(PDF)。ユトレヒト大学。2023 年9 月 2 日に取得。

王昊(1957年6 月)。「算術の公理化」。記号論理学ジャーナル。22 (2)。記号論理学会誌 : 145–158。doi :10.2307/2964176。JSTOR 2964176。S2CID 26896458。

Willard, Dan E. (2001). 「自己検証公理系、不完全性定理および関連する反射原理」(PDF) . The Journal of Symbolic Logic . 66 (2): 536–596. doi :10.2307/2695030. JSTOR 2695030. MR 1833464. S2CID 2822314.

さらに読む

Buss, Samuel R. (1998)。「第 2 章: 算術の第一階証明理論」。Buss, Samuel R. (編)。証明理論ハンドブック。ニューヨーク: Elsevier Science。ISBN 978-0-444-89840-1。

メンデルソン、エリオット（2015年6月）[1979年12月]。数理論理学入門（離散数学とその応用）（第6版）。チャップマン＆ホール/CRC。ISBN 978-1-4822-3772-6。

スムリアン、レイモンド M. (2013 年 12 月)。ゲーデルのパズルの本: パズル、パラドックス、証明。ドーバー出版。ISBN 978-0-486-49705-1。

竹内外史（2013）。証明理論(第 2 版)。ミネオラ、ニューヨーク州。ISBN 978-0-486-49073-1。{{cite book}}: CS1 maint: location missing publisher (link)

外部リンク

ムルジ、マウロ。「アンリ・ポアンカレ」。インターネット哲学百科事典。ポアンカレによるペアノの公理に対する批判についての議論が含まれています。
Podnieks, Karlis (2015-01-25). 「3. 第一階算術」. 数学とは何か: ゲーデルの定理とその周辺。pp. 93–121。
「ペアノの公理」、数学百科事典、EMS Press、2001 [1994]
Weisstein, Eric W.「ペアノの公理」。MathWorld。
Burris, Stanley N. (2001)。「数字とは何か、そしてその意味は何か: Dedekind」。デデキントの作品の解説。

この記事には、クリエイティブ・コモンズ表示/継承ライセンスに基づいてライセンスされているPA on PlanetMathの資料が組み込まれています。

[11] 0に対応する最も近いライトピースと、後続に対応する隣接ピース

[14] 非連続集合は、0 要素を持つため公理 1 を満たし、2 ～ 5 は等式関係に影響を与えないため公理 6 と 8 を満たし、0 要素を除くすべてのピースに後続のピースがあるため公理 7 を満たし、2 つのドミノが同じピースによって倒れたり倒れたりすることはないため公理 7 を満たします。

[30] " " は、他の公理 (一階述語論理) から次のように証明できます。まず、分配法則と加法的な恒等式によって。次に、公理 15 によって。の場合、同じ要素の加算と可換性により、つまり置換により、反射性と矛盾します。したがって、でなければなりません。 $\forall x\ (x\cdot 0=0)$ $x\cdot 0+x\cdot 0=x\cdot (0+0)=x\cdot 0=x\cdot 0+0$ $x\cdot 0=0\lor x\cdot 0>0$ $x\cdot 0>0$ $x\cdot 0+x\cdot 0>x\cdot 0+0$ $x\cdot 0+0>x\cdot 0+0$ $x\cdot 0=0$

[1] 「ペアノ」。ランダムハウス・ウェブスター大辞典。

[FOOTNOTEGrassmann1861-2] グラスマン 1861年。

[FOOTNOTEWang1957145,_147"It_is_rather_well-known,_through_Peano's_own_acknowledgement,_that_Peano_[…]_made_extensive_use_of_Grassmann's_work_in_his_development_of_the_axioms._It_is_not_so_well-known_that_Grassmann_had_essentially_the_characterization_of_the_set_of_all_integers,_now_customary_in_texts_of_modern_algebra,_that_it_forms_an_ordered_[[integral_domain]]_in_wihich_each_set_of_positive_elements_has_a_least_member._[…]_[Grassmann's_book]_was_probably_the_first_serious_and_rather_successful_attempt_to_put_numbers_on_a_more_or_less_axiomatic_basis."-3] Wang 1957、pp. 145、147、「ペアノ自身が認めているように、ペアノはグラスマンの研究を公理の発展に大いに活用した。グラスマンが本質的に、すべての整数の集合を、正の要素の各集合が最小の要素を持つ整列した整域を形成するという特徴付けをしたことは、あまり知られていない。[グラスマンの本]は、数を多かれ少なかれ公理的な基盤に置こうとした最初の真剣でかなり成功した試みだっただろう。」

[FOOTNOTEPeirce1881-4] ピアース 1881年。

[FOOTNOTEShields1997-5] シールド 1997.

[FOOTNOTEVan_Heijenoort196794-6] ヴァン・ヘイジェノールト1967年、94ページ。

[FOOTNOTEVan_Heijenoort19672-7] ヴァン・ヘイジェノールト 1967年、2ページ。

[FOOTNOTEVan_Heijenoort196783-8] Van Heijenoort 1967、p. 83.

[FOOTNOTEPeano18891-9] ペアノ 1889年、1ページ。

[FOOTNOTEPeano190827-10] ペアノ1908年、27ページ。

[12] マット・デヴォス、数学的帰納法、サイモンフレーザー大学

[13] ジェラルド・コン・ディアス、数学的帰納法、2013年5月2日アーカイブ、ハーバード大学、Wayback Machine

[FOOTNOTEMeseguerGoguen1986sections_2.3_(p._464)_and_4.1_(p._471)-15] Meseguer & Goguen 1986、セクション 2.3 (p. 464) および 4.1 (p. 471)。

[16] 正式な証明については、例えばFile:Inductive proofs of properties of add, mult from recursive definitions.pdfを参照してください。

[17] サップス 1960、ハッチャー 2014

[FOOTNOTETarskiGivant1987Section_7.6-18] Tarski & Givant 1987、セクション 7.6。

[19] Fritz 1952、p. 137
「解釈」の実例として、ラッセル自身の「基数」の定義が挙げられます。この場合の解釈されない体系とは、数体系に関するペアノの公理であり、その 3 つの基本的な考え方と 5 つの公理があれば、自然数体系のすべての特性を導き出すのに十分であるとペアノは信じていました。実際、ラッセルは、ペアノの公理は、自然数の級数がその一例である形式のあらゆる数列を定義していると主張しています。 $x_{0},x_{1},x_{2},\ldots ,x_{n},\ldots$

[20] Gray 2013, p. 133
そこでポアンカレは、論理主義が算術、より正確には順序数の算術を生み出すことができるかどうかを調べることにした。クーチュラは、ポアンカレはペアノの公理を数の定義として受け入れたと述べた。しかし、これではだめだ。公理は、例を見つけることで矛盾がないことを示すことはできないし、その含意の全体を調べることで矛盾がないことを示す試みには、クーチュラがそれらが含意すると信じていた数学的帰納法の原理そのものが必要になるだろう。なぜなら、（S&Mから削除されたさらなる一節によれば）原理を証明するために原理を仮定することは、それが真であれば自己矛盾ではないことを証明するだけであり、それでは何も言えないからである。あるいは、述べられた形式とは別の形式で原理を使用した場合、推論のステップ数が新しい定義に従って整数であることを示す必要があるが、これはできなかった (1905c、834)。

[FOOTNOTEHilbert1902-21] ヒルベルト 1902.

[FOOTNOTEGödel1931-22] ゲーデル 1931.

[23] ゲーデル 1958

[24] ゲンツェン 1936

[FOOTNOTEWillard2001-25] ウィラード 2001.

[FOOTNOTEParteeTer_MeulenWall2012215-26] Partee、Ter Meulen & Wall 2012、215ページ。

[FOOTNOTEHarsanyi1983-27] ハルサニ（1983年）。

[FOOTNOTEMendelson1997155-28] メンデルソン 1997、155ページ。

[FOOTNOTEKaye199116–18-29] ケイ1991、16-18頁。

[FOOTNOTEHermes1973VI.4.3-31] ^ヘルメス 1973、VI.4.3、 ソラルフ・スコレムの定理を提示

[FOOTNOTEHermes1973VI.3.1-32] ヘルメス1973、VI.3.1。

[FOOTNOTEKaye1991Section_11.3-33] Kaye 1991、セクション11.3。

[FOOTNOTEKaye199170ff.-34] Kaye 1991、70ページ以降。