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

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 の "気持ち" を文章にするとこうだ、

1. o ∈ ℕ
   → 集合 ℕ には少なくともひとつの要素 o が在る
2. 任意の n ∈ ℕ について S(n) ∈ ℕ
   → 全て自然数には「次の数」が在って、「次の数」もまた自然数だ
3. 任意の n ∈ ℕ について S(n) ≠ o
   → ただし o は「次の数」にはならない、o の「前の数」は無い
4. 任意の 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 によって ℕ の各要素が別の要素に移る様を書き並べると。

左辺に着目すると、公理 2 により全ての要素を S によって移せるため k 個の要素全てが現れていることになる。
一方右辺に着目すると、公理 3 により右辺には o が現れないため高々 k-1 個の要素しか現れない。

S によって k 個の要素が高々 k-1 個の要素に移されるため、 鳩の巣原理 によりある i, j が存在し、nᵢ ≠ nⱼ, S(nᵢ) = S(nⱼ) となる。しかしこれは公理 4 に矛盾する。

よって仮定に誤りがあり、ペアノの公理を満たす集合 ℕ が存在すればそれは無限集合であることが示された。

まとめ

子供の質問にちゃんと答えるのは難しい。

私からは以上です。

*1:自然数を 1 から始める流儀もあるが、この記事では 0 から始まる前提で進める。1 から始まる流儀を採用しても以降の議論は同じになる

*2:余談だがペアノの公理を満たすような (ℕ, o, S) の組は他にもある、何なら無限に存在するらしい

10月の体重推移

ビーチサンダルが寒いので最近は靴を履くようになりました。
10月の体重の推移を振り返ります。

9月20日から10月31日にかけて 78.8kg→76.8kg (マイナス2.0kg) という推移でした。

6ヵ月間のグラフを見るとどうにか下降トレンドであることは分かる。

運動の記録

10月の消費は11,425kcalでした。目標通り10,000kcalを超えられてよかった。

ウォーキングとランニングを抽出した記録です。10月は合計で121kmでした。
こちらも目標にしていた100kmを超えられてよかった。

前回の振り返り

これまでの振り返りはこんな感じでした。

blog.mudatobunka.org

blog.mudatobunka.org

まとめ

エクササイズ時間・消費cal・移動距離ともに減ってます。
有酸素運動を減らして筋トレを増やしたのが要因です。が、単純に飽きつつある気がしますね。
気を引き締めてがんばります。

今月も消費10,000kcal, ウォーキング+ランニングで100kmを目指せたらいいかなと思います。

年内にあと6kg落として体重70kgを切りたい。がんばるぞ💪

私からは以上です。

JavaScript で割り算の商と余りを求める

JavaScript で整数同士の割り算をして商と余りを求める方法について解説します。

まず2つの整数 m, n を受け取って商と余りの組を返す関数 div を定義しましょう。

const div = (f=>(u=>u(u))(x=>f(y=>x(x)(y))))(g=>m=>n=>m>=n?(b=>b?1+g(m-n)(n)(1):g(m-n)(n)(0)):(b=>b?0:m));

はい、書けました。

試しに 14 ÷ 3 = 4 ... 2 を計算してみます。

「商: 4, 余り: 2」と正しく表示されていますね！

私からは以上です。

解説 (蛇足)

上記のコードをどのように錬成したか分かりたい人向けです。

まず再帰を使って普通に div を書きます。

/**
 * @param {number} m 割られる数
 * @param {number} n 割る数
 * @returns {[number, number]} 商と余りの組
 */
const div = (m, n) => {
  if (m >= n) {
    const [q, r] = div(m - n, n);
    return [1 + q, r];
  } else {
    return [0, m];
  }
}

div を実行すると div(14, 3) → [4, 2] のように2要素のタプル (配列) が返ってきます。
0番目の要素が商で、1番目の要素が余りです。

分割代入は Internet Explorer で動かない ので愚直なブラケット記法に書き換えます。

const div = (m, n) => {
  if (m >= n) {
    return [1 + div(m - n, n)[0], div(m - n, n)[1]];
  } else {
    return [0, m];
  }
}

ブレース {} が美しくないので if 文を三項演算子で書き換えます。

const div = (m, n) => m >= n
  ? [1 + div(m - n, n)[0], div(m - n, n)[1]]
  : [0, m];

ブラケット [] も美しくないのでタプルを三項演算子で書き換えます。

const div = (m, n) => m >= n
  ? (b => b ? 1 + div(m - n, n)(1) : div(m - n, n)(0))
  : (b => b ? 0 : m);

カリー化 🍛 します。

const div = m => n => m >= n
  ? (b => b ? 1 + div(m - n)(n)(1) : div(m - n)(n)(0))
  : (b => b ? 0 : m);

div 関数に引数 g を追加して div_ 関数に書き換えます。

const div_ = g => m => n => m >= n
  ? (b => b ? 1 + g(m - n)(n)(1) : g(m - n)(n)(0))
  : (b => b ? 0 : m);

おもむろに Z コンビネータを持ち出します。

const z = f => (u => u(u))(x => f(y => x(x)(y)));

z と div_ をがっちゃんこします。

const div = z(div_);

これだけでは味気ないので z と div_ をそれぞれ展開します。

const div = (f => (u => u(u))(x => f(y => x(x)(y))))(
  g => m => n => m >= n
    ? (b => b ? 1 + g(m - n)(n)(1) : g(m - n)(n)(0))
    : (b => b ? 0 : m)
);

余分なスペースや改行を取り除いてあげれば完成！

const div = (f=>(u=>u(u))(x=>f(y=>x(x)(y))))(g=>m=>n=>m>=n?(b=>b?1+g(m-n)(n)(1):g(m-n)(n)(0)):(b=>b?0:m);

いい感じですね (？)

解説の解説 (蛇足の蛇足)

「タプルを三項演算子で書き換える」とは？

タプルとは複数の値の組を保持しておけるデータ構造です。キーに名前が付いていない構造体 (キーを連番で管理している構造体) と見ることもできます。
(そもそも JavaScript にはタプルが無いので ['foo', 'bar'] のように配列を使っていましたが)

さて、ここで三項演算子を思い出して以下のような関数を書いてみましょう。

const f = b => b : 'foo', 'bar';

この関数 f は以下のような振る舞いをします。

f(true)   // → 'foo'
f(false)  // → 'bar'

引数に応じて 'foo' または 'bar' を返しています。
引数によって 'foo', 'bar' のどちらも返せると云うことは、関数 f は内部的に ('foo', 'bar') の組を保持しているということです。これって2要素のタプルと実質的に同じことですよね？

というわけで一般化すると、2要素 (x, y) を保持するタプルは三項演算子を使って b => b ? x : y と書けます。
要素を取り出すときは引数に true, false を渡してもいいのですが、1, 0 を渡しても同じように動作します。

const f = b => b : 'foo', 'bar';
f(1)  // → 'foo'
f(0)  // → 'bar'