世界のはじめに空集合が存在した。これを0と名付けよう。

世界のはじめに、空集合が存在した。
これを"0"と名付けよう
そして、無限に続く自然数が生まれた。

自然数とは数学的（詳しく言えば集合論的）にどのように構成されるのか、これをRubyによる実装を踏まえて紹介したいと思います。

Cやpythonなどの何らかのプログラミング言語を少しでも触ったことがあれば理解はできるかと思います。

Rubyに詳しい方は、自然数の構成について興味を持っていただければ、数学に詳しい方は、Rubyのプログラミングについて興味を持っていただければ嬉しいです。両方に詳しい方は、是非訂正をいただければと思います。

世界のはじめに、空集合が存在した。

数学の世界のはじめには、空集合が存在していたそうです。(空集合の公理）

（注：「公理」とは、数学などの体系において議論の前提となる仮定のことです。つまり、空集合はなぜ存在するのか？ではなく、空集合は存在するものとして数学の議論を進めるのです）

この天から降ってきた空集合から出発して、自然数を構成していきます。方法はたくさんあるのですが、最も代表的なフォン・ノイマンの構成法を紹介したいと思います。

世界に0が生まれた

まず、空集合$\varnothing$に"0"という名前をつけます。これで0の誕生です。

0 := \varnothing

一般的には、自然数は1から始まる場合が多いですが、このような集合論的な議論では自然数は0から始まる場合が多いです。

これをRubyで表現すると、

def _0
  []
end

Rubyで実装する上で0を直接定義するわけには行かないので、これから自然数を_0, _1, _2, ....と定義していきます。空集合は、空配列で表現することとしましょう。

（注：Cやpythonとは違ってrubyはreturn文を明示的に書く必要がないことに気をつけましょう。上記の_0という関数(正確にはメソッド)は空配列[]を返す関数です)

次に1が生まれた。

0が出来たので、0をもとに1を作ることができます。

1 := 0 \cup\{0\}

$\cup$とは、和集合を表し、二つの集合を合併します。
例えば、

\{a, b, c\} \cup \{d, e\} = \{a, b, c, d, e\}

このように和集合の計算が行われます。

{$0$}は、0を要素にもつ集合で、$0$自身も集合（空集合）であることに注意しましょう。つまり、

1 := 0 \cup\{0\} = \varnothing \cup\{\varnothing\} = \{\varnothing\}

{$\varnothing$} は空集合を要素とする集合で、空集合とは異なります。

プログラミングに慣れている方は、Rubyのソースコードを見るとイメージが湧くかと思います。

def _1
  _0 + [_0]
end

# irb(main)> _1
# => [[]]

_0 自身も配列であることに気をつけましょう。配列の+ は配列同士の結合を表します。

そして、無限に続く自然数が生まれた。

1が生まれたので、1をもとに2を作ることができます。

2 := 1 \cup\{1\} = \{\varnothing\} \cup \{\{\varnothing\}\} = \{\varnothing, \{\varnothing\} \}

Rubyでは、

def _2
  _1 + [_1]
end

# irb(main)> _2
# => [[], [[]]]

このようになります。

このような手続きを繰り返すことで、自然数を無限に続けて作ることができます。
具体的には、自然数$n$に対して、$n$の 次の数 (successor) $suc(n)$は、

suc(n) := n \cup\{n\}

と定義します。

（注：要するに、$suc(n)$とは$n+1$のことなのですが、この世界にはまだ、"+"は生まれていないのです。

Rubyでは、

def suc(_n)
  _n + [_n]
end

# irb(main)> suc(_1)
# => [[], [[]]]
# irb(main)> suc(_1) == _2
# => true

と書くことができます。

method_missingを使って動的に定義する

ここの章は、若干話を逸らしてrubyのメタプログラミングの話をします。
ここまでは _1 や _2 を逐一定義していましたが、これを無限に続く自然数の分を定義するのは不可能です。
そこで、method_missingメソッドを用いることで動的に関数（正確にはメソッド）を定義することができます。

定義されていないメソッドが呼ばれた時、Rubyはmethod_missingを呼びます。これを独自に定義することで、未定義のメソッド名に対しても特定の動作を実行させることができます。

def method_missing(name)
  if name.to_s =~ /^_(\d+)$/
    n = $1.to_i
    (1..n).reduce(_0) { |sum, _| suc(sum) }
  else
    super
  end
end

