集合論の言葉による自然数の表現
ここまでで集合論のいくつかの公理 (ルール) を持ち出すことで、すでにモノが存在するなら、そこから外延的記法を使って記述できるいくつものモノもまた存在することが示された。今回はこれを利用して、自然数を定義する。このシリーズでは「すべてのモノは集合である」ような論理を扱っているので、当然ながらこれから定義する自然数もすべて集合である。
空集合の公理
この記事では自然数を定義しようと思うのだが、じつは今まで導入した公理だけではまだ定義できない。なぜかというと、まだ何一つとしてモノ (集合) が存在することを示せていないのである。思い出してみてほしいが、これまで導入した公理は
- 外延性の公理
- 対の公理
- 和集合の公理
このような理由から、無条件にある集合の存在を認める公理である空集合の公理を導入する。
公理\[\exists x\forall y[y\not\in x]\]
すなわち、「どんなモノ (集合) も属していない集合」が存在する。
この公理によって存在が認められる「どんなモノ (集合) も属していない集合」を空集合とよぶ。外延性の公理よりそのようなモノ (集合) はただ一つしかないので、その唯一のモノを\[\emptyset\]と書く (書籍によっては ∅ やギリシャ文字 $\phi$ を使うこともあるだろう)。外延的記法を使えばこの空集合のことを\[\{\}\]とも書ける。
自然数の定義
準備が整ったので自然数を定義していく。このシリーズで扱う集合論の言葉では「すべてのモノは集合である」ので、当然これから定義する自然数もすべて集合である (そのように定義しなくてはならない)。ただし、四則演算や大小関係などを集合として定義する準備はまだできていないので、これらの定義は後の記事で行うこととし、今回の記事では自然数そのものを用意するに留める。
さっそく先ほど存在を認めた空集合 $\emptyset$ を使うことにしよう。この空集合 $\emptyset$ のことを自然数 $0$ として扱うことにする (注: 後の説明を簡潔にするために0も自然数に含める)。つまり\[0=\emptyset=\{\}.\]こうすると、自然数 0 は集合 $\emptyset$ として存在するので「すべてのモノが集合である」ような論理に登場することができる。
さて、次は「0の次の自然数 (通常は 1 と呼ばれる)」を定義しよう。0 ($\emptyset$) の存在がわかっているので、対の公理から「0だけが属する集合」である $\{0\}$ も存在が確定する。これを自然数 $1$ として扱うことにする。つまり\[1=\{0\}=\{\emptyset\}=\{\{\}\}.\]
では「1の次の自然数 (通常は 2 と呼ばれる)」はどうしようか。これまでの流れで「1だけが属する集合」である $\{1\}=\{\{0\}\}=\{\{\{\}\}\}$ を 2 としようと思う人もいるかもしれない。発想としては有りだが、集合論全体をすっきりさせようとするとこれから述べる方法に従う方がよい。その方法とは、「$n$ の次の数」を「$n$ に属するモノがすべて属し、$n$ そのものも属し、それ以外は属さない集合」である $n\cup\{n\}$ とするのである。つまり\[(\text{$n$ の次の自然数})=n\cup\{n\}\]とする。これに従うと1以降の自然数は\[\begin{array}{rclcl}1&=& 0\cup\{0\}=\{\}\cup\{0\}&=&\{0\}\\ 2&=&1\cup\{1\}=\{0\}\cup\{1\}&=&\{0,1\}\\ 3&=&2\cup\{2\}=\{0,1\}\cup\{2\}&=&\{0,1,2\}\\ &\vdots&&&\end{array}\]となり、どの自然数も「自身以前の自然数が属して、それ以外のモノが属さない集合」として定義される。$n$ が集合として存在すれば対の公理と和集合の公理により $n\cup\{n\}$ も存在するので、この方法でどの自然数も確かに存在する集合として定義できたことになる。以降は 0 ($\emptyset$) およびそこから上の操作で作ることができる集合 1,2,3,... が自然数であるとし、そのように自然数と言う言葉を用いる。
$n$ の次の自然数を $n\cup\{n\}$ とする利点としては
- 自然数 $n$ に属するモノの個数は $n$ となる
- 自然数の大小関係 $n\lt m$ が $n\in m$ に一致する
すべての自然数が属する集合
以上から、どんな自然数についても、それを集合として定義して存在を示すことができた。だが、まだ「すべての自然数が属し、それ以外のモノが属さない集合 (つまり 0 ($\emptyset$) とそこから上の操作で作れる 1,2,3,... が属し、それ以外のものが属さない集合)」の存在を示していない。通常の数学ではこの集合を当たり前に使っているので、是非とも存在することを確かめたい。
前回の記事でも述べたが、「すべての自然数が属する集合」のように無限にモノが属する集合はこれまで挙げた公理ではその存在を証明できない。そこで、無限公理を導入する。
公理\[\exists x[\exists y[y\in x \land \forall z[z\not\in y]]\land \forall w[w\in x \to \exists v[v\in x \land \forall u[u\in v\leftrightarrow u=w \lor u\in w]]]]\]
すなわち、「すべての自然数が属する集合」が存在する。
ここで注意すべきは、この公理で存在が証明されるのは「すべての自然数が属する集合」であって、「すべての自然数が属して、それ以外のモノが属さない集合」ではない。あくまで「すべての自然数が属する集合」が1つは存在すると言っているのである。ここから「すべての自然数が属して、それ以外のモノが属さない集合」の存在を示すには後の記事で紹介する分出公理か置換公理を使うのだが、その証明はやや複雑である。そのため、このシリーズ内では「すべての自然数が属して、それ以外のモノが属さない集合」が存在する理屈は扱わず、その存在を認めてしまうことにする (本シリーズとは無関係の記事でいずれ解説する予定)。
以降では「すべての自然数が属して、それ以外のモノが属さない集合」を「自然数集合」と呼び $\omega$ と書くことにする (文脈によっては $\boldsymbol{\rm N}$ や $\mathbb{N}$ で表すことも多いだろう)。
数学的帰納法
さて、ここで1つ根本的な問いとして「今作った $\omega$ は自然数集合として機能するのか」を問うてみる。言い換えると、「$\omega$ に属するモノだけで作られる自然数と言う構造が、素朴な意味で自然数と呼んでいるモノが担っていた役割をすべてこなせるのか」ということだ。ただ、この問題にまじめに解答しようとしたら、先ほど棚上げした $\omega$ の存在証明に触れなくてはならない。そこで、ここでもやはり理屈を抜きにして「$\omega$ は自然数が果たすべき役割をひととおり果たせる」と結論だけ述べる。
特にここで述べておきたいのは数学的帰納法が機能するという点である。つまり「$\omega$ に属する任意の $x$ に対して $\psi(x)$ が成立する」ことを証明したいとき、
- $\psi(0)$ が成立する
- $x$ について $\psi(x)$ が成立するという仮定から $\psi(x\cup\{x\})$ の成立が導ける
命題0でない自然数には 0 が属する。
(証明) 「$0\in x$ または $0=x$」(以下、$\psi(x)$ と書く) が任意の $x\in\omega$ に対して成立することを数学的帰納法を用いて示す。まず $0=0$ は明らかだから $\psi(0)$。
次に $\psi(x)$ を仮定する。つまり $0\in x$ か $0=x$ のいずれかが成立することを仮定する。ここで、もし $0=x$ であれば $0\in\{x\}$ であるので $0\in x\cup\{x\}$ となり $\psi(x\cup\{x\})$。もし $0\in x$ であればやはり $0\in x\cup\{x\}$ となり $\psi(x\cup\{x\})$。以上よりいずれにしても $\psi(x\cup\{x\})$。
もういくつか、後々重要になる定理を、数学的帰納法を用いて証明しておく。
命題0でない自然数はみなある自然数の次の数である。
(証明) 「ある自然数 $y$ が存在して $x=y\text{の次の数}$ または $x=0$」(以下、$\psi(x)$ と書く) が任意の $x\in\omega$ に対して成立することを数学的帰納法を用いて示す。まず $0=0$ は明らかだから $\psi(0)$。
次に $\psi(x)$ を仮定する。このとき $x\text{の次の数}=x\text{の次の数}$ は明らかだから $\psi(x\text{の次の数})$。
定理$\omega$ に属する $z$ について、$x\in y$, $y\in z$ ならば $x\in z$。
(証明) 「どんな $x$, $y$ についても $x\in y$, $y\in z$ が満たされるならば $x\in z$」(以下、$\psi(z)$ と書く) が任意の $z\in\omega$ に対して成立することを数学的帰納法を用いて示す。まず $z=0$ なら前提が満たされないので $\psi(0)$。
次に $\psi(z)$ を仮定する。ここで $x\in y$, $y\in z\cup\{z\}$ とすると、$y\in z$ か $y\in\{z\}$ のいずれかが成立する。前者なら $x\in y$, $y\in z$ と仮定の $\psi(z)$ より $x\in z$。したがって $x\in z\cup\{z\}$。後者なら $y=z$ であるので $x\in y$ より $x\in z$ となり、したがって $x\in z\cup\{z\}$。いずれにしても $x\in z\cup\{z\}$ であるので $\psi(z\cup\{z\})$
定理$\omega$ に属する $y$ について、$x\in y$ ならば $x\in \omega$。
(証明) 「どんな $x$ についても $x\in y$ が満たされるならば $x\in \omega$」(以下、$\psi(y)$ と書く) が任意の $y\in\omega$ に対して成立することを数学的帰納法を用いて示す。まず $y=0$ なら前提が満たされないので $\psi(0)$。
次に $\psi(y)$ を仮定する。ここで $x\in y\cup\{y\}$ とすると、$x\in y$ か $x\in\{y\}$ のいずれかが成立する。前者なら $x\in y$ と仮定の $\psi(y)$ より $x\in \omega$。後者なら $x=y$ であるので $y\in\omega$ より $x\in \omega$。いずれにしても $x\in \omega$ であるので $\psi(y\cup\{y\})$
命題自然数 $x$, $y$ に対して $x\in y$ であれば $x\cup\{x\}\in y$ または $x\cup\{x\}= y$。
(証明) 「自然数 $x$ に対して $x\in y$ ならば $x\cup\{x\}\in y$ または $x\cup\{x\}= y$」(以下、$\psi(y)$ と書く) が任意の $y\in\omega$ に対して成立することを数学的帰納法を用いて示す。まず $x\not\in 0$ は明らかだから $\psi(0)$。
次に $\psi(y)$ を仮定する。このとき $x\in y\cup\{y\}$ とすると、$x\in y$ か $x=y$ である。$x\in y$ であれば数学的帰納法の仮定より $x\cup\{x\}\in y$ または $x\cup\{x\}= y$ であるので自然数の推移性より $x\cup\{x\}\in y\cup\{y\}$。$x=y$ であれば $x\cup\{x\}= y\cup\{y\}$。以上より $\psi(y\cup\{y\})$。
定理$\omega$ に属する $x$ について、$x\not\in x$。(注: これは正則性の公理を使えばすぐにわかることであるが、この記事では正則性の公理について説明しないので、代わりに数学的帰納法を用いて証明する。数学的帰納法が機能すること自体が正則性の公理に依存しているので、本来ならば数学的帰納法を使わずに直接正則性の公理を使うべきである。)
(証明) $x$ について数学的帰納法を用いる。まず $0\not\in 0$ は明らか。
次に $x\not\in x$ とする。このとき $x\cup\{x\}\in x\cup\{x\}$ とすると矛盾することを示す。この仮定より\[x\cup\{x\} \in x \text{ か } x\cup\{x\}=x\]のいずれかが成立する。前者の場合は自然数の推移性と $x\in x\cup\{x\}$ より $x\in x$ となって数学的帰納法の仮定に矛盾する。後者の場合は $x\in x\cup\{x\}$ より $x\in x$ となってやはり数学的帰納法の仮定に矛盾する。いずれにしても矛盾するので $x\cup\{x\}\not\in x\cup\{x\}$。
定理任意の自然数 $x$, $y$ について、$x$ の次の数が $y$ の次の数に等しいとき $x=y$。つまり\[x\cup\{x\}=y\cup\{y\}\]であれば\[x=y.\](注: これは正則性の公理を使えば $x$ や $y$ が自然数に限らなくても証明できる。しかし、この記事では正則性の公理について説明しないので、$x$ と $y$ を自然数に限定して自然数の正則性を用いて証明する。)
(証明) 背理法を用いる。$x\cup\{x\}=y\cup\{y\}$ とすると、\[x\in y\cup\{y\}\]である。ここで $x\neq y$ と仮定すると $x\in y$ となる。同様に $y\in x\cup\{x\}$ から $y\in x$ となる。このとき自然数の推移性より $x\in x$ となるがこれは自然数の正則性に矛盾する。よって $x=y$。
余談
ここで用いられている自然数の定義はよく知られ用いられている。それを前提として下の記述を見てみよう。\[1\in 3\]高校数学の知識では「3は集合ではないので $\in$ の右側に 3 を書くのはおかしい」となるのであろうが、我々が採用した「すべてのモノは集合である」論理では 3 も集合として定義しているのでその指摘は当たらない。しかも、3 は $\{0,1,2\}$ (0と1と2だけが属する集合) と定義されているので $1\in 3$ (1は3に属する) は正しい。この点で微妙に高校数学の集合論と公理的集合論 (とりわけ ZF 公理系や ZFC 公理系を採用する集合論) には違いがある。