: 2022年5月1日

ペアノの公理系

: 基礎数学
: 自然数; ペアノの公理系; 再帰性定理
対象: 大学2.0年
前提知識: 集合の基礎; 写像; 集合族の共通部分

自然数が満たすべき性質をまとめたペアノの公理系は有名で，巷で盛んに紹介されています．自然数全体の集合は数学において基本的なものですから，自然数とはそもそも何かを追求するのは健全な姿勢です．自然数について紹介しているウェブページは沢山ありますが，この文書では自然数を知る上でかなり重要な概念である「再帰性定理（recursion theorem）」について掘り下げて解説します．

漸化式による数列の定義は認められる？

まずは再帰性定理を学ぶ意義について軽く解説します．例えば， $a_{1} = 1, a_{n + 1} = 2 + a_{n} (n = 1, 2, 3, \dots)$ で定義される数列 $(a_{n})$ なんてものを平然と扱いますが，一般項が初等的に表せなくてもそのような数列を数学では扱うことができます．つまり，実際に計算せずとも，すべての自然数 $n$ に対して $a_{n}$ がただ一つ確定している，としてよいのです．このような漸化式によって数列が確定するという事実は，再帰性定理によるものなのです．中間値の定理や平均値の定理のように，具体的に幾つかは不明だけど，それを満足する実数は存在する，そんな感覚に似ています．

他にも，再帰性定理があるがゆえに自然数同士の和や積，冪乗，階乗などを論理的に定義でき，なおかつ数々の諸性質を証明することができるのです．あと，大学数学でやたら登場する帰納的に閉区間の列 $(I_{n})$ を定義する，といった帰納的写像の定義も再帰性定理を用いています．

みなさんがもし大学の数学を学んでいるのならば，絶対にどこかで知らないうちに再帰性定理を使っています．その定理をちゃんと証明して，いかに自然数が崇高な概念を実感してもらいたいと思います．

ペアノの公理系

自然数とは何かを考えるので， $0$ や $1$ といった記号は一旦使わないことにします．ただし，箇条書きの (1) や (2) などは容赦ください．

さて，ペアノの公理系を集合論の言葉で書き直したものが以下です．

定義

自然数の体系

集合 $N$ と， $o \in N$ と，写像 $N \to N$ が以下を満たすとき， $(N, o, σ)$ を自然数の体系と呼ぶ．

$\forall n \in N σ (n) \neq = o$ ．
$\forall n, m \in N σ (n) = σ (m) ⟹ n = m$ ．
$M \subset N$ が以下を満たすとき， $M = N$ ．
1. $o \in M$ ．
2. $\forall n \in M σ (n) \in M$ ．

無味乾燥な定義ですが，用語を定義すると雰囲気が伝わってきます．

定義

$(N, o, σ)$ を自然数の体系とする． $N$ の元を自然数と呼び，特に， $o$ を最初の自然数と呼ぶ．また， $n \in N$ に対する $σ (n) \in N$ を $n$ の後者（後継者）と呼び， $σ (m) = n$ を満たす $m \in N$ を， $n$ の前者と呼ぶ．

このように定義すると，ペアノの公理系の主張を言語的に理解できるようになります．

まず， $o \in N$ ゆえに，最初の自然数が $N$ に存在します．また， $σ$ が写像であることより，どんな自然数にも後者がただ一つ存在することになります． $1$ と加法の定義をのちにしますが，いずれ $σ (n) = n + 1$ であることが分かります．

P1 は， $o$ はどんな自然数の後者にはなりえない，と読めます．P2 は， $σ$ の単射性を表しますが，自然数に前者が存在するとしたら，ただ一つに限ることを意味します（一つって言葉，使っていいのかな）．P3 は後述しますが，（数学的）帰納法が正しい証明法であることと同値です．

最初の自然数 $o$ は origin の o で， $0$ に見立ていますが，人によって $1$ と考えても構いません．ただし， $0$ と考えた人と $1$ と考えた人で加法や乗法の定義が変わってくるので注意が必要です．この文書では $o$ は $0$ のつもりでいきます．

定義

記号 $0, 1, ..., 9$ を以下で定義する：

0369 : = o, : = σ (2), : = σ (5), : = σ (8) . 147 : = σ (0), : = σ (3), : = σ (6), 258 : = σ (1), : = σ (4), : = σ (7),

2桁以上の数はあとで定義します．

自然数の体系は存在するか