name.to_s =~ /^_(\d+)$/ の部分では、呼ばれた未定義のメソッド名が、_数字の形式かを判定しています。
n = $1.to_i の部分でメソッド名の数字の箇所を抽出して整数に変換しています。
(1..n).reduce(_0) { |sum, _| suc(sum) } この部分はやや技巧的ですが、_0 を初期値としてsuc をn回作用させています。すなわち、_n となります。

そして、足し算ができるようになった。

ようやく自然数が出来上がりました。しかし、これだけでは単に数が集まっただけにすぎません。実際に計算ができないと面白くありません。

その前に準備として、$suc$の逆関数$pre$を定義しておきます。

n \neq 0 \;\; pre(n) = suc^{-1}(n)

堅苦しいように見えますが、$pre(3)=2$、$pre(2)=1$のように前の数 を取り出す関数です。0に対しては定義できないことに気をつけましょう。

Rubyで実装するには、

def pre(_n)
  _n.last
end

_nの一番最後の要素を取ってくると、実はpre(_n)となっています。

これは具体的に書き下してみるとわかります。

1 := 0 \cup\{0\} = \varnothing \cup \{0\} = \{0\} \\
2 := 1 \cup\{1\} = \{0\} \cup \{1\} = \{0, 1\} \\
3 := 2 \cup\{2\} = \{0, 1\} \cup \{2\} = \{0, 1, 2\} \\
4 := 3 \cup\{3\} = \{0, 1, 2\} \cup \{3\} = \{0, 1, 2, 3\} \\

確かに末尾の要素が自分自身の前の数になっていることがわかるかと思います。

（注：数学的には集合の要素には順序はついていないので、数学的にはおかしな説明ですが、プログラミングのための説明と捉えてください。

さて、ようやく足し算を定義していきましょう。
二つの自然数n, m に対して、n+mを定義します。add(n, m)と書くこととします。

add(n, m) = 
  \begin{cases}
    n \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \mathrm{if}\; m = 0 \\
    suc(add(n, pre(m))) \;\;\; \mathrm{otherwise}
  \end{cases}

定義からこれが足し算になってるかはすぐにはわかりにくいですが、具体例を見てみましょう。

まず、$m=0$のときをみてみると、次のことが明らかです。

add(n, 0) = n

たしかに、$n+0=n$なので、予想通りの計算結果です。

次に$m=1$をみましょう。

add(n, 1) = suc(add(n, pre(1)) = suc(add(n, 0)) = suc(n) = n+1

定義に従って計算すると確かに$n+1$になっていることがわかります。

$m=2$も計算してみましょう。

add(n, 2) = suc(add(n, pre(2)) = suc(add(n, 1)) = suc(suc(n)) = n+2

$add(n, 1)=suc(n)$ ということが$m=1$の時にわかっているのでそれを代入しています。

このことを繰り返していくと、$add(n, m)$は$n$に対して、$suc$を$m$回計算する定義になっていることがわかるかと思います。その計算結果は$n+m$になることがわかります。

次に、Rubyのよる実装をしてしまいましょう。

def add(_n, _m)
  if _m == _0
    _n
  else
    suc(add(_n, pre(_m)))
  end
end

# irb(main)> _3 == add(_1, _2)
# => true

数学の定義どおりに、プログラミングできるかと思います。

そして、整数へ

ようやくこここまできて、自然数と簡単な計算がこの世界に生まれました。この後、整数や有理数、実数などが世界に生まれていくのですが、それはまた別の話...

ソースコード全文

def method_missing(name)
  if name.to_s =~ /^_(\d+)$/
    n = $1.to_i
    (1..n).reduce(_0) { |sum, _| suc(sum) }
  else
    super
  end
end

def _0
  []
end

def suc(_n)
  _n + [_n]
end

def pre(_n)
  _n.last
end

def add(_n, _m)
  if _m == _0
    _n
  else
    suc(add(_n, pre(_m)))
  end
end

余談：swiftのものはすでにあったみたいです https://qiita.com/taketo1024/items/2ab856d21bf9b9f30357

U-TOKYO AP Advent Calendar

こちらの投稿は、東京大学応用物理学系の有志によるアドベントカレンダーの投稿でした。言い出しっぺの @snowhork がトップバッターを担当させていただきました！

筆者が所属する計数工学科は数学・情報・物理を３本柱とする学科です。今回の記事で、純粋数学とプログラミングが交わるところに興味持っていただければ幸いです！