ペアノの公理

一階述語論理による自然数論の形式化である「ペアノ算術（Peano arithmetic）」あるいは常微分方程式に関する「ペアノの存在定理」とは異なります。

ペアノの公理（ペアノのこうり、英: Peano axioms） とは、自然数の全体を特徴づける公理である。ペアノの公準（英: Peano postulates）あるいはデーデキント＝ペアノの公理系（英: Dedekind-Peano axioms）と呼ばれる^[1][2]。1891年にイタリアの数学者ジュゼッペ・ペアノにより定式化された。自然数は数学における基本的対象であるが，これを経験的な特定対象物としてではなくいかなる性質を満たすべきものとして存在しているのかに答えるのが本公理系である．

ペアノの公理を起点とし、初等算術と整数・有理数・実数・複素数の構成を実際に展開した古典的な書物に、ランダウによる『解析学の基礎』（Grundlagen der Analysis）（1930出版）がある。

公理

以下の公理系をデーデキント＝ペアノの公理系という^{[3][注釈 1]}。

• 0 ∈ N
• 任意の n ∈ N について S(n) ∈ N
• 任意の n ∈ N について S(n) ≠ 0
• 任意の n, m ∈ N について n ≠ m ならば S(n) ≠ S(m)
• 任意の E ⊆ N について ( 0 ∈ E かつ任意の n ∈ N について n ∈ E → S(n) ∈ E ) ならば E = N （数学的帰納法）^{[注釈 2]}。

後述の通り，この公理系を満たす構造Nは（同型を除いて）一通りとなり自然数の特徴づけとなっている．したがってこれを ℕ で表すことが出来る．また ℕ の各要素を自然数と呼ぶ．S(n) を n の後者（英: successor）^{[注釈 3]} ，Sをsuccessor functionと云う。またこの上での加法や乗法の展開については例えば Henle (1986, pp. 17, 18, 103, 104) を見よ。

再帰定理

次の主張を再帰定理（recursion theorem）という^[5]。

任意の集合 X と， x ∈ X ，写像 g: X → X に対して，写像 ${\displaystyle f\colon \mathbb {N} \to X}$がただひとつ存在し，

${\displaystyle f(0)=x,\ f\circ S=g\circ f}$

を満たす．

たとえば X = ℕ のとき写像 f は初項が x の漸化式により定義される数列である。再帰定理はこのような再帰的に定義される写像の存在と一意性を数学的帰納法の原理により保証する。

数学的帰納法と範疇性

集合 ℕ^ と定数 0^ と関数 S^ がペアノの公理を満たすとき組 (ℕ^, 0^, S^) をペアノ構造（Peano structure）という。ペアノ構造は数学的帰納法の原理により同型を除いてただ一つに定まる^{[注 1]}、つまりペアノの公理は範疇的（categorical）であることがわかる。

一方，後述するペアノ算術 (Peano arithmetic) は数学的帰納法の原理を弱めた公理系であり，レーヴェンハイム＝スコーレムの定理から超準モデルを持ち，範疇的公理系ではない。

自然数の集合論的構成

ジョン・フォン・ノイマン^[6]は集合論における自然数の標準的な構成法を与えた．まず無限公理に基いて何かしらひとつ集合Aを得たのち，

• ${\displaystyle \mathbb {N}$ :=\bigcap \ \{\,x\subset A\mid \varnothing \in x\land \forall \ y\ [y\in x\to y\cup \{y\}\in x]\,\}}
• ${\displaystyle 0:=\varnothing }$
• ${\displaystyle S(x):=x\cup \{x\}}$

とする．構造( ℕ, 0, S ) はDedekind-Peanoの公理系を満たす．

このとき具体的な自然数は

• ${\displaystyle 1:=S(0)=\{0\}=\{\varnothing \}}$
• ${\displaystyle 2:=S(1)=\{0,1\}=\{\varnothing ,\{\varnothing \}\}}$
• ${\displaystyle 3:=S(2)=\{0,1,2\}=\{\varnothing ,\{\varnothing \},\{\varnothing ,\{\varnothing \}\}\}}$
• ${\displaystyle 4:=S(3)=\{0,1,2,3\}=\{\varnothing ,\{\varnothing \},\{\varnothing ,\{\varnothing \}\},\{\varnothing ,\{\varnothing \},\{\varnothing ,\{\varnothing \}\}\}\}}$

のようになる。

自然数の集合が定義されたとき、その構成と自然数上での帰納法から、自然数上の算術や順序を定めることができる。

加法

自然数の加法は次のように再帰的に定義される。

