ZFC公理系について：その2 - Rei Frontier Tech Blog

レイ・フロンティア株式会社のデータアナリストの齋藤です。
本記事の目的は、自然数全体の集合$\mathbb{N}$を定義し、その性質（の一部）を述べることです。

べき集合の公理、自然数の全体
ペアノの公理

べき集合の公理、自然数の全体

自然数の話に戻ります。前記事で得られた、空集合0とその後継ぎ1,2,...の"全体"の集まりを$\mathbb{N}$とするのが、いかにも自然な発想であるように思われます。しかし、今無限公理によって存在が保証されているのは、あくまで0とその後継ぎたちを全て含む集合（すなわち、無限系譜）だけです。そのような集合は、"自然数"だけではなく、その他にいろいろ余計な元を含んでいる可能性があります。そこで、ある一つの無限系譜（それには自然数が全て含まれています）をてきとうにとり、それに含まれる無限系譜すべての共通部分をとればよいのではないか？というアイデアを思いつきます。これを実行するには、また新しい公理を加えねばなりません。というのも、ある無限系譜が与えられたときに、「それに含まれる無限系譜の全体」は集合だろうか？という問いに答えられないからです。この問いを一般化すると、「集合$a$が与えられたとき、"$a$の部分集合全体"は集合になるか？」ということになりますが、これに肯定的に答えるために以下の公理を導入します：

(Set7) べき集合の公理$$\forall a \exists b \forall x (x\in b \Leftrightarrow x \subset a) .$$

普通の言葉で言うと、「任意の集合$a$に対して、$a$の部分集合全体から成る集合$b$が存在する」ということです。この集合$b$は$a$のべき集合(power set)とよばれ、$\mathcal{P}(a)$と表されます。

さて、いよいよ自然数全体の定義に入りましょう。まず集合$x$について、「$x$は無限系譜である」という命題を$M(x)$で表します。論理式で書くと、$M(x)$とは、$$\emptyset \in x \wedge \forall y (y \in x \Rightarrow y^+ \in x)$$ということです。空集合とは異なる集合$a$に対して、$$\forall x(x \in a \Rightarrow M(x))$$が成り立つとき、$a$を無限樹と呼ぶことにします。たとえば、ある無限系譜$x$のシングルトン$\{x\}$は無限樹です。無限公理によって、無限樹は少なくとも一つ存在します。てきとうな無限樹をとって、共通部分をとることによって樹の"枝"を刈り取り、$\mathbb{N}$という一本の幹を切り出そうという魂胆です。
明らかに次の補題が成り立ちます：

補題1.無限系譜$a,b$について以下が成り立つ：
(i) $\cap a$は無限系譜である。
(ii) $a \subset b \Rightarrow \cap a \supset \cap b .$

さて、$a$を無限系譜として、$$\tilde a = \{x \in \mathcal{P}(z) \mid M(x)\}$$
とおきます。すなわち、$\tilde a$は$a$に部分集合として含まれる無限系譜全体からなる集合です。べき集合と分出公理と無限公理によって$\tilde a$は集合であり、外延性公理によって$\tilde a$は$a$によって確定します。さらに、$a \tilde \ni a$だから$\tilde a \not= \emptyset $であり、$\tilde a$は無限樹となっています。
$$\omega_a = \bigcap \tilde a$$とおきます。補題1によって$\omega_a$は無限系譜であり、$\omega_a \in \tilde a$が成り立ちます。いま、$b$を任意の無限系譜とすると、$a\cap b$もまた無限系譜なので、補題1により$\omega_{a\cap b} \supset \omega_a$となります。
ここで、$z$を$\omega_{a\cap b}$の任意の元とし、$x \in \tilde a$とします。すると、$x \cap b \subset a \cap b$であり、しかも$x\cap b$は無限系譜となるので$x\cap b \in \widetilde {a \cap b}$、ゆえに$z \in x\cap b$、したがって$z \in x$が成り立ちます。これにより$z \in \omega_a$が成り立つので、$\omega_{a\cap b} \subset \omega_a$、したがって$\omega_{a\cap b} = \omega_a$です。$a,b$は任意の無限系譜であったので、$\omega_a = \omega_{a\cap b} = \omega_b$となります。よって、無限系譜$\omega_a$は$a$の選び方によらずに確定し、しかも任意の無限系譜の部分集合になることがわかりました。この$\omega_a$を$\mathbb{N}$と書き、自然数全体の集合と呼びます。$\mathbb{N}$は0,1,2,...を元として含んでおり、$\mathbb{N}$の元を自然数(natural number)と呼びます。

