ペアノの公理
ペアノの公理(ペアノのこうり、Peano axioms) とは、自然数の全体を特徴づける公理である。ペアノの公準(Peano postulates)あるいはデデキント=ペアノの公理(Dedekind-Peano axioms)とも呼ばれる。1891年にイタリアの数学者ジュゼッペ・ペアノにより定式化された。
ペアノの公理を起点にして、初等算術と整数・有理数・実数・複素数の構成などを実際に展開してみせた古典的な書物に、1930年に出版されたランダウによる『解析学の基礎』(Grundlagen Der Analysis)がある。
集合 ℕ と定数 0 と関数 Sと命題Eに関する次の公理をペアノの公理という自然数を 0 からではなく 1 から始める流儀もある。また自然数の全体が順序数であることを意識するときにはギリシャ文字の ω を用いることがある。。
任意の n ∈ ℕ について S(n) ∈ ℕ
任意の n ∈ ℕ について S(n) ≠ 0
任意の n, m ∈ ℕ について S(n) ≠ S(m)
任意の E ⊆ ℕ について 0 ∈ E かつ任意の n ∈ ℕ について n ∈ E → S(n) ∈ E ならば E  ℕ
このとき ℕ の元を自然数といい、自然数 n に対して自然数 S(n) をその後者 (successor)自然数 S(n) は直後の数 n + 1 に相当する。ただし定数 1 や関数 + はまだ定義されていないことに注意。という。
第五公理は、数学的帰納法の原理である任意の部分集合に関する量化を行っているので、これは一階述語論理では形式化できない。。
これらの公理は互いに独立であり、いずれも残りから導くことはできない。
ペアノの公理から 2 + 2  4 や 2 ⋅ 2  4 のような「定理」を証明するには 2  S(S(0)) などの項を導入したり、加法 + や乗法 ⋅ の存在や性質を示したりする必要がある。たとえば  を見よ。
次の主張を回帰定理(recursion theorem)という。
集合 X に属する元 x と写像 g: X → X が与えられたとき
f(0) = x,\ f \circ S = g \circ f
f \colon \mathbb N \to X
が一意的に存在する。
たとえば X  ℕ のとき写像 f は初項が x の漸化式により定義される数列に他ならない。回帰定理はこのような再帰的に定義される写像の存在と一意性を数学的帰納法の原理により保証する。
集合 ℕ^ と定数 0^ と関数 S^ がペアノの公理を満たすとき組 (ℕ^, 0^, S^) をペアノ構造(Peano structure)という。ペアノ構造は同型を除いてただ一つに定まるすなわち全単射 φ: ℕ → ℕ^ で φ(0)  0^ かつ φ ∘ S  S^ ∘ φ を満たすものが存在する。、つまりペアノの公理は範疇的(categorical)であることがわかる。
一方で後述するペアノ算術はレーヴェンハイム=スコーレムの定理から超準モデルをもつので範疇的ではない。
現代数学において標準的な数学の対象はすべて集合として実現されている。集合論における自然数の標準的な構成法としては
\mathbb N := \bigcap \{\, x \mid \emptyset \in x \land \forall y[ y \in x \to y \cup \{ y \} \in x ] \,\}
0 := \emptyset
S(x) := x \cup \{ x \}
があるハルモス曰く「読者がこの自然数の定義に関連して味わうかもしれない軽微な不快感はまったく普通のまた大ていの場合は一時的なものである」。。これらの集合は存在して、ペアノの公理を満たすことが確かめられる。
0 = \emptyset = \{\}
1 := S(0) = \{0\} = \{\{\}\}
2 := S(1) = \{0, 1\} = \{\{\}, \{\{\}\}\}
3 := S(2) = \{0, 1, 2\} = \{\{\}, \{\{\}\}, \{\{\}, \{\{\}\}\}\}
のようになる。この構成法はジョン・フォン・ノイマンによる。
自然数の集合が定義されたとき、その構成と自然数上での帰納法から、自然数上の算術や順序を定めることができる。
自然数の加法は次のように再帰的に定義される。
n + 0 = n
n + S(m) = S(n + m)
自然数の乗法は次のように再帰的に定義される。
n \cdot 0 = 0
n \cdot S(m) = n \cdot m + n
自然数の順序は次のように定義される。
ある k について
n + k = m
n \le m
と定義する。
また n ≤ m かつ n ≠ m のとき n < m と定義する。
非論理記号として定数記号 0 と関数記号 S, +, ⋅ と述語記号 < をもつ等号つき一階述語論理の形式言語上で、以下の公理によって定まる理論をペアノ算術(Peano arithmetic)あるいは PA という(形式言語や公理の選び方には本質的に同じものが色々とある。)。
\forall n \lnot[S(n) = 0]
\forall n \forall m [S(n) = S(m) \to n = m]
\forall n [n + 0 = n]
\forall n \forall m[n + S(m) = S(n + m)]
\forall n [n \cdot 0 = 0]
\forall n \forall m [n \cdot S(m) = n \cdot m + n]
\forall n \lnot[n < 0]
\forall n \forall m [ [n < S(m)] \leftrightarrow [n < m] \lor [n = m]
[\varphi(0) \land \forall n [\varphi(n) \to \varphi(S(n))] \to \forall n [\varphi(n)]
自然数の標準モデル ℕ において真である Σ1 閉論理式はペアノ算術から証明ができること(PA の Σ1 完全性)が知られている。
一方でゲーデルの第一不完全性定理によりペアノ算術からは証明も反証もできない命題が存在する。有名な例としてはグッドスタインの定理やパリス=ハーリントンの定理がある。
ペアノは 1889年に「Arithmetices Principia, nova methodo exposita(算術原理)」と題するラテン語で書かれた論文で自然数の公理の原型となるべきものを発表しているが、それらは自然数以外の公理を含み本来必要とされるよりも多くの命題が述べられているなど、自然数の公理系としては不十分なものであった。1889 年の記載は以下の通り。原論文には誤植があるが正しい形に修正。本論文では、この後、四則演算の定義などが続き、ここでは明示的に自然数を定義しようとしている。
1 は自然数
a が自然数なら a = a
a, b が自然数で a = b なら b = a
a, b, c が自然数で a = b, b = c なら a = c
a = b で b が自然数なら a は自然数
a が自然数なら a + 1 は自然数
a, b が自然数で a = b なら a + 1 = b + 1
a が自然数なら、a + 1 と 1 は等しくない
もし集合 K が、1 を含み かつ 自然数 x が K に含まれるなら x + 1 が K に含まれる、という条件を満たすなら K は全ての自然数を含む
現在ペアノの公理系として知られる形のものが発表されたのは 1891年の「数の概念について」である。
この論文の中でペアノは次の 5 項目を自然数の満たすべき原始命題として与え、さらにこれら 5 つの命題が互いに独立であることを証明した。ペアノは現代の用語で言うところの公理と推論規則を合わせて原始命題と呼んだ。ここで挙げているものは公理にあたる。
1 は自然数である
任意の自然数 a に対して、a+ が自然数を与えるような右作用演算 + が存在する
もし a, b を自然数とすると、 a+ = b+ ならば a = b である
a+ = 1 を満たすような自然数 a は存在しない
集合s が二条件「(i) 1 は s に含まれる, (ii) 自然数 a が s に含まれるならば a+ も s に含まれる」を満たすならば、あらゆる自然数は s に含まれる。
ペアノがこれらの原始命題によって自然数そのものを定義しようとはしなかった点には注意を払う必要がある。
彼は自然数の持つべき性質を挙げ、自然数 や 1 などの原始命題中に現れる用語を無定義述語として扱っている。
これは後にヒルベルトらによって強力に進められることになる、形式主義的方法の格好の例といえる。