自然数の集合が無限集合であることを証明する

6歳になる子供がいる。ある日、自転車に乗りながらこんな話をした、

👦「ねぇ、数字って数えていったらどこまで続くの？」
👨『いい質問だね、どう思う？』
👦「うーん、どこまでも続く？」
👨『そう、数字はどこまでも続くから 1, 2, 3, ... と数えていっても終わりはないんだよ』

本当だろうか？確かめてみよう。

自然数の集合 ℕ は無限集合であると定義されているか？

自然数の定義はいろいろあり得るが、代表的かつ簡単な定義はこうだ。

次の公理を満たす集合 ℕ の元を自然数と云う

集合 ℕ と定数 o と関数 S について、
　1. o ∈ ℕ
　2. 任意の n ∈ ℕ について S(n) ∈ ℕ
　3. 任意の n ∈ ℕ について S(n) ≠ o
　4. 任意の n, m ∈ ℕ について n ≠ m ならば S(n) ≠ S(m)

この公理をペアノの公理と云う。

普段、私たちが素朴に "自然数" と呼んでいるものはこの公理を満たす。
定数 o とは 0 のことで。関数 S とは「n に対して n の次の数を返す関数」のことだ。

集合 ℕ : 自然数の集合、0, 1, 2, ...
定数 o : 0
関数 S : S(n) = n + 1

こうなる。 *1 *2

さて自然数の定義を見てみたが「自然数は無限にある」とは書かれていなかった。
定義にも公理にも無い以上、自然数が無限にあると主張するには証明が必要だ。

というわけで証明してみよう。

ペアノの公理の気持ちを理解する

証明にはペアノの公理を使う。証明に取りかかるまえにペアノの公理の気持ちを理解しておこう。
公理 1~4 の "気持ち" を文章にするとこうだ、

o ∈ ℕ
→ 集合 ℕ には少なくともひとつの要素 o が在る
任意の n ∈ ℕ について S(n) ∈ ℕ
→ 全て自然数には「次の数」が在って、「次の数」もまた自然数だ
任意の n ∈ ℕ について S(n) ≠ o
→ ただし o は「次の数」にはならない、o の「前の数」は無い
任意の n, m ∈ ℕ について n ≠ m ならば S(n) ≠ S(m)
→ 「次の数」が他の人と被ることはない

さらにペアノの公理の集合 ℕ を絵に描いてみよう、

graph LR;
    O((o)) -->|"S(o)"| N1(("n₁"));
    N1(("n₁")) -->|"S(n1)"| N2(("n₂"));
    N2(("n₂")) -->|"S(n₂)"| N3(("n₃"));
    N3(("n₃")) -->|"S(n₃)"| NEXT[どこまでも続く...];

o から始まって次の数 (関数 S による変換) を辿っていくとどこまでも続く。この「次の数チェーン」を辿った全体が自然数の集合 ℕ になる。

自然数が無限にあることは自明か

先ほどの絵を見ていると「うーん、自然数が無限にあるのは自明だなぁ」と思う読者もいるんじゃないか。
気持ちは分かる。さきほどの絵がきれいすぎるのが良くない。

今度はもう少し汚い絵を描いて「自然数ってもしかしたら有限かも」という気持ちも味わってみよう。
次に見ていくのはどれも "このようにはならない" という例である。

次の数チェーンが途切れる

もしも次の数チェーンが途中で途切れていたらどうだろう。その場合は「自然数は有限個」ということになりそうだ。

graph LR;
    O((o)) -->|"S(o)"| N1(("n₁"));
    N1(("n₁")) -->|"S(n₁)"| N2(("n₂"));
    N2(("n₂")) -->|"S(n₂)"| N3(("n₃"));
    N3(("n₃")) --->|...| Nz(("nₓ"));

nₓ には次の数が無い。なのでチェーンはここで終わり。

ということにはならない。公理 2 が「全ての自然数に次の数があり、かつ、次の数もまた自然数である」ことを要請してくれている。

次の数チェーンが袋小路にはまる

次の数チェーンの先がループになっている場合も問題がありそうだ。

graph LR;
    O((o)) -->|"S(o)"| N1(("n₁"));
    N1(("n₁")) -->|"S(n₁)"| N2(("n₂"));
    N2(("n₂")) -->|"S(n₂)"| N3(("n₃"));
    N3(("n₃")) --->|...| Nz(("nₓ"));
    Nz(("nₓ")) -->|"S(nₓ)"| N2(("n₂"));

全ての自然数に次の数があるという公理を満たしつつ有限個になってしまった。

このようなことも起こらないはずだ。公理 4 によって次の数が被らないことが要請されている。 S(n₁) と S(nₓ) の矢印がどちらも n₂ に向いているのは公理 4 に反している。

次の数チェーンが元の場所に戻ってくる

次の数チェーンがぐるっと一周して元の場所 o に戻ってくる場合はどうだろう。

graph LR;
    O((o)) -->|"S(o)"| N1(("n₁"));
    N1(("n₁")) -->|"S(n₁)"| N2(("n₂"));
    N2(("n₂")) -->|"S(n₂)"| N3(("n₃"));
    N3(("n₃")) --->|...| Nz(("nₓ"));
    Nz(("nₓ")) -->|"S(nₓ)"| O((o));

チェーンは途切れていないし、次の数が被ってもいない。でもループができてしまった。

やはりこのようなことも起こらない。公理 3 が「o は次の数にならない」ことを要請している。 S(nₓ) の矢印が o に向いているのはおかしなことだ。

ここまでどうにか自然数有限個の危機は回避してきた。が、自然数が無限に存在していることは全然自明ではない気がしてきた。ちゃんと証明して心から安心したいところだ。

自然数の集合 ℕ が無限集合であることを証明する

というわけでようやく証明にとりかかろう。

背理法で示す。ペアノの公理を満たす有限集合 ℕ が存在し、その要素数が k であると仮定する。

関数 S によって ℕ の各要素が別の要素に移る様を書き並べると。

$\mathbb N \ni o \rightarrow n_{\, w} \in \mathbb N$
$\mathbb N \ni n₁ \rightarrow n_{\, x} \in \mathbb N$
$\mathbb N \ni n₂ \rightarrow n_{\, y} \in \mathbb N$
$\vdots$
$\mathbb N \ni n_{\, k-1} \rightarrow n_{\, z} \in \mathbb N$