「無」から生まれる自然数~Clojureで空集合から考える自然数~

はじめに

聖書の創世記1章1-8節に「はじめに神は天と地とを創造された。」という記述があります。この文によれば、何もないところから、今の世の中を作ったされているようです。また偶然なのか、仏教の般若心経でも色即是空、空即是色とあり、「この世の物や事象(色)には実体というものがない(空)・実体のないもの(空)が物や現象を作っている」とあります。どうやら世界の理は「無」からあらゆるものが生まれたようです。

我々も理にならって無から何かを生み出して見ましょう。今回はペアノの公理を利用して空集合から自然数となる世界を構築してみる記事です。

自然数って?

我々は幼いときからずっと使っている$0,1,2,3,4,5\dots$といった自然数は一体どういったものなのでしょうか。1とは? 2とは?、そもそもなんでしょうか。どういったものに対して、1という数を用いればよろしいのでしょうか。

ペアノの公理

そんな疑問に関して、19世紀にジュゼッペ・ペアノという数学者が自然数がどういう特徴を持っているかという公理を発見しました。

1. ${\bf 0} \in \mathbb{N}$ である。
2. 任意の$a \in \mathbb{N}$において、後者である$succ(a) \in \mathbb{N}$が存在する。
3. $a,b \in \mathbb{N}$のとき、$a \neq b$ならば、$succ(a) \neq succ(b)$である。
4. ${\bf 0}$は、いかなる自然数の後者ではない。すなわち、 $a \in \mathbb{N}, succ(a)={\bf 0}$ となるような$a$は存在しない。
5. ${\bf 0}, a, succ(a)$が、それぞれある性質を満たすのであれば、自然数は、その性質を満たす。

意味が分からないですよね。我々の普段の感覚言えば

• $0$は自然数だよ
• $succ(0)$は計算すると$1$が、後者(次の数)として導く関数があるよ
• $succ(x), succ(y)$が等しくなるのって、$x,y$が等しくないとダメだよね($13=1020$みたいなことは無いよ)
• 後者をし続けて、0になるようなことはないよ。つまり、0,1,2,3,4,5...となって、5の次がまた0になったりしないよ。
  みたいなことを小難しくいっています。

これが面白いのが、自然数とはペアノの公理を満たしたものを自然数と呼ぶことができるといっていることです。すなわち、我々が普段見慣れているような$1,2,3 \dots$みたいなものでなくても良いということになります。

無から有を築いてみよう

実際にペアノの公理のおかげで、別に数字でなくても、それを自然数とみなすことができることが知られています。

では、冒頭で述べたように「無」から築いてみましょう。

1. 空集合$\{\}$を$\mathbb{N}$の要素とする。
   つまり $\{\} \in \mathbb{N}$。
2. 後者関数 $succ(x) := x \cup \{x\}$ とし、$succ(x):\mathbb{N} \rightarrow \mathbb{N}$とする。

解説

1で空集合${}$を自然数だと宣言しており、空集合$\{\}$は、自然数で言う$0$に該当します。
2は少し難しいですね。空集合は数字そのものではないので、$+1$されるような関数を考えて上げる必要があります。そこで出てくるのが$succ(x) := x \cup \{x\}$です。定義だけだと分かりにくいので、具体例で確かめてみましょう。

$$\begin{align} succ(\{\}) &= \{\} \cup \{\{\}\} \text{ sucの定義より} \\ &= \{\{\}\} \\ succ(succ(\{\})) &= \{\{\}\} \cup \{\{\{\}\}\} \text{ sucの定義より} \\ &= \{\{\}, \{\{\}\}\} \end{align}$$

となります。
ちょっと見にくいですが、これは$\{\}, \{\{\}\}, \{\{\}, \{\{\}\}\}$が、それぞれ$0,1,2$といったように対応しており、次の数は前の数を全て集合に含むようになっています。
これにより、数字で言う$1<2$という比較が$\{\{\}\} \subset \{\{\}, \{\{\}\}\}$といったように集合の包含関係で比較をすることができるようになります。

このように定義してしまえば、ペアノの公理にあるように自然数の性質を満たすことができます。工夫してあげたことで数字で扱っていた大小も集合で表現できるようになったのが面白いですね。

いざ、プログラムで挑戦

さてここまで理解できたのであれば、実際に自然数をプログラムで表現してみましょう！今回はLispの1つであるClojureと言う言語で書いてみます。

;; ペアノの公理の再現
(def empty-set #{})
(defn succ [x]
    (conj x x))


;; チェック用に自然数にあたるものを定義
(def _0 empty-set)
(def _1 #{#{}})
(def _2 #{ #{} #{#{}}})

;; 後者関数のチェック
(= _1 (succ empty-set)) ;; true
(= _2 (succ (succ empty-set))) ;; true

;; 大小比べ
;; 2 > 1と同等の比較
(contains? (succ (succ empty-set)) (succ empty-set)) ;; true

プログラムの説明

初めに

• (def empty-set #{}) で空集合の$\{\}$を表現
• (conj x x) というxの集合にxを加えるという処理をする関数をsucという名前で定義
  をやっています。

以降は、succ関数がちゃんと定義できているかを(= _1 (succ empty-set))でチェックしたり、大小の比較を contains? という関数で確かめていたりします。

感想

集合を使って自然数を定義できることを確かめました。空集合から意味のあるものを定義できるのは面白い発見でした。あとClojureで書いてみたんですが、思ったより見通しの良いコードになって嬉しかったです。ここまで読んでいただきありがとうございました。

参考

天地創造
色即是空
ペアノの公理
Prologプログラミング: 自然数を定義する