${\displaystyle n+0=n}$

${\displaystyle n+S(m)=S(n+m)}$

乗法

自然数の乗法は次のように再帰的に定義される。

${\displaystyle n\cdot 0=0}$

${\displaystyle n\cdot S(m)=n\cdot m+n}$

順序

自然数の順序は次のように定義される。 ある k について

${\displaystyle n+k=m}$

が成り立つとき

${\displaystyle n\leq m}$

と定義する。

また n ≤ m かつ n ≠ m のとき n < m と定義する。

発表時の公理系

ペアノは 1889年に「Arithmetices Principia, nova methodo exposita（算術原理）」と題する論文のおいて自然数の公理の原型となるべきものを発表している^[7][8]．これらは自然数以外の公理を含み本来必要とされるよりも多くの命題が述べられているなど、自然数の公理系としては未整備であった。1889 年の記載は誤植の修正を除いて以下の通りである。当該論文では、この後、四則演算の定義などが続くが、ここでは明示的に自然数を定義しようとしている。

1. 1 は自然数
2. a が自然数なら a = a
3. a, b が自然数で a = b なら b = a
4. a, b, c が自然数で a = b, b = c なら a = c
5. a = b で b が自然数なら a は自然数
6. a が自然数なら a + 1 は自然数
7. a, b が自然数で a = b なら a + 1 = b + 1
8. a が自然数なら、a + 1 と 1 は等しくない
9. もし集合 K が、1 を含み かつ 自然数 x が K に含まれるなら x + 1 が K に含まれる、という条件を満たすなら K は全ての自然数を含む

現在ペアノの公理系として知られる形のものが発表されたのは 1891年の「数の概念について」である。 この論文の中でペアノは次の 5 項目を自然数の満たすべき原始命題として与え、さらにこれら 5 つの命題が互いに独立であることを証明した。ペアノは現代の用語で言うところの公理と推論規則を合わせて原始命題と呼んだ。ここで挙げているものは公理にあたる。

1. 1 は自然数である
2. 任意の自然数 a に対して、a+ が自然数を与えるような右作用演算 + が存在する
3. もし a, b を自然数とすると、 a+ = b+ ならば a = b である
4. a+ = 1 を満たすような自然数 a は存在しない
5. 集合s が二条件「(i) 1 は s に含まれる, (ii) 自然数 a が s に含まれるならば a+ も s に含まれる」を満たすならば、あらゆる自然数は s に含まれる。

ペアノがこれらの原始命題によって自然数そのものを定義しようとはしなかった点には注意を払う必要がある。 彼は自然数の持つべき性質を挙げ、自然数 や 1 などの原始命題中に現れる用語を無定義述語として扱っている。 これは後にヒルベルトらによって強力に進められることになる、形式主義的方法の格好の例といえる。

ペアノ算術

Dedekind-Peanoの公理系における数学的帰納法の原理をいわゆる一階述語論理に弱めることで得られる体系をPeano arithmeticと云い，重要な研究対象である．非論理記号として定数記号 0 と関数記号 S, +, ⋅ と述語記号 < をもつ等号つき一階述語論理の形式言語上で、以下の公理系をペアノ算術（Peano arithmetic）あるいは PA という^[9]．言語選択や公理設定は流行や流儀が存在し本質的に同じものが考察される：

1. ${\displaystyle \forall n\lnot [S(n)=0]}$
2. ${\displaystyle \forall n\forall m[S(n)=S(m)\to n=m]}$
3. ${\displaystyle \forall n[n+0=n]}$
4. ${\displaystyle \forall n\forall m[n+S(m)=S(n+m)]}$
5. ${\displaystyle \forall n[n\cdot 0=0]}$
6. ${\displaystyle \forall n\forall m[n\cdot S(m)=n\cdot m+n]}$
7. ${\displaystyle \forall n\lnot [n<0]}$
8. ${\displaystyle \forall n\forall m[[n<S(m)]\leftrightarrow [n<m]\lor [n=m]]}$
9. ${\displaystyle [\varphi (0)\land \forall n[\varphi (n)\to \varphi (S(n))]]\to \forall n[\varphi (n)]}$

自然数の標準モデル ℕ において真である Σ₁ 閉論理式はペアノ算術から証明ができること（PA の Σ₁ 完全性）が知られている^[10]。

一方でゲーデルの第一不完全性定理によりペアノ算術からは証明も反証もできない命題が存在する。有名な例としてはグッドスタインの定理やパリス＝ハーリントンの定理がある。

→「ロビンソン算術」および「原始再帰的算術」も参照