ペアノの公理

前節の議論によって、我々はついに当初の目的であった「自然数の全体」という、具体的でかつ非自明な集合を手に入れることができました。しかし、果たしてこの集合を、我々がふだん接している"自然数の全体"であると言ってもよいのでしょうか。たとえば、定義から$1 \subset 2 \subset 3 \subset \cdots$のような関係が成り立ちますが、これは"普通の自然数"を考えるときにはちょっと馴染みの薄い光景です。しかし、考えようによっては、これは単に我々が自然数を定義するために上記のような方法をとったために産まれた"副産物"にすぎず、自然数としての"算術的性質"さえ満たされていれば、あとは"普通の自然数"として扱えても差し支えない、と思うこともできます。では、今我々が構成した"集合論的自然数"が"普通の自然数"と同じような"算術的性質"をもつことが示されるでしょうか？

自然数のもつべき"算術的性質"には、大小関係、足し算掛け算等々いろいろありますが、それらはいくつかの基本的な性質から証明できます（長くなるので、本記事では扱いません）。そのような基本的性質として挙げられるのが、ペアノ(Peano)の公理です。すなわち、集合$a$がつぎの命題たちを満たしていれば、$a$は"自然数の集合の算術的性質"を満たすことが示されます：

Peanoの公理(P1) $x \in a$ならば$x^\prime$と表される$a$の元が確定する。
(P2) $a$の元$\nu$で、$a$の任意の元$x$に対して$x^\prime \not = \nu$となるものが存在する。
(P3) $b\subset a, \nu \in b$かつ$\forall x (x \in b \Rightarrow x^\prime \in b)$が成り立てば$b = a$である。
(P4) $x\in a, y \in a$かつ$x^\prime = y^\prime$ならば$x=y$である。

そして、この性質は今定義した$\mathbb{N}$についても無事成立します。

定理3.集合$\mathbb{N}$について、Peanoの公理が成り立つ。ただし、$x \in \mathbb{N}$について$x^\prime = x^+ = x \cup \{x\}$とし、$\nu = 0 = \emptyset$とする。

(証明) (P1)が成り立つことは明らか。また、(P3)に現れる$b$は無限系譜であるから、$\mathbb{N} \subset b \mathbb{N}$ゆえに$b = \omega$だから(P3)が成り立つ。(P2)についても、$\nu = 0 = \emptyset $であり、なおかつ$x^\prime = x \cup \{x\} \in x$なので$x^\prime \not= 0$となる。
(P4)を示すために、$x \in \omega, y \in \omega$とし、$x^+ = y^+$としよう。$x \in x^+ = y^+ = y \cup \{y\}$であるから、$x \in y$と$x = y$のどちらかが成り立つ。同様にして、$y \in x^+$であるから、$y \in x$または$y = x$が成り立つ。
つぎの補題が成り立つとしよう（証明は後で述べる）：

補題2.$\mathbb{N}$の元$x,y$について、$x \in y \Leftrightarrow x \subsetneqq y .$

$x \in y$かつ$y \in x$であると仮定する。上の議論により、$x^+ = y^+ \Rightarrow x = y \vee (x \in y \wedge y \in x)$であるが、補題2により$x \in y \wedge y \in x \Rightarrow x \subsetneqq y \wedge y \subsetneqq x \Leftrightarrow x \subset y \wedge y \subset x \wedge x \not= y$となり、一番右の命題は$ (x = y) \wedge \lnot (x = y)$を意味するので矛盾。したがって$x^+ = y^+ \Rightarrow x = y$が成り立つ。■

