ペアノの公理
ペアノは 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 は全ての自然数を含む
∀ n ¬ [ n < 0 ] {\displaystyle \forall n\lnot [n<0]}
∀ n ∀ m [ [ n < S ( m ) ] ↔ [ n < m ] ∨ [ n = m ] ] {\displaystyle \forall n\forall m[[n<S(m)]\leftrightarrow [n<m]\lor [n=m]]}
[ φ ( 0 ) ∧ ∀ n [ φ ( n ) → φ ( S ( n ) ) ] ] → ∀ n [ φ ( n ) ] {\displaystyle [\varphi (0)\land \forall n[\varphi (n)\to \varphi (S(n))]]\to \forall n[\varphi (n)]}
自然数の標準モデル N において真である Σ1 閉論理式はペアノ算術から証明ができること(PA の Σ1 完全性)が知られている。
一方でゲーデルの第一不完全性定理によりペアノ算術からは証明も反証もできない命題が存在する。有名な例としてはグッドスタインの定理やパリス=ハーリントンの定理がある。
次の主張を回帰定理(recursion theorem)という。
集合 X に属する元 x と写像 g: X → X が与えられたとき
f ( 0 ) = x , f ∘ S = g ∘ f {\displaystyle f(0)=x,\ f\circ S=g\circ f}
を満たす写像
f : N → X {\displaystyle f\colon \mathbb {N} \to X}
が一意的に存在する。
たとえば X = N のとき写像 f は初項が x の漸化式により定義される数列に他ならない。回帰定理はこのような再帰的に定義される写像の存在と一意性を数学的帰納法の原理により保証する。