Rei Frontier Tech Blog

人工知能を活用した位置情報分析プラットフォーム「SilentLog Analytics」を運営する、レイ・フロンティア株式会社のエンジニアメンバーで運営する技術ブログです。

ZFC公理系について:その3

レイ・フロンティア株式会社のデータアナリストの齋藤です。
前前回前回につづいて、ZFC公理系の残りの公理を紹介していきます。

写像と選択公理

順序対、直積

ふだん慣れ親しんでいる数学的対象として、自然数などの数だけではなく、数と数の関係を定める関数(あるいは写像)があります。そこで、Zermelo-Fraenkelの立場から関数を構成することを考えてみましょう。
集合\(A\)から集合\(B\)への写像\(f \colon A \to B\)を集合論的に定義するためには、写像\(f\)のグラフというものを用います。\(f\)のグラフというのを直感的に説明すると、"\(A\)と\(B\)の直積"\(A times B\)の部分集合で、\( (x,f(x))\ (x\in a)\)というペアの全体から成るもののことです。\(A=B=\mathbb{R}\)の場合を考えると、関数\(f\)のグラフを座標平面にプロットしたものは、\(y=x^2\)のグラフは放物線などといったお馴染みの"グラフ"になります。
しかし、我々はまだ\(A\)と\(B\)の直積なるものを定義できていません。したがって、まずこの\(A \times B\)を定義するところから始めます。

集合\(a,b\)が与えられたとしましょう。それらの直積\(a\times b\)の元として我々が想定しているのは、\(a,b\)のそれぞれの元\(x,y\)のペア\( (x,y) \)のことです。そして、2つのペア\( (x,y) , (x^\prime, y^\prime)\)が等しいとは\(x=x^\prime , y=y^\prime\)が成り立つことでした。2つの集合の組として非順序対\( \{ a,b \}\)というのを以前考えましたが、\(\{ a,b\} = \{ b,a \}\)なので、これではうまくいきません。しかし、非順序対に一工夫加えることで、順序対を構成することができます。
次の補題が成り立ちます:

補題3.集合\(x,y,x^\prime, y^\prime \)について、次が成り立つ:$$\{ \{ x \}, \{ x , y \} \} = \{ \{ x^\prime \}, \{ x^\prime , y^\prime \} \} \Leftrightarrow x = x^\prime \wedge y = y^\prime .$$
集合\(x,y\)に対し、\( \{ \{ x \} , \{ x , y \} \} \)を\(x,y\)の順序対(ordered pair)と呼び、\( ( x , y ) \)と書きます。
\(x , y\)がそれぞれ集合\(a,b\)の元であるとき、\(\{ x \} , \{ x,y \} \subset a \cup b\)だから、\(\{ x \} , \{ x,y \} \)はともにべき集合\(\mathcal{P}(a\cup b)\)の元となります。したがって、$$ (x,y) = \{ \{ x \} , \{ x , y \} \} \in \mathcal{P} ( \mathcal{P} (a \cup b) )$$です。

集合\(a,b\)に対して、それらの直積(direct product)あるいはカルテシアン積(Cartesian product)\(a \times b\)を、$$a \times b = \{ u \in \mathcal{P}(\mathcal{P}(a \cup b )) \mid \exists x \exists y ( x \in a \wedge y \in b \wedge u = ( x , y ) ) \}$$によって定義します。"普通の言葉"で言えば、\(a \times b\)は\(a\)の元\(x\), \(b\)の元\(y\)の順序対\( (x,y) \)全体から成る集合です。合併集合の公理、分出公理、べき集合の公理によって\(a \times b\)の存在は保証され、外延性公理によって\(a \times b\)は\(a\)と\(b\)が与えられたとき確定します。上の定義により、$$u \in a \times b \Leftrightarrow \exists x \exists y ( x \in a \wedge y \in b \wedge u = (x,y) )$$となるので、とくに$$\emptyset \times b = \emptyset, \ a \times \emptyset = \emptyset$$が任意の集合\(a,b\)について成り立ちます。

写像、一般の直積、選択公理