以下，ペアノの公理系を満たす $(N, 0, σ)$ が存在することを前提として話を進めます．気になるのは，そのような $(N, 0, σ)$ が数学の枠組（集合論）の中において具体的に存在するかです．主旨から外れるので，簡単に説明します（途端に難しくなるのでとばしてもOK）．自然数は空集合 $\emptyset$ だけで定義される，そんな話を聞いたことがあるでしょうか．

$0 : = \emptyset, 1 : = {0}, 2 : = {0, 1}, 3 : = {0, 1, 2}, \dots$ と，前の自然数全体を次の自然数とするという規則で自然数を定義し，このようにして定義できるものすべてを考えたいのです．しかし，そのようにして定まるモノ全体を，集合として扱えるかを議論しなくてはなりません．ここら辺になってくると，集合が存在するということはどういうことか，という話になってくるので詳しくは説明しませんが，ともかく，現代数学（集合論）では無限公理と呼ばれる性質

$\emptyset \in I$
$x \in I ⟹ x \cup {x} \in I$

を満たす集合 $I$ が少なくとも一つ存在することを仮定しています．無限公理を満たす $I, J$ に対し，共通部分 $I \cap J$ は無限公理を満たし，なおかつ $I, J$ よりも小さな集合です．それで，なるべく小さな無限公理を満たす集合を考えるのです．具体的には，無限公理を満たす集合 $J$ を固定し， $J$ の部分集合で無限公理を満たす集合 $I$ 全体の共通部分は， $J$ のとりかたによらずただ一つ定まるので，それを $ω$ とかきます．共通部分をとっている点から， $ω$ は無限公理を満たす集合で最小の集合です．ここで写像 $suc : ω \to ω$ を $x \mapsto x \cup {x}$ で定義すると， $(ω, \emptyset, suc)$ はペアノの公理系を満たすことが（そんなに簡単ではありませんが）証明できます．一応，現代数学ではこのようにして自然数を取り入れています．

余談ですが，このような話を聞くと， $0$ は空集合 $\emptyset$ のことだと思い込んでしまう人がいるかも知れませんが，例えば実数全体 $R$ の元としての $0$ は $\emptyset$ ではありません． $R$ の部分集合としての $N$ は， $N$ とまったく同じ性質をもった別の集合なのです．この話に関してはいつか説明しましょう．

基本命題

以下， $(N, 0, σ)$ を自然数の体系とし，基本的な性質を示していきます．

命題

数学的帰納法の原理

$A (n)$ を $n \in N$ についての命題（論理式）とする．このとき，以下を満たせば $\forall n \in N A (n)$ ．

$A (0)$ ．
$A (n) ⟹ A (σ (n))$ ．

先述しましたが，加法を定義すると $σ (n) = n + 1$ が分かるので，まさしく帰納法の原理を表しています．

証明

$A (n)$ を満たす $n$ 全体を $M$ とする．すなわち， $M = {n \in N ∣ A (n)}$ ．(1) より $A (0)$ が成り立つから $0 \in M$ ． $n \in M$ とすると $A (n)$ が成り立つから (2) より $A (σ (n))$ も成り立ち， $σ (n) \in M$ ．(P3) より $M = N$ ．ゆえに $\forall n \in N A (n)$ ．

命題

前者の存在

$N = {0} ⊔ σ (N)$ ．すなわち， $0$ 以外の自然数は前者をもつ．

$σ (N)$ はある $n \in N$ に対し $σ (n)$ と表せる自然数全体ですので，前者をもつ自然数全体を表します．また， $A ⊔ B$ は，集合 $A, B$ の直和を表す記号です．

証明

(P1)より， $0 \in / σ (N)$ ．よって ${0} \cup σ (N)$ は直和． $M = {0} ⊔ σ (N)$ とおくと， $0 \in M$ ．また， $n \in M$ とすると， $σ (n) \in σ (N)$ だから， $σ (n) \in M$ ．(P3)より $M = N$ ．

命題

$\forall n \in N σ (n) \neq = n$ ．

自然数とその後者は必ず異なることを主張しています．

証明

$M = {n \in N ∣ σ (n) \neq = n}$ とおく．(P1) より $σ (0) \neq = 0$ ． $n \in M$ とすると， $σ (n) \neq = n$ ． $σ$ は単射だから $σ (σ (n)) \neq = σ (n)$ ．ゆえに $σ (n) \in M$ ．(P3) より $M = N$ ．

ペアノの公理系をすべて用いる気持ちのよい証明です．

次のページで再帰性定理を証明します．