最後に、仕上げとして補題2を証明しましょう。

(補題2の証明) $y = 0 = \emptyset$ならば、どのような$x$に対しても$x \in y $も$x \subsetneqq y$も成立しない。したがって、$P,Q$を任意の命題とするとき、$x \in 0 \Rightarrow P$と$x \subsetneqq 0 \Rightarrow Q$がともに成立する。ゆえに、このとき補題は成り立つ。
さて、上の議論のなかで、$\mathbb{N}$に関して(P3)が成り立つことは補題を用いずに証明されているので、$\mathbb{N}$の元$y$に関する次の命題$P_1, P_2$が示されればよい：$$\begin{align} &P_1: \forall x(x \in \mathbb{N} \wedge x \in y \Rightarrow x\subsetneqq y)\ \Rightarrow \ \forall x(x \in \mathbb{N} \wedge x \in y^+ \Rightarrow x\subsetneqq y^+) \\ &P_2: \forall x(x \in \mathbb{N} \wedge x \subsetneqq y \Rightarrow x\in y)\ \Rightarrow \ \forall x(x \in \mathbb{N} \wedge x \subsetneqq y^+ \Rightarrow x\in y^+) \end{align}$$まず$P_1$を示そう。$x\in \mathbb{N}$にたいして、$x \in y^+ = y \cup \{y\}$となれば、$x \in y \vee x = y$である。もし$x \in y$ ならば、仮定により$x \subsetneqq y$であり、ゆえに$x \subsetneqq y^+$となる。また$x=y$ならば明らかに$x \subset y^+$であるから、$y \not= y^+$が示されれば$x \subsetneqq y^+$が示される。もし$y = y^+$ならば、$y^+$の定義から$y \in y$となるが、仮定と$x=y$より$y \subsetneqq y$、とくに$y \not= y$となるので矛盾である。したがって、$y \subsetneqq y^+$となって、$P_1$は示された。
次に、$P_2$が成り立つことを示そう。$x \in \mathbb{N}$について$x \subsetneqq y^+$となると仮定する。もし$y \in x$ならば$P_1$により$y \subsetneqq x$となり、ゆえに$y \cup \{y\} \subset x$となるが、これは$x \subsetneqq y^+$に反する。よって$y \not\in x $であるが、このとき$x \subsetneqq y^+ = y \cup \{y\}$から$x \subset y$がいえる。$x \subset y \Leftrightarrow x \subsetneqq y \vee x = y$である。仮定から$x \subsetneqq y \Rightarrow x \in y \Rightarrow x \in y^+$であり、しかも$x=y \Rightarrow x \in y^+$であるから、$P_2$は成り立つ。■

補題2の証明で活躍した公理(P3)は数学的帰納法の原理とも呼ばれています。実際、Peanoの公理は高校数学などでもお馴染みの数学的帰納法の定理を含んでいます：

定理4.(数学的帰納法)自然数$n$に関する命題$P(n)$について、つぎの(i),(ii)が成り立てば、任意の自然数$n$について$P(n)$が成り立つ：
(i) $P(0). $
(ii) $\forall n (n \in \mathbb{N} \wedge P(n) \Rightarrow P(n^+)). $

これでようやく、集合の公理を基礎として自然数および自然数全体の集合$\mathbb{N}$を、期待される算術的性質を満たす形で構成することができました。ここでは取り上げませんが、これらの公理を用いて、有理数、実数、複素数なども構成されます。では集合の公理はこれで全部としてよいのかというとそんなことはなく、様々な"無限集合"同士を比較するために新しい公理が必要となります。本記事もずいぶん長くなってしまいました。残りのZFCの公理の紹介は次回の記事で行いたいと思います。

次回に続きます。