ペアノの公理

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

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

公理

集合 $ℕ$ と定数 $0$ と関数 $S$ と集合 $E$ に関する次の公理をペアノの公理という^[3]^{[注 1]}。

$0 \in ℕ$
任意の $n \in ℕ$ について $S (n) \in ℕ$
任意の $n \in ℕ$ について $S (n) \neq 0$
任意の $n, m \in ℕ$ について $n \neq m$ ならば $S (n) \neq S (m)$
任意の $E \subseteq ℕ$ について $0 \in E$ かつ任意の $n \in ℕ$ について $n \in E \to S (n) \in E$ ならば $E = ℕ$

このとき $ℕ$ の元を自然数といい、自然数 $n$ に対して自然数 $S (n)$ をその後者 (successor)^{[注 2]}という。

第五公理は、数学的帰納法の原理である^{[注 3]}。

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

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

回帰定理

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

集合 $X$ に属する元 $x$ と写像 $g : X \to 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）という。ペアノ構造は同型を除いてただ一つに定まる^{[注 4]}、つまりペアノの公理は範疇的（categorical）であることがわかる。

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

集合論的な構成

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

\mathbb {N} :=\bigcap \{\,x\subset A\mid \emptyset \in x\land \forall y[y\in x\to y\cup \{y\}\in x]\,\}

0:=\emptyset

S(x):=x\cup \{x\}

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

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

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

$0=\emptyset =\{\}$
$1:=S(0)=\{0\}=\{\{\}\}$
$2:=S(1)=\{0,1\}=\{\{\},\{\{\}\}\}$
$3:=S(2)=\{0,1,2\}=\{\{\},\{\{\}\},\{\{\},\{\{\}\}\}\}$

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

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

加法

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

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\leq m

と定義する。

また $n \leq m$ かつ $n \neq m$ のとき $n < m$ と定義する。

ペアノ算術

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

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

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

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

無矛盾性

歴史

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

脚注

[脚注の使い方]

注釈

^ 自然数を $0$ からではなく $1$ から始める流儀もある^[4]。また自然数の全体が順序数であることを意識するときにはギリシャ文字の $ω$ を用いることがある。
^ 自然数 $S (n)$ は直後の数 $n + 1$ に相当する。ただし定数 $1$ や関数 $+$ はまだ定義されていないことに注意。
^ 任意の部分集合に関する量化を行っているので、これは一階述語論理では形式化できない。
^ すなわち全単射 $φ : ℕ \to ℕ^$ で $φ (0) = 0^$ かつ $φ \circ S = S^ \circ φ$ を満たすものが存在する。

出典

^ G. バーコフ、S. マクレーン『現代代数学概論』（改訂3版）白水社、1967年、82–86頁。NDLJP:2422244。
^ 菊池 2014, p. 98.
^ ハルモス 1975, p. 82.
^ 彌永 1972, p. 66.
^ EoM 2001.
^ 足立 2002, p. 77, 定理 3.2（回帰定理）.
^ von Neumann 1923
^ 鹿島 2007, p. 64.
^ 鹿島 2007, p. 70.
^ ペアノ 1969
^ Peano 1889

参考文献

足立恒雄『数：体系と歴史』朝倉書店、2002年。ISBN 4-254-11088-X。
彌永昌吉『数の体系』上、岩波書店〈岩波新書（青版）815〉、1972年。ISBN 4-00-416001-4。
鹿島亮 (2007), “第一不完全性定理と第二不完全性定理”, 不完全性定理と算術の体系, ゲーデルと20世紀の論理学, 3, 東京大学出版会, ISBN 978-4-13-064097-8
菊池誠『不完全性定理』共立出版、2014年。ISBN 978-4-320-11096-0。
ハルモス, P.R. 著、富川滋訳『素朴集合論』ミネルヴァ書房、1975年。
Dedekind, Richard (1963-06-01) [1901], Essays on the Theory of Numbers, Dover Books on Mathematics (Paparback ed.), Dover Publications, ISBN 978-0-486-21010-0
- デーデキント著、河野伊三郎訳『数について――連続性と数の本質――』岩波書店〈岩波文庫青924-1〉、1961年11月16日。ISBN 978-4-00-339241-6。
- リヒャルト・デデキント『数とは何かそして何であるべきか』渕野昌訳・解説、筑摩書房〈ちくま学芸文庫テ9-1 Math & Science〉、2013年7月10日。ISBN 978-4-480-09547-3。 - 「数とは何かそして何であるべきか？」・「連続性と無理数」を収録。
ジュゼッペ・ペアノ『数の概念について』小野勝次・梅沢敏郎訳・解説、共立出版〈現代数学の系譜 2〉、1969年8月30日。ISBN 978-4-320-01155-7。
van Heijenoort, Jean, ed. (1967), From Frege to Gödel: A Source Book in Mathematical Logic, 1879–1931, Cambridge, Mass: Harvard University Press, ISBN 978-0-674-32449-7
Henle, J.M. (1986). An Outline of Set Theory. Springer-Verlag. ISBN 978-0-387-96368-6. MR861950. Zbl 0613.04001
- ヘンレ, J.R. 著、一松信訳『集合論問題ゼミ』シュプリンガー・フェアラーク東京、1987年。ISBN 4-431-70531-7。

外部リンク

[5] 自然数を $0$ からではなく $1$ から始める流儀もある^[4]。また自然数の全体が順序数であることを意識するときにはギリシャ文字の $ω$ を用いることがある。

[6] 自然数 $S (n)$ は直後の数 $n + 1$ に相当する。ただし定数 $1$ や関数 $+$ はまだ定義されていないことに注意。

[7] 任意の部分集合に関する量化を行っているので、これは一階述語論理では形式化できない。

[10] すなわち全単射 $φ : ℕ \to ℕ^$ で $φ (0) = 0^$ かつ $φ \circ S = S^ \circ φ$ を満たすものが存在する。

[1] G. バーコフ、S. マクレーン『現代代数学概論』（改訂3版）白水社、1967年、82–86頁。NDLJP:2422244。

[FOOTNOTE菊池201498-2] 菊池 2014, p. 98.

[FOOTNOTEハルモス197582-3] ハルモス 1975, p. 82.

[FOOTNOTE彌永197266-4] 彌永 1972, p. 66.

[FOOTNOTEEoM2001-8] EoM 2001.

[FOOTNOTE足立200277定理_3.2（回帰定理）-9] 足立 2002, p. 77, 定理 3.2（回帰定理）.

[11] von Neumann 1923

[FOOTNOTE鹿島200764-12] 鹿島 2007, p. 64.

[FOOTNOTE鹿島200770-13] 鹿島 2007, p. 70.

[14] ペアノ 1969

[15] Peano 1889

[1]

[2]

[3]

[注 1]

[注 2]

[注 3]

[5]

[6]

[注 4]

[7]

[8]

[9]

[10]

[11]

[4]

公理