さてこれから写像を定義するわけですが、その前により一般的な概念である"対応"の定義から始めましょう。集合\(a,b\)に対して、直積\(a \times b\)とその部分集合\(f\)の順序対\( (a \times b , f) \)を\(a\)から\(b\)への対応(correspondence)と呼び、\(f\)を対応\( (a \times b, f) \)のグラフ(graph)と呼びます。\(a,b\)が与えられているとき、\( (a \times b , f) \)をたんに対応\(f\)と言うこともあります。\(x \in a\)のとき、\( f(x) = \{ y \in b \mid (x, y) \in f \} \)とおき、\(f(x)\)を\(x\)の\(f\)による像(image)と呼びます。とくに、\(f(x) = \{ y \} ,\ y \in b\)のとき、たんに\(f(x) = y\)と書きます。\(a\)から\(b\)への対応\( (a \times b , f) \)が与えられたとき、これを"対応\(f \colon a \to b\)"と表します。また、集合\(\{ x \in a \mid f(x) \not= \emptyset \}\)を\(f\)の定義域(domain of definition)と呼び、これを\(\mathrm{Dom} f\)と書きます。また、部分集合\(a^\prime \subset a \)に対して、\(f[a^\prime] = \{ y \in b \mid \exists x (x \in a^\prime \wedge (x,y) \in f) \}\)とおけば、$$f[a^\prime] = \bigcup_{x \in a^\prime} f(x)$$となります。\(f[a^\prime]\)のことを\(f\)による\(a^\prime\)の像(image)と呼びます。\(f[a^\prime]\)のことを\(f(a^\prime)\)と書くこともあります。とくに、\(f[a]\)を\(f\)の像または値域と呼び、\(\mathrm{Im}f\)とも表します。
対応\(f\colon a \to b\)は、\(\mathrm{Dom} f = a\)かつ\(a\)の任意の元\(x\)に対して\(f(x)\)が\(b\)の元のシングルトンとなるとき、\(a\)から\(b\)への写像(mapping)と呼びます。たとえば、\(\mathbb{N}\)から\(\mathbb{N}\)への対応\(f\)として\(f = \{ (m,n) \in \mathbb{N} \times \mathbb{N} \mid n = m^+ \}\)をとるとき、この対応\(f \colon \mathbb{N} \to \mathbb{N}\)は\(\mathbb{N}\)から\(\mathbb{N}\)への写像であり、\(f(m) = m^+\)です。
もう一つ重要な例を挙げておきましょう。集合\(a\)に対して\(\Delta_a = \{ (x,y) \in a \times a \mid x = y \}\)を直積\(a \times a\)の対角線集合(diagonal set)と呼びます。\(f = \Delta_a\)とおけば、\( (a \times a , f)\)は\(a\)からそれ自身への写像であり、\(a\)の任意の元\(x\)について\(f(x) = x\)となります。この写像は\(a\)の恒等写像(identity mapping)と呼ばれ、\(\mathrm{id}_a\)または\(1_a\)などと表されます。
写像\(f \colon a \to b\)について\(f[a]=b\)のとき、\(f\)は\(a\)から\(b\)への全射(surjection)と呼ばれ、\(a\)の任意の元\(x,y\)に対して\(f(x)=f(y)\Rightarrow x=y\)が成り立つとき\(f\)は\(a\)から\(b\)への単射(injection)と呼ばれます。\(f\)が\(a\)から\(b\)への全射でありかつ単射でもあるとき、\(f\)は\(a\)から\(b\)への全単射(bijection)と呼ばれます。\(a\)から\(b\)への全単射が存在するとき\(a\)と\(b\)は対等(equivalent)であるといわれ、\(a\approx b\)と書かれます。
また、集合\(a,b\)が与えられたとき、写像\(f \colon a \to b\)は直積\(a \times b\)の部分集合のなかの特殊なものによって定まりますが、\(a\)から\(b\)への写像のグラフ全体からなる集まりは\(\mathcal{P}(a \times b)\)の部分集合です。この後者の集合を\(b^a\)と書くことにします。
\(a\)から\(b\)への対応\(f\)が与えられたとき、\(b\)から\(a\)への対応\(f^{-1}\)を$$f^{-1} = \{ (y,x) \in b \times a \mid (x,y) \in f \}$$によって定義し、\( (b \times a, f^{-1}\)または略して\(f^{-1}\)を\(f\)の逆対応とよびます。2つの対応\(f \colon a \to b\)と\(g \colon b \to c\)が与えられたとき、\(f,g\)の"合成"とよばれる対応\(g \circ f \colon a \to c\)が$$g \circ f = \{ (x,z) \in a \times c \mid f(x) \cap g^{-1}(z) \not= \phi \}$$というように定義されます。\(f \colon a \to b\)と\(g \colon b \to c\)がともに写像ならば、それらの合成\(g\circ f \colon a \to c\)も写像となり、\(x \in a\)に対して\( (g \circ f)(x) = g(f(x)) \)となります。


2つの集合の直積を定義し、それを用いて写像を定義することができました。しかし、実際にはもっと多くの個数、とくに無限に多くの集合の直積を考えたくなることがあります。そのような一般の直積を、写像を用いて定義します。
空でない集合\(I\)が与えられ、\(I\)から集合\(A\)への写像\(f\)が与えられているとき、順序対\( (f,f[I]) \)を\(I\)によって添数づけられた集合(indexed set)と呼び、\(I\)を\(f[I]\)の添数集合、\(I\)の元\(i\)を添数(index)と呼びます。\(f(i)\)を\(a_i\)とも書き、\( (f,f[I])\)を\(\{ a_i \}_{i \in I}\)のようにも書きます。また、このとき\(\cup f[I]\)のことを\(\cup_{i \in I}a_i\)とも書きます。
空集合とは異なる集合\(I\)によって添数づけられた集合\(\{ a_i \}_{i \in I}\)が与えられたとき、その直積とはつぎのような集合\(b\)のことをいいます:$$b = \left\{ \lambda \in \left( \bigcup_{i\in I}a_i \right)^I \middle| \forall i (i \in I \Rightarrow \lambda(i) \in a_i) \right\} .$$この集合\(b\)を\(\prod_{i \in I} a_i\)と表します。とくに、\(I = 2\)のときには、\(\prod_{i \in I} a_i \approx a_0 \times a_1\)となります。自然数\(n\)に対して\(I = n\)のとき、\(\prod_{i \in I} a_i\)は\(\prod_{i = 0}^{n-1} a_i\)または\(a_0 \times a_1 \times \cdots \times a_{n-1}\)というふうに表されます(正確には、自然数\(n\)の引き算を定義する必要があります)。
一般に、\(\lambda\)を直積\(\prod_{i \in I} a_i\)の元とすれば、\(\lambda\)は\(\lambda(i)\)によって定まるので、\(\lambda\)を\( (\lambda(i))_{i \in I}\)というふうに書きます。とくに、\(a_0 \times a_1 \times \cdots \times a_{n-1}\)の元は\( (\lambda(0), \lambda(1), \dots, \lambda(n-1))\)と書きます。こうして、我々がふだん使っている直積の姿が見えてきました。

さて、直積の定義から明らかに、\(a \not= \emptyset \)かつ\(b \not= \emptyset \)ならば\(a \times b \not= \emptyset\)です。それでは、一般に空集合とは異なる集合\(I\)によって添数づけられた集合\(\{ a_i \}_{i \in I}\)で、\(I\)の任意の元\(i\)に対して\(a_i \not= \emptyset\)なるものが与えられたとき、\(\prod_{i \in I} a_i\)は空集合ではないと言えるでしょうか。この問いに肯定的に答えるために考えられたのが、次の公理です:

(Set8) 選択公理$$\forall a \exists f [ f \in (\cup a)^a \wedge \forall x (x \in a \wedge x \not= \emptyset \Rightarrow f(x) \in x) ]$$
普通の言葉でいうと、「任意の集合\(a\)に対して、\(a\)から\(\cup a\)への写像\(f\)が存在し、\(a\)の任意の元で空集合とは異なるもの\(x\)に対して\(f(x) \in x\)となる」というものです。この公理は選択公理(axiom of choice)と呼ばれ、この公理によって存在を保証される写像\(f\)を、\(a\)の選択写像あるいは選択関数(choice function)と呼びます。
次が成り立ちます:
定理5.\(I\)を空集合とは異なる集合、\(\{ a_i \}_{i \in I}\)を\(I\)によって添数づけられた集合で、任意の\(i \in I\)に対して\(a_i \not= \emptyset\)であるものとする。このとき、直積\(\prod_{i \in I}a_i\)は空集合ではない。
(証明) \(A = \{ a_i \}_{i \in I}\)とおけば、定義により写像\(f \colon I \to A\)で\(f(i) = a_i\)となるものが存在する。\(F\)を\(A\)の選択関数とすれば、任意の\(i \in I\)に対して\(a_i \not= \emptyset \)だから、\(F(a_i) \in a_i\)となる。ここで、\(\lambda = F \circ f\)とおけば、\(\lambda\)は\(I\)から\(\cup A = \cup_{i \in I}a_i\)への写像であり、任意の\(i \in I\)について\(\lambda(i) = F(a_i) \in a_i\)となるから、\(\lambda \in \prod_{i \in I}a_i\)となる。■

順序数、ZFC公理系

順序関係と順序数

自然数、実数といった数の性質を調べるにあたっては、数の大小関係は重要です。そこで、数の大小関係の一般化にあたる"順序関係"を定義していきます。

集合\(a\)からそれ自身への対応\( (a \times a , f) \)あるいは単にそのグラフ\(f\)を、\(a\)の元の間の関係(relation)といいます。集合\(a\)の元の間の関係\(\prec\)について、\( (x,y) \in \prec \)のことを\(x \prec y\)と書くことにしましょう。つぎの条件$$\begin{align} &(1)\ \forall x (x \in a \Rightarrow x \prec x )\ (反射律) \\ &(2)\ x \prec y \wedge y \prec x \Rightarrow x=y\ (反対称律)\\ &(3)\ x \prec y \wedge y \prec z \Rightarrow x \prec z\ (推移律) \end{align}$$が成り立つとき、\(\prec\)を\(a\)の元の間の順序関係(order relation)と呼び、順序対\( (a,\prec) \)のことを順序集合(ordered set)と呼びます。上の(1),(2),(3)は順序の公理(axion of order)と呼ばれます。
\( (a,\prec) \)を順序集合、\(x,y \in a\)に対して、\(x \prec y \wedge x \not= y\)のとき\(x \precneqq y\)と書くことにします。\(x \in a\)に対して、\(a\)の部分集合で\(x\)の切片(segment)と呼ばれるものを$$s(x) = \{ y \in a \mid y \precneqq x \}$$と定めます。
\( (a,\prec) \)を順序集合、\( S \subset a\)とします。\(S\)の元\(s\)について\( \forall t (t \in S \Rightarrow s \prec t ) \)が成り立つとき、そのような\(s\)は一意的に定まり、それを\(S\)の(\(\prec\)に関する)最小元(minimum)と呼び、\(\min S\)と書きます。自然数全体の集合\(\mathbb{N}\)の重要な性質として、「\(\mathbb{N}\)の任意の空ではない部分集合が最小元をもつ」というものがありますが、一般に順序集合\( (a,\prec ) \)において、任意の空でない\(a\)の部分集合\(s\)について\(\min s\)が存在するとき、\( (a,\prec )\)または\(a\)を整列集合(well-ordered set)であるといいます。
順序集合\( (a,\prec_1 ), (b,\prec_2 ) \)および写像\(F\colon a \to b\)が与えられたとします。\(a\)の任意の元\(x,y\)について、$$x \prec_1 y \Rightarrow F(x) \prec_2 F(y)$$が成り立つとき、\(F\)は順序を保つ写像(order preserving mapping)と呼びます。\(F\)が\(a\)から\(b\)への全単射であれば\(F\)は\(a\)から\(b\)の上への順序同型写像(order isomorphism)といい、またこのとき\( (a,\prec_1) \)と\( (b,\prec_2) \)は順序同型(order isomorphic)であるといって\( (a,\prec_1) \simeq (b,\prec_2) \)または\(a \simeq b\)と書きます。たとえば恒等写像\(1_a\)は\(a\)からそれ自身への上への順序同型写像です。

ところで、自然数\(0, 1=\{ 0 \}, 2 = \{ 0,1 \} , 3 = \{ 0,1,2 \} , \dots \)や自然数全体の集合\(\mathbb{N}\)、\(\mathbb{N}^+ = \mathbb{N} \cup \{ \mathbb{N} \}\)などはみな包含関係について整列集合となっています。これらに共通する性質のひとつに、「\(x\)をこれらの中の任意のものの元とするとき、切片\(s(x)\)と\(x\)が相等しいものがある」というものがあります。一般に、\( (a,\prec) \)を整列集合とするとき、\(a\)の任意の元\(x\)について\(x = s(x)\)が成り立つならば、\( (a,\prec) \)(または\(a\))を順序数(ordinal number)と呼びます。自然数や\(\mathbb{N}\)などは順序数ですが、たとえば\(\{ 0,2 \}\)などは包含関係について整列集合とみなすとき順序数ではありません。
\( (a,\prec) \)を順序数としましょう。\(x ,y \in a \)とすると、\(x \precneqq y \Leftrightarrow x \in s(y) \Leftrightarrow x \in y \)、ゆえに\( x \precneqq y \Leftrightarrow x \in y\)が成り立ちます。さらに、\(x \precneqq y \Leftrightarrow s(x) \subsetneqq s(y)\)であるので、$$x \precneqq y \Leftrightarrow x \subsetneqq y \Leftrightarrow x \in y$$が成り立ちます。よって、このとき、順序関係\(\prec\)というのは包含関係\(\subset\)にほかならず、\(a\)の集合論的構造のみによって定まるのです。この事実からも、順序数\( (a,\prec) \)を単に\(a\)と表しても問題ないと納得がいくでしょう。

正則性公理

\(\alpha\)を任意の順序数とするとき、\(\alpha \in \alpha^+ \in (\alpha^+)^+ \in \cdots \)となり、このような列はいくらでも延ばすことができます。しかし、\(\alpha\)から"左へ"いくらでも列を延ばすことはできません。たとえば\(\alpha = 2\)とすれば\(2 \ni 1 \ni 0\)でストップです。
一般に、\(\alpha\)を任意の順序数とするとき、\(\alpha\)に含まれる元\(\beta\)で\(\gamma \in \beta \Rightarrow \gamma \not\in a\)が成り立つものが存在します(\(\beta = 0\)とすればよい)。このことがより一般的に成り立つことを主張するのが、つぎの公理です:

(Set9) 正則性公理$$\forall a [ a \not= \emptyset \Rightarrow \exists b (b \in a \wedge a \cap b = \emptyset) ]$$
普通の言葉でいうと、「空でない集合\(a\)に対して、その元\(b\)で、\(b\)のいかなる元も\(a\)には含まれないものが存在する」ということになります。
たとえば、\(x\)を任意の集合とし、\(a = \{ x \}\)とおけば、\(a\)の元は\(x\)のみなので、正則性公理から\(\{ x\} \cup x = \emptyset\)となり、したがって\(x \not\in x \)が成り立ちます。すなわち、正則性公理を仮定すれば、集合がそれ自身を元として含むという状況は起こらなくなります。

置換公理

順序数に関しては、次の定理が基本的です:

定理6.\( (a,\prec) \)を任意の整列集合とすると、順序数\(\alpha \)で\(a \simeq \alpha \)となるものが一意的に存在する。
実は、この定理の証明に困難が伴うのです。\(\alpha\)の存在を証明するためには超限帰納法というテクニックを用います。これについては割愛しますが、そのプロセスにおいて「\(s(x)\)の任意の元\(y\)に対して\(s(y) \simeq \alpha_y\)となるような順序数\(\alpha_y\)が存在する」ということを仮定して「\(s(x)\)と順序同型な順序数が存在する」ことを証明する場面が出てきます。\(s(x)\)と順序同型となるような順序数\(\alpha_x\)の候補として\(\alpha_y (y \in s(x))\)の合併集合が考えられますが、ここで困難が生じます。というのも、合併集合をとるためには"\(\alpha_y (y \in s(x))\)の全体"が集合であることが示されねばなりませんが、\(s(x)\)というのは今我々の持っている分出公理が使えないほどに"巨大な"集合なのです。
ここで、この困難を克服するために、つぎの公理が導入されます:
(Set6) 置換公理\(P(x,y)\)を\(x,y\)を自由変数とする命題とし、\(a\)を集合とするとき、次が成り立つ:$$\begin{align}& \forall x [ x \in a \Rightarrow \forall y \forall z ( P(x,y) \wedge P(x,z) \Rightarrow y = z ) ] \\ & \quad \quad \Rightarrow \exists b \forall u [u \in b \Rightarrow \exists x ( x \in a \wedge P(x,u) ) ] \end{align}$$
普通の言葉でいうと、「\(a\)の任意の元\(x\)に対して\(P(x,y)\)が成り立つような\(y\)が存在するならばそれは一意的だとしよう。そのとき、集合\(b\)で、\(P(x,u) (x \in a)\)を成り立たせるような\(u\)全体からなるものが存在する」ということです。

最後に、(Set1)-(Set9)から分出公理(Set6')が示されることを見ていきます。集合\(a\)が元\(x\)を含むとき、\(a\)の部分集合\(b\)で、$$t \in b \Leftrightarrow t \in a \wedge t\not= x$$を満たすものが存在することを示します。
\(a = \{x\}\)のときは、\(b = \emptyset\)とすればよいので、\(a \in y, y \not= x\)とします。命題\(P(s,t)\)として、$$(s \in a \wedge s \not= x \Rightarrow t=s) \wedge (s=x \Rightarrow t=y)$$をとると、置換公理によって、集合\(b\)で$$t \in b \Leftrightarrow \exists s (s \in a \wedge P(s,t))$$をみたすものが存在します。これは示したかった性質をみたしています。
このような集合\(b\)を\(a-\{x\}\)と書きましょう。いま\(a\)を集合、\(P(x)\)を\(x\)を自由変数とする命題とするとき、集合\(c\)で$$x \in c \Leftrightarrow x \in a \wedge P(x)$$をみたすものが存在することを示せば、分出公理が成り立つことがわかります。\(x,y\)についての命題\(Q(x,y)\)として、$$(x \in a \wedge P(x) \Rightarrow y = x) \wedge (x \in a \wedge \lnot P(x) \Rightarrow y = a)$$というものをとります。置換公理によって、集合\(b\)で、$$y \in b \Leftrightarrow \exists x (x \in a \wedge Q(x,y))$$をみたすものが存在します。\(b\)の元\(y\)は、\(a\)の元\(x\)で\(P(x)\)を成り立たせるものか、または\(a\)自身です。もし\(a\)の任意の元\(x\)について\(P(x)\)が成り立つならば、\(b = a\)が成り立ち、その場合では上のような\(c\)として\(a\)自身をとれば解決です。もし\(a\)の元\(x\)で\(\lnot P(x)\)となるようなものがあれば、そのような\(x\)に対して命題\(Q(x,a)\)が成り立つから、\(a \in b\)が成り立ちます。ここで\(c = b - \{a\}\)とおけば、\(c\)の元はすべて\(a\)の元\(x\)で\(P(x)\)を成り立たせるものであり、また逆に\(a\)の元\(x\)で\(P(x)\)を満たすようなものがあれば、正則性公理によって\(x\)は\(a\)自身ではないので、\(c\)の元となっています。よって\(c\)は求める集合です。これで分出公理が導かれました。

以上、紹介した9つの公理(Set1)-(Set9)のことをZermelo-Fraenkelの公理系、あるいはZFC公理系と呼びます。我々が当たり前のように使っている数学(のほとんど)は、これら僅か9個のルールを基礎として築き上げられているのです。

参考文献

[1] 彌永昌吉,彌永健一 (1990), "集合と位相", 岩波書店
[2] G. Takeuti, W. M. Zaring (1971), "Introduction to Axiomatic Set Theory", Springer-Verlag