Rei Frontier Tech Blog

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

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

レイ・フロンティア株式会社のデータアナリストの齋藤です。
今回皆様にお話するのは、現代数学の土台であり、我々が普段接する数学的対象をつくる素材を提供してくれる、ZFC公理系にまつわるお話です。

はじめに

集合とは「ものの集まり」を厳密に考える数学的対象のことで、数や図形、関数など現代の数学に登場するほとんど全ての概念が集合の言葉で書かれていると言っても過言ではありません。
集合が何たるかについては、集合論の創始者といわれるゲオルク・カントール(Georg Cantor)の著書"超限集合論"のつぎの言葉によって的確に表現されています:

'集合'とは一つの総体\(M\)であり、それを形成するもの\(m\)(それは\(M\)の'要素'とよばれる)は、それぞれ確定し、互いに識別され得る、われわれの直感または思惟の対象である。
カントールは集合論の研究を推し進め、数や図形にとどまらず、"ものの集まり"として考えることのできるあらゆるものを数学の対象にしようと試みました。しかし、そのような試みは集合論の内部からパラドックスの数々が見出されたことで致命的な危機にさらされることになりました。
(初期)集合論のパラドックスの一つとして有名なのが、ラッセル(Russell)のパラドックスでしょう。それは次のようなものです。集合について考えるとき、できるだけ普遍的な集合を想定するのが自然な考え方ですが、最も普遍的な集合は何かというと、それは「集合全体からなる集合\(\mathbb{S}\)」でしょう。\(\mathbb{S}\)はそれ自体が集合なので、当然\(\mathbb{S}\)の要素です。しかし、たとえば自然数の集合\(\mathbb{N}\)それ自体は自然数ではないので、\(\mathbb{N}\)の要素ではありません。このように、集合、すなわち\(\mathbb{S}\)の要素の中には「自分自身を要素として含まない集合」が存在しています。そのような集合の全体を\(\mathbb{A}\)とおきます。
さて、\(\mathbb{A}\)という集合は\(\mathbb{A}\)の要素でしょうか。もしYesであるならば、\(\mathbb{A}\)の定義により\(\mathbb{A}\)は\(\mathbb{A}\)の要素ではなくなってしまうので矛盾です。Noであるならば、やはり\(\mathbb{A}\)の定義により\(\mathbb{A}\)は\(\mathbb{A}\)の要素になってしまうのでこれまた矛盾してしまいます。
このようなパラドックスを回避するために、ツェルメロ(Zermelo)らによって集合論の公理系が整備されました。現代の数学者のほとんどはZFCと呼ばれる、ツェルメロとフレンケル(Fraenkel)による8つの公理に選択公理(Axiom of Choice)と呼ばれる公理を付け加えた公理系のもとで展開される数学を研究しています。そこでは、自然数や実数、関数、ベクトルと行列などなど身近な数学的対象は問題なく構成されており、私たちは(それなりに)安心して数学を利用することができています。
本記事の目標は、このZFC公理系に含まれる公理たちを、身近な数学的対象の代表といえる自然数とその全体\(\mathbb{N}\)を構成しながら紹介することです。

命題と論理式

命題(proposition)とは、数学的対象について論理記号や演算記号などを用いて記述された文章で、真であるかあるいは偽であるという性質をもつものです。たとえば、"\(1+1=2\)"であるとか、"\(\ \triangle ABC\)において\(AB=AC\)"などがそれに該当します。
与えられた命題\(P\)に対して、その否定、すなわち"\(P\)ではない"という命題のことを、$$\lnot P$$と書きます。また、命題\(P,Q\)が与えられたとき、"\(P\)または\(Q\)"という命題のことを\(P \vee Q\)と書き、"\(P\)かつ\(Q\)"のことを\(P \wedge Q\)と書きます。"\(P\)ならば\(Q\)"という命題は\(P \Rightarrow Q\)あるいは\(Q \Leftarrow P\)と書きます。これは\(\lnot P \vee Q\)と同じ意味です。命題\(P \Rightarrow Q \wedge P \Leftarrow Q\)のことを\(P \Leftrightarrow Q\)と書き、これが成り立つとき\(P\)と\(Q\)は同値であるといいます。
対象\(x\)についての命題を\(P(x)\)のように表すことがあります。\(P(x)\)は\(x\)を変数(variable)とする命題とよびます。この場合、\(x\)はある決まった集まり(あるいは族)に属するものとされます。
(与えられた族に属する)任意の対象\(x\)について、命題\(P(x)\)が成り立つことを主張する命題を、$$\forall xP(x)$$と書きます。また、対象\(x\)で命題\(P(x)\)が成立するようなものが存在するという命題を、$$\exists xP(x)$$と書きます。
これらの記号を用いて、たとえば、与えられた族に属する対象\(x\)についての命題\(P(x)\)が与えられたとき、$$\lnot (\forall xP(x)) \Leftrightarrow \exists x\lnot P(x)$$である……といった風な表現がなされます。これから説明していくZFC公理系の一つ一つも、これらの記号を組み合わせた論理式によって表現されます。

