ペアノの公理

以下の公理系をデーデキント＝ペアノの公理系という^{[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 の漸化式により定義される数列である。再帰定理はこのような再帰的に定義される写像の存在と一意性を数学的帰納法の原理により保証する。

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

この一意性（2つのペアノシステムが互いに同型であること）は、リヒャルト・デーデキントによって証明されたものであり、再帰定理の帰結として以下のように具体的に導かれる。

2つの任意のペアノ構造 ${\displaystyle (\mathbb {N} ,0,S)}$ と ${\displaystyle (\mathbb {N} ',0',S')}$ を考える。構造 ${\displaystyle (\mathbb {N} ,0,S)}$ に対する再帰定理において、集合 ${\displaystyle X}$ として ${\displaystyle \mathbb {N} '}$ を、要素 ${\displaystyle x}$ として ${\displaystyle 0'}$ を、写像 ${\displaystyle g}$ として ${\displaystyle S'\colon \mathbb {N} '\to \mathbb {N} '}$ を選択すると、写像 ${\displaystyle f\colon \mathbb {N} \to \mathbb {N} '}$ であって次の条件を満たすものがただ一つ存在する：

${\displaystyle f(0)=0'}$

${\displaystyle f(S(n))=S'(f(n))\quad (\forall n\in \mathbb {N} )}$

対称性により、同様にして写像 ${\displaystyle f'\colon \mathbb {N} '\to \mathbb {N} }$ であって ${\displaystyle f'(0')=0}$ および ${\displaystyle f'(S'(n'))=S(f'(n'))}$ を満たすものもただ一つ存在する。

ここで、合成写像 ${\displaystyle f'\circ f\colon \mathbb {N} \to \mathbb {N} }$ について考えると、これは ${\displaystyle (f'\circ f)(0)=f'(0')=0}$、および ${\displaystyle (f'\circ f)(S(n))=f'(S'(f(n)))=S(f'(f(n)))=S((f'\circ f)(n))}$ を満たす。一方で、恒等写像 ${\displaystyle \mathrm {id} _{\mathbb {N} }\colon \mathbb {N} \to \mathbb {N} }$ もまた ${\displaystyle \mathrm {id} _{\mathbb {N} }(0)=0}$ および ${\displaystyle \mathrm {id} _{\mathbb {N} }(S(n))=S(\mathrm {id} _{\mathbb {N} }(n))}$ を満たす。構造 ${\displaystyle \mathbb {N} }$ 上の再帰定理における一意性により、これらは一致しなければならないため、${\displaystyle f'\circ f=\mathrm {id} _{\mathbb {N} }}$ が成り立つ。全く同様の議論を合成写像 ${\displaystyle f\circ f'\colon \mathbb {N} '\to \mathbb {N} '}$ に適用することで、${\displaystyle f\circ f'=\mathrm {id} _{\mathbb {N} '}}$ も得られる。

したがって、写像 ${\displaystyle f}$ は全単射（同型写像）であり、${\displaystyle f'}$ はその逆写像 ${\displaystyle f^{-1}}$ であることが示される。この事実から、ペアノの公理を満たすいかなる2つのシステムも、構造として本質的に同一（互いに同型）であることが保証される。

一方，後述するペアノ算術 (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 \}\}\}\}}$

のようになる。

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

ペアノは 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]。

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