ペアノの公理

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

ペアノの公理（ペアノのこうり、英: Peano axioms） とは、自然数の全体を特徴づける公理である。ペアノの公準（英: Peano postulates）あるいはデデキント＝ペアノの公理（英: Dedekind-Peano axioms）とも呼ばれる^[1][2]。1891年にイタリアの数学者ジュゼッペ・ペアノにより定式化された。

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

公理

集合 ℕ と定数 0 と関数 S と集合 E に関する次の公理を、ペアノの公理という^{[3][注釈 1]}。ℕ の元を自然数、S(n) を n の後者（英: successor）^{[注釈 2]} という。

• 0 ∈ ℕ
• 任意の n ∈ ℕ について S(n) ∈ ℕ
• 任意の n ∈ ℕ について S(n) ≠ 0
• 任意の n, m ∈ ℕ について n ≠ m ならば S(n) ≠ S(m)
• 任意の E ⊆ ℕ について 0 ∈ E かつ任意の n ∈ ℕ について n ∈ E → S(n) ∈ E ならば E = ℕ
  • この公理は、数学的帰納法の原理である^{[注釈 3]}。

これらの公理は互いに独立であり、いずれも残りから導くことはできない^[5]。

ペアノの公理から 2 + 2 = 4 や 2 • 2 = 4 のような「定理」を証明するには、2 = S(S(0)) などの項を導入したり、加法 + や乗法 • の存在や性質を示したりする必要がある。例えば Henle (1986, pp. 17, 18, 103, 104) を見よ。

回帰定理

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

集合 X に属する元 x と写像 g: X → X が与えられたとき

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

を満たす写像

${\displaystyle f\colon \mathbb {N} \to X}$

が一意的に存在する。

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

範疇性

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

一方で後述するペアノ算術はレーヴェンハイム＝スコーレムの定理から超準モデルをもつので範疇的ではない。

自然数の集合論的構成

現代数学において標準的な数学の対象はすべて集合として実現されている。集合論における自然数の標準的な構成法としては、

• ${\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\}}$

がある。ただしここでAは無限公理により存在する集合を任意に選んだものである。

これらの集合は存在して、ペアノの公理を満たすことが確かめられる。

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

• ${\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 \}\}\}\}}$

のようになる。この構成法はジョン・フォン・ノイマンによる^[7]。

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

加法

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

${\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 と定義する。

ペアノ算術

非論理記号として定数記号 0 と関数記号 S, +, ⋅ と述語記号 < をもつ等号つき一階述語論理の形式言語上で、以下の公理によって定まる理論をペアノ算術（Peano arithmetic）あるいは PA という^[8]（形式言語や公理の選び方には本質的に同じものが色々とある。）。

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 の Σ₁ 完全性）が知られている^[9]。

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

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

無矛盾性

歴史

ペアノは 1889年に「Arithmetices Principia, nova methodo exposita（算術原理）」と題するラテン語で書かれた論文で自然数の公理の原型となるべきものを発表している^[10][11]が、それらは自然数以外の公理を含み本来必要とされるよりも多くの命題が述べられているなど、自然数の公理系としては不十分なものであった。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 などの原始命題中に現れる用語を無定義述語として扱っている。 これは後にヒルベルトらによって強力に進められることになる、形式主義的方法の格好の例といえる。