外延性公理と集合

集合論で扱われる対象のことを集合(set)とよびます。正確には、以下に述べる公理(Set1)-(Set9)をみたす対象のことを集合といいます。9つの公理を設ける目的は、数や関数などの大昔から広く受け入れられている数学的対象の諸々を再構成し、なおかつ"集合全体の集合"といったあまりに"大きすぎる"集まりを集合の世界から締め出すことにあります。
集合論的な命題を作るために、新しい記号\(\in, \ni\)を導入しましょう。命題$$a \in b \quad (または\ b \ni a)$$は、「\(a\)は\(b\)の元(または要素)(element)である」といい、否定命題\(\lnot (a \in b)\)のことを$$a \not\in b \quad (または\ b \not\ni a)$$と書きます。
ここで、最初の公理をおきましょう:

(Set1) 外延性公理$$\forall a \forall b [ a = b \Leftrightarrow \forall x (x \in a \Leftrightarrow x \in b)] .$$
外延性公理を"普通の言葉"で述べると、「任意の集合\(a,b\)について、\(a=b\)であるための必要十分条件は、任意の\(x\)に対して\(x \in a \Leftrightarrow x \in b\)が成り立つことである」となります。この公理によれば、集合は「それがどんな元を含むか」によって決定されるのです。集合の元どうしがどのように関係しあっていたとしても、その集合の(集合論的な)特徴づけには一切関与しません。
集合\(a,b\)について、\(\forall x (x \in a \Rightarrow x \in b\)が成り立つとき、「\(a\)は\(b\)の部分集合(subset)である」といい、これを\(a\subset b\)あるいは\(b \supset a\)と表します。

つぎの公理は、集合が(少なくとも1つ)存在することを、ある具体的な集合を論理式を用いて厳密に定めることによって主張するものです:

(Set2) 空集合の存在公理$$\exists a \forall x [\lnot (x \in a)].$$
"普通の言葉"でいうと、「このような元をも含まない集合\(a\)が存在する」というものです。
定理1.集合\(a\)が空集合となるための必要十分条件は、\(a\)が任意の集合\(x\)の部分集合となることである。
(証明) まず\(z\)をひとつの空集合とし、\(\forall x (x \supset z)\)が成り立つことを示す。そのためには、\(\forall y (y \in z \Rightarrow y \in x)\)を示せば良い。ところが、命題$$y \in z \Rightarrow y \in z$$の対偶は$$\lnot (y \in x) \Rightarrow \lnot (y \in z)$$であるが、空集合の定義によりこれは任意の\(y\)について成り立つ。
つぎに、集合\(a\)について\(\forall x (a \subset x)\)が成り立つとすると、とくに\(a \subset z\)となるが、上の議論により\(z \subset a\)であり、一般に\(a \subset z \wedge z \subset a \Leftrightarrow a = z\)であることより\(a =z \)となり、したがって\(a\)は空集合である。■
系.空集合は確定する。
(証明) 集合\(a,b\)について\(\forall x [\lnot (x \in a) ]\)と\(\forall x [\lnot (x \in b) ]\)が同時に成り立つとすれば、定理により\(a\subset b \wedge b\subset a \)が成り立つため、\(a =b \)となる。■

この系によって一つに定まる空集合を\(\emptyset\)と書きます。これでようやく、「何も含まない集合」という具体的な集合を得ることができました。

非順序対と合併

われわれは前節で要素の個数が0の集合\(\emptyset\)を得ることができましたが、普段当たり前のように接している有限集合\(\{a\}\)、\(\{1,2\}\)などはまだ知らないものとして議論を進めています。このような集合の存在を許すためには、新しい公理が必要です:

(Set3) 非順序対の存在公理$$\forall a \forall b \exists c \forall x (x \in c \Leftrightarrow x =a \vee x = b) .$$
"普通の言葉"で述べると、「任意の集合\(a,b\)に対して、\(a,b\)を元として含み、それ以外の元を含まない集合\(c\)が存在する」というものです。この集合\(c\)は\(a,b\)の非順序対(unordered pair)と呼ばれ、\(\{ a,b \}\)と書かれます。\(x=a \wedge x=b\)と\(x=b \wedge x=a\)は同値であるため、外延性公理によって\(\{a,b\} = \{b,a\}\)が成り立ちます。
集合\(\{ a,a \}\)を\(a\)のシングルトン(singleton)とよび、\(\{a\}\)と書きます。空集合のシングルトン\(\{\emptyset\}\)は、空集合を元として含むので空集合ではありません。こうして、非順序対の存在公理によって空でない集合を手にすることができました。

集合\(a,b,c\)について、\(\{ \{a,b\}, \{c\}\}, \{ \{a,c\}, \{b\}\}\)といった集合の存在は非順序対の存在公理によって示すことができます。では、\(\{a,b,c\}\)と書かれる集合の存在を示すことはできるでしょうか。一般にそういった集合の存在を許すのが、次の公理です。

(Set4) 合併集合の公理$$\forall a \exists b \forall x [x \in b \Leftrightarrow c (c \in a \wedge x \in c)] .$$
"普通の言葉"で述べると、「任意の集合\(a\)に対して集合\(b\)が存在し、任意の\(x\)に対して、\(x \in b\)となることと、\(x\)が\(a\)に含まれるある集合\(c\)の元となることが同値である」ということになります。ここで、\(b\)は\(a\)の元の元全体からなる集合と呼ばれます。外延性公理によりそのような集合は確定し、\(b\)は\(a\)に含まれる集合全体の合併と呼び、$$\bigcup_{c \in a}c$$あるいは$$\bigcup a$$と表します。また、集合\(a,b\)に対して\(c = \{a,b\}\)とするとき、\(\cup c\)を\(a\)と\(b\)の合併(union)とよび、\(a \cup b\)と表します。定義から、明らかに$$\forall x (x \in a \cup b \Leftrightarrow x \in a \vee x \in b)$$です。
明らかに\(\{a,b\} = \{a\} \cup \{b\}\)となり、したがって$$\begin{align} \{a,b\}\cup \{c\} &= (\{a\}\cup\{b\}) \cup \{c\} = \{a\} \cup \{b,c\} \\ &= \{a\}\cup \{c,b\} = \{a,c\}\cup \{b\} = \cdots \cdots \end{align}$$となります。\(\{a,b\}\cup \{c\}\)を\(\{a,b,c\}\)と表し、これを\(a,b,c\)からなる(非順序)組と呼びます。同様に、\(\{a,b,c\}\cup \{d\}\)を\(\{a,b,c,d\}\)などと書きます。

無限公理と無限系譜

さて、前節までの議論から次のことがわかります。空集合\(\emptyset\)が確定します。また、\(\emptyset\)のシングルトン\(\{\emptyset\}\)は\(\emptyset\)とは異なる集合です。また、\(\{\emptyset, \{\emptyset\}\} = \{\emptyset\} \cup \{\{\emptyset\}\}\)はこれら2つを部分集合として含みますが、どれとも異なります。
このようにして、つぎつぎと新しい集合を構成してゆくことができるのではないでしょうか。そして、集合論的に自然数\(0,1,2,3,\dots\)が存在し、よく知られた性質を満たすことを証明できるのではないでしょうか? そのためには、まず\(0\)とか\(1\)とかいった対象を集合論的に与える必要があります。そこで、我々が今持っている道具を用いて、$$\begin{align} 0 &= \emptyset , \\ 1 &= \{\emptyset\} = 0 \cup \{0\} , \\ 2 &= 1 \cup \{1\} = \{\emptyset, \{\emptyset\}\} = \{0,1\} , \\ 3 &= 2 \cup \{2\} = \{0,1,2\} , \\ &= \cdots \cdots \end{align}$$などと定義します。

一般に集合\(a\)が与えられたときに、非順序対の存在公理と合併集合の公理によって存在が保証される集合\(a \cup \{a\}\)を\(a\)の後継ぎと呼び、\(a^+\)と表します。たとえば、\(1 = 0^+ , 2 = 1^+, \dots\)となります。こうして、\(0 = \emptyset\)から始めて後継ぎを順々に取っていくことにより、我々は自然数を具体的に手にすることができるのです。
しかし、ここで問題が生じます。こうして得られた"自然数"の全体の集まりは、集合であるといえるのでしょうか。そして、もしそうであるならば、それを"自然数の集合"と呼んでよいでしょうか。こういった問題を解決するための第一歩として、また新しい公理を導入することにしましょう。

(Set5) 無限公理$$\exists a [ \emptyset \in a \wedge \forall x ( x \in a \Rightarrow x^+ \in a)] .$$
"普通の言葉"で述べると、「集合\(a\)で、\(\emptyset\)を含み、かつ任意の集合\(x\)について、\(x\in a\) ならば\(x^+ \in a \)となるようなものが存在する」と言い表せます。集合\(a\)が無限公理の条件をみたすとき、\(a\)を無限系譜と呼ぶことにします。
無限系譜は、少なくとも一つ存在しますが、一つに確定してはいません。"自然数の全体"という集合を構成するためには、無限系譜から"無駄なものを取り除く"という操作をすることが必要です。そのような操作を可能にするために、次節で述べる分出公理が用いられます。

分出公理と共通部分

次の公理を導入しましょう。

(Set6') 分出公理$$\forall a \exists b \forall x (x \in b \Leftrightarrow x \in a \wedge P(x)) .$$
"普通の言葉"で述べると、「任意の集合\(a\)に対して、\(P(x)\)が成り立つような\(a\)の元\(x\)の全体からなる\(a\)の部分集合\(b\)が存在する」といえます。番号にダッシュ'がついているのは、分出公理は後々に出てくる公理から証明されるので、ZFCに数える必要がないためです。外延性公理によってこのような\(b\)は確定し、\(\{x \in a \mid P(x)\}\)と表されます。
集合\(a,b\)に対して、集合\(\{x \in a \mid x \in b\}\)を\(a,b\)の共通部分とよび、\(a \cap b\)と表します。定義から明らかに次の命題が成り立ちます:$$\forall x (x \in a \cap b \Leftrightarrow x \in a \wedge x \in b).$$前節で定義された集合\(0,1,2,3,\dots\)について、$$0\cap a= 1 , 1\cap 2= 1, 1\cap 3= 1, 2\cap 3= 2, \dots$$などが成立します。
集合\(a,b,c\)に対して\((a\cap b)\cap c\)を\(a,b,c\)の共通部分とよび、\(a\cap b\cap c\)と表します。同様に、集合\(a,b,c,d\)について\((a\cap b\cap c)\cap d\)を\(a,b,c,d\)の共通部分とよび\(a\cap b\cap c\cap d\)、などと順次定義されます。このようなことを一般的に考えるために、\(a\)を空集合と異なる集合として、\(b\in a\)に対して$$\bar b = \{ x \in b \mid \forall y (y \in a \Rightarrow x \in y) \}$$を考えましょう。\(\bar b\)は、\(b\)の元で\(a\)のすべての元に含まれるもの全体からなる\(b\)の部分集合です。一般に、任意の\(x\)について、\(b\in a\)から、つぎの命題が成り立ちます:$$x\in \bar b \Leftrightarrow \forall y (y \in a \Rightarrow x \in y) .$$したがって、もし\(c\in a\)ならば\(\bar b = \bar c\)となり、\(\bar b\)は\(a\)の元\(b\)のとり方によらずに定まります。\(\bar b\)を\(a\)の元の共通部分(intersection)とよび、$$\bigcap_{x \in a}x$$または$$\bigcap a$$と書きます。とくに、\(a = \{b,c\}\)のとき、\(a\)の元の共通部分は\(b\cap c\)に他なりません。

次の定理が成り立ちます。

定理2.集合\(a\)に対して、\(a^\prime = \{x \in a \mid x \not\in x\}\)とすると、\(a^\prime \not\in a\)。
(証明) 命題\(P\)として\(a^\prime \in a\)を、命題\(Q\)として\(a^\prime \in a^\prime\)をとり、\(P \Rightarrow Q \wedge \lnot Q\)を示す。そうすれば\(\lnot P\)すなわち\(a^\prime \not\in a\)が成り立つ(背理法)。\(P\)が成り立つとすると、\(\lnot Q \Leftrightarrow P \wedge \lnot Q\)が成り立つが、\(a^\prime\)の定義によって\(P\wedge \lnot Q\)すなわち\( (a^\prime \in a)\wedge (a^\prime \not\in a^\prime) \)と\(Q\)すなわち\(a^\prime \in a^\prime\)とは同値である。ゆえに命題\(P\Rightarrow (\lnot Q \Leftrightarrow Q)\)が成り立つが、\(\lnot Q \Leftrightarrow Q\)は\(Q \wedge \lnot Q\)と同値であるので、\(P \Rightarrow Q \wedge \lnot Q\)が成り立つ。■
系.$$\forall a \exists b (b \not \in a) .$$
この系によって、どのような集合\(a\)をとっても、\(a\)に含まれない集合(たとえば\(a^\prime \))が存在することがわかります。したがって、"集合全体の集まり"は集合でないということになり、Russellのパラドックスは無事回避されたことになります。


自然数全体の集合はまだ定義されていませんが、きりがよいので本記事はここまでとします。次回で、自然数全体の集合\(\mathbb{N}\)と有名なペアノ(Peano)の公理、そしてZFC公理系の残りについて説明することにします。