κeenのHappy Hacκing Blog | Lispエイリアンの狂想曲

オーディナルの話とカーディナルの話

ちょっとオーディナルの話をしよう。ついでにカーディナルの話もしよう。 特に何も知らなくても分かる内容。だけど文脈を知ってると伝えたいことが伝わる筈。

まずは何もないところから始めよう。机もスマホもパソコンンもない。空気もないし数字もない、自然数もない。

何もない。

「何もない」、もうちょっと正確にいうと「何も要素がない集合」のことを覚えているだろうか。中学校で習った気もする。

\[ \emptyset \]

と書く。 さて、ここから始める。何もないところから何か作れるだろうか。まずは $\emptyset$ を要素に持つ集合、

\[ \{\emptyset\} \]

がある。これは要素を1つだけ持つので $\emptyset$ とは異なる集合だ。これをさらに進められないだろうか。例えば

\[ \{\emptyset, \emptyset\} \]

とか。これではダメだ。結局2つの要素が同じ $\emptyset$ なので要素を取り出してみても $\{\emptyset\}$ から取り出したときと区別がつかない。 何か $\emptyset$ とは別のものが必要だ。 $\emptyset$ とは別のもの。既に出てきた。 $\{\emptyset\}$ だ。

\[ \{\emptyset, \{\emptyset\}\} \]

これで $\emptyset$ とも $\{\emptyset\}$ とも異なる集合が作れた。ここまできたらあとはもうパターンだ。「次」が欲しければ今までに出てきた集合を全部$\{\}$に放り込めばいい。

\[ \{\emptyset, \{\emptyset\}, \{\emptyset, \{\emptyset\}\}\} \]

「次(Successor)」を求める手続を $\mathbf{succ}$ と書くとすると、集合の合併 $\cup$ を用いて

\[ \mathbf{succ} (x) = x \cup \{x\} \]

と書ける。この $\mathbf{succ}$ 、必ず新たな集合を生み出している。これはつまり、任意の $x$ に対して $\mathbf{succ}(x)$ は $\emptyset$ にはならないし、 $x \not= y$ のとき $\mathbf{succ}(x) \not=\mathbf{succ}(y)$ でもある。 このようなものをご存知ないだろうか(細かいことを言うと帰納法の原理も必要だが飛ばす)。

自然数だ。

  1. $\emptyset$ がある
  2. 任意の自然数 $x$ に $\mathbf{succ}(x)$ がある
  3. $\emptyset$ はいかなる自然数 $x$ の $\mathbf{succ}$ でもない
  4. $x \not= y$ のとき $\mathbf{succ}(x) \not=\mathbf{succ}(y)$
  5. (帰納法の原理が成り立つ)

これは、こういうことだ。

\[ \begin{eqnarray} 0 & = & \emptyset \\\
1 & = & \{\emptyset\} \\\
2 & = & \{\emptyset, \{\emptyset\}\} \\\
3 & = & \{\emptyset, \{\emptyset\}, \{\emptyset, \{\emptyset\}\}\} \\\
& \vdots & \end{eqnarray} \]

ここでは #0は自然数 としてある。 さて、今我々は何もないところから出発してDASH村のように自然数を作り上げた。

この自然数、面白い性質がある。 0 は 1の要素( $0 \in 1$) だ。 1 は 2 の要素 ( $1 \in 2$ )だし、0も2の要素 $0 \in 2$ だ。もうちょっというと、 $x \in y$ かつ $y \in z$ のとき、 $x \in z$も成り立つ。 この関係で自然数には順序がつく。つまり、自然数は順序数(オーディナルナンバー)だ。再度、オーディナルナンバーであるところの自然数を列挙するとこうなる。

\[ \emptyset, \{\emptyset\}, \{\emptyset, \{\emptyset\}\}, \{\emptyset, \{\emptyset\}, \{\emptyset, \{\emptyset\}\}\}, … \]

これに見覚えがあるならオーディナルの話はこれで十分。

さて、カーディナルの話をしよう。 $\emptyset$ は要素が0個。 $\{\emptyset\}$ は要素が1つ。 $\{\emptyset, \{\emptyset\}\}$ は要素が2つ。 要素数の話だ。これは別に自然数だけでなくて、 $\{2, 4\}$ のように自然数ではない集合でも要素数という概念はある。要素数をどう数えようか。一応要素数に濃度という名前もついている。 これにも自然数が使える。2と $\{2, 4\}$ を $\{2, 4\}$ を $2 -\emptyset$ と $4 - \{\emptyset\}$ と1対1に対応づければ、「$\{2, 4\}$と 2は同じ濃度を持つ」といえる。 このように濃度を数えるための数を基数(カーディナルナンバー)という。

手で数えられる(有限な)ものは面白みがない。無限なものについて考えよう。例えば今我々が作った自然数は常に $\mathbf{succ}$ がとれるので無限の要素がある。 まだ作ってないが、自然数だけでなく整数にも有理数にも実数にも無限の要素がある。これらの「無限」は全て同じ大きさなのだろうか、つまり同じ濃度なのだろうか。 結論からいうと自然数と整数と有理数は同じ濃度を持つ。全て自然数と1対1の対応が取れるということだ。一方実数は対応が作れない。実数の濃度の方がずっと大きい訳だ。つまり、無限の間にも大小関係がある。実は自然数は無限の中でも一番小さい。この一番小さい基数のことをヘブライ文字からとって

\[ \aleph_0 \]

と書く。これも見覚えがあればカーディナルの話はこれにて重畳。

そういえばこういう「紙の上でDASH村」を気に入ったならこの本がお勧め。

コンピュータは数学者になれるのか? -数学基礎論から証明とプログラムの理論へ- | 照井一成 |本 | 通販 | Amazon

Written by κeen
Later article
Rust in Production