形式的なペアノの公理で誤解しやすいポイント

ペアノの公理,ペアノ算術,自然数

10035

概要

ペアノの公理で誤解しやすいポイントについてまとめました。
なお、本記事では形式的な立場をとり、論理体系は等号付き古典一階述語論理に限定します。

ペアノの公理とペアノ算術は違う

ペアノの公理

（ここでは特定の公理系で議論を限定するため, 公理系はZFCとする）

集合$N,\ S,\ O$が次を満たすとき, 集合の組$(N,S,O)$をペアノシステムとよぶ.

$O\in N$
$S\colon N\to N$
$\forall n\in N\ S(n) \not= O$
$\forall m,\ n\in N\ (S(m)=S(n) \Rightarrow m = n)$
$\forall A\subseteq N\ ((O\in A \wedge (\forall n\in A\ S(n)\in A)) \Rightarrow A = N)$

論理式1.から5.をペアノの公理とよぶ.

ペアノ算術

語彙は次の4つとする.

$0$は定数記号
$S$は1変数の関数記号
$+,\ \times$は2変数の関数記号

次の論理式1.から6.と公理図式7.を集めたものをペアノ算術とよぶ.

$\forall n\ S(n) \not= 0$
$\forall m\forall n\ (S(m)=S(n) \Rightarrow m = n)$
$\forall n\ n+0 = n$
$\forall m\forall n\ m+S(n) = S(m+n)$
$\forall n\ n\times0 = 0$
$\forall m\forall n\ m\times S(n) = (m\times n)+m$
$P$を算術の論理式とする.
$P$の自由変数を$n,\ w_0,\ \ldots,\ w_{i-1}$とする.
$\forall w_0\ldots \forall w_{i-1}((P(0) \wedge (\forall n\ (P(n)\Rightarrow P(S(n)))))\Rightarrow \forall n\ P(n))$

2つの大きな違いは次のようになります。

ペアノの公理は集合論の中におけるペアノシステムの定義式
ペアノ算術は一階述語論理の公理系

ペアノの公理は自然数を作っていない

ペアノの公理は「自然数がこんな風になってたらいいなー」ということが書いてますが、具体的に自然数を構成していません。

つまりペアノシステム$(N,S,O)$が存在するかはペアノの公理を定義しただけではわかりません。

またペアノシステム$(N,S,O)$の例はたくさん作れます。

有限順序数全体の集合を$\omega$とし、写像$\mathrm{suc}:\omega\to\omega$を$\mathrm{suc}(n)=n\cup\{n\}$で定義すると$(\omega,\mathrm{suc},\emptyset)$や$(\omega\setminus\{\emptyset\},\mathrm{suc}|_{\omega\setminus\{\emptyset\}},\{\emptyset\})$などはペアノシステムです。

数学的帰納法と再帰的定義は違う

おおざっぱにいえば、数学的帰納法は証明の方法で、再帰的定義は定義の方法です。

ペアノの公理の中に数学的帰納法はありますが、再帰的定義については書いてないので再帰的定義ができることを示さないといけません。

1+1=2の証明で本当に難しいのは+を作ること

繰り返しになりますが、ペアノシステム$(N,S,O)$について$N$上で再帰的定義ができることを示さないといけません。

$+$を構成をしてからようやく$1+1=2$の証明ができます。

ペアノの公理と1+1=2の証明が関係あるかと言われると微妙

ペアノの公理から+を構成できたとして$1+1=2$を証明しようとするとだいたい↓のようになると思います。

$1:=S(O),\ 2:=S(S(O))$と略記して

$1+1=S(O)+S(O)=S(S(O)+O)=S(S(O))=2.\ \square$

この証明に使っているのは+の定義とペアノの公理のうち$S\colon N\to N$と$O\in N$だけです。

表面上、単射とか、全射でないとか、数学的帰納法とかのペアノの公理の大事な部分を使っていません。

なので、+の構成を省略するならペアノの公理を紹介されても、あまり関係がないように見えると思います。

ペアノ算術の公理の数は無限個

ペアノ算術における数学的帰納法は↓のことです。

$P$を算術の論理式とする.
　$P$の自由変数を$n,\ w_0,\ \ldots,\ w_{i-1}$とする.
$\forall w_0\ldots \forall w_{i-1}((P(0) \wedge (\forall n\ (P(n)\Rightarrow P(S(n)))))\Rightarrow \forall n\ P(n))$

これは一つの公理ではなく、論理式$P$ごとに一つの公理があって、それを全部集めたものです。

なのでペアノ算術の公理の数は無限個になります。