内包的記法と共通部分

前回まででは、各自然数や自然数集合 $\omega$ を集合として定義したうえで、冪集合公理を導入することで多様な集合の存在を示すことができるようになった。今回は部分集合の存在を示す公理を導入することで、より多くの集合の存在を示せるようにする。

部分集合の存在証明はしていない

前回の記事では部分集合というものを定義したが、まだ部分集合を作る方法は述べていない。この点を勘違いしている者もいるかもしれないので詳解する。

属するモノの数が有限である部分集合は外延的記法で記述できるので、対の公理と和集合の公理によってその存在は保証される。しかし、この方法では例えば自然数集合 $\omega$ の部分集合である「偶数だけが属する集合」のようにモノが無限に属する部分集合の存在は示せない。また、冪集合公理は部分集合がすべて属する集合の存在を保証するが、具体的に何が属しているかを述べているわけではない。つまり冪集合公理から言えるのは「$x$ の部分集合 $y$ がもし存在するなら、その $y$ は $x$ の冪集合 $\mathfrak{P}(x)$ に属する」ということである。

以上のことから、現段階では外延的記法で書けない部分集合についてはその存在が保障されていないことがわかるだろう (そもそも無限にモノが属する集合は $\omega$ とその冪集合とその冪集合と ... しかその存在を証明できていない)。今回は、そのような部分集合の書き表し方と、その部分集合が存在する根拠となる公理を述べる。

部分集合の内包的記法

ここでまず部分集合の作り方を述べることにする。$x$ の部分集合の表し方として「$x$ に属しているモノのうち、$\psi(y)$ を満たすような $y$ だけがすべて属する集合 (そのような集合は外延性の公理より一つしかない)」を\[\{y\in x \mid \psi(y)\}\]で表すことにし、この記法を内包的記法とよぶ。この集合には $x$ に属するモノしか属していないので、$x$ の部分集合である。

わかりにくいと思うので例を示す。たとえば「$\omega$ に属しているモノ (つまり自然数) のうち、偶数だけがすべて属する集合」は\[\{y\in\omega \mid \text{$y$ は偶数}\}\]と表せる (注: このシリーズでは掛け算や偶数を定義していないが簡潔に例示するために用いた)。この例では $x$ に $\omega$ を当てはめ、$\psi(y)$ に「$y$ は偶数」を当てはめた。なお、$y$ の部分は (他と干渉しなければ) 何でもよく、たとえば\[\{t\in\omega \mid \text{$t$ は偶数}\}\]と書いても全く同じである。

この記法を使えば、すでに存在がわかっているモノの部分集合であれば、モノが無限に属する集合であっても記述することができる。

内包的記法の例

さらにいくつか例示していくが、そのためにこの節では自然数の四則演算や大小関係や個数の概念を用いる。本シリーズではそのいずれもまだ定義していないので、この段階では以下に示す集合の存在を論理的には示せないことに留意しつつ見てほしい。

先ほど示した「偶数だけがすべて属する集合」をもう少し細かく書こう。「$x$ が偶数である」とは「$x=2y$ を満たす自然数 $y$ が存在する (論理式で書くと $\exists y[x=2y]$)」ということなので「偶数だけがすべて属する集合」は\[\{x\in\omega\mid \exists y[x=2y]\}\]と書ける。こうすると $\psi(x)$ の部分が (自然数の掛け算を含んではいるが) 論理式のようになる。

次に「5より大きい自然数だけがすべて属する集合」を作ってみる。つまり $\omega$ に属するモノのうち $5\lt x$ の $x$ に当てはまるようなモノだけがすべて属していればよいので\[\{x\in\omega \mid 5\lt x\}\]となる。自然数の定義のときにちらっと述べたが、$n$ と $m$ が自然数であれば $n\in m$ と $n\lt m$ はちょうど一致する (ように自然数を作った) ので、上の集合は\[\{x\in\omega \mid 5\in x\}\]とも書ける。まさに集合論の言葉だけで記述できている。

もう一つ、今度は趣向を変えて $\omega$ の冪集合 $\mathfrak{P}(\omega)$ の部分集合を考えてみる。集合 $E$ を\[E=\{x\in\mathfrak{P}(\omega) \mid \text{$x$ にちょうど二つのモノが属する}\}\]としたらどうなるだろうか。たとえば $\{1,2,3\}$ は $\omega$ の部分集合なので $\{1,2,3\}\in\mathfrak{P}(\omega)$ であるが「$\{1,2,3\}$ にちょうど二つのモノが属する」わけではないので \[\{1,2,3\}\not\in E\]であり、一方で $\omega$ の部分集合 $\{4,5\}$ にはちょうど二つのモノが属するので \[\{4,5\}\in E\]である。このようにして $E$ は「$\mathfrak{P}(\omega)$ に属するモノ (つまり $\omega$ の部分集合) のうち、モノがちょうど二つだけ属するものだけがすべて属する集合」となる。

分出公理

では、上の記法で作られるモノ (集合) の存在を保証する公理 (ルール) を導入する。

公理$\psi$ が1つの自由変数を持つ論理式であるとする。このとき\[\forall x\exists y \forall z[z\in y\leftrightarrow z\in x \land \psi(z)].\]

すなわち、いかなるモノ (集合) $x$ に対しても「$x$ に属するモノのうち、$\psi(z)$ であるような $z$ がすべて属し、それ以外のモノが属さない集合」が存在する。

この公理はまさに $x$ の部分集合 $\{y\in x\mid \psi(y)\}$ の存在を示すものである。

内包的記法の制限

この記事で、内包的記法は部分集合を記述する方法であると紹介した。では、既存の集合の部分集合でないものは内包的記法で記述できないのであろうか。普通、この問いに対しては「そうではない」となる。分出公理では部分集合であるものしか存在を証明できないが、この公理の代わりに置換公理を採用すれば部分集合でないものについても (一部は) 存在が証明できるようになる。ただ、置換公理は複雑であることと、本シリーズ内の話題については分出公理だけで (おそらく) 証明できるので取り上げないこととした。したがって、本シリーズでは内包的記法は専ら部分集合を記述する方法として用いる。

また、置換公理を採用しても内包的記法が直感的に無制限に使えるようになるわけではない。たとえば、$S$ を「すべてのモノが属する集合」とすると、$x=x$ のようないつでも成立する論理式を使って、直感的な内包的記法で\[S=\{x\mid x=x\}\]と書けそうだが、このような集合の存在は置換公理からも証明できない。むしろ、これの存在を許すと分出公理や置換公理より\[R=\{x\in S\mid x\not\in x\}\]も存在することになるが、ここから $R\in R$ と $R\not\in R$ の両方が導かれて矛盾 (ラッセルのパラドックス) となるので、$S$ は (そして $R$ も) 存在が証明できないだけではなく、存在してはならない。もしこれらの存在を証明できる公理 (ルール) を導入すれば、その論理は (代わりに別の公理の採用を取りやめない限り) 矛盾を含む論理となる。

共通部分

内包的記法を使えるようになった今なら共通部分の存在を容易に示せる。まず共通部分とは何かを確認しておく。

定義$x$ が空集合ではないモノ (集合) であるとする。「$x$ に属するすべてのモノに属するモノが属し、それ以外のモノが属さない集合」を共通部分とよび、 $\bigcap x$ と書き表す。

和集合のときと同様で、$x$ に属するモノが有限個ならたとえば \[\bigcap \{y,z\} = y\cap z\] のように $x$ に属するモノで記号 $\cap$ を挟んだ表記も使う。具体例を出すと $\{\{1,2,3\}, \{2,3,4\}, \{3,4,5\}\}$ に属するモノは $\{1,2,3\}$ と $\{2,3,4\}$ と $\{3,4,5\}$ であり、そのすべてに属するモノは 3 だけなので共通部分は「3だけが属し、それ以外のモノが属さない集合」である $\{3\}$ であり、つまり\begin{eqnarray}\bigcap \{\{1,2,3\}, \{2,3,4\}, \{3,4,5\}\} &=& \{3\}\\ \{1,2,3\}\cap\{2,3,4\}\cap \{3,4,5\} &=& \{3\}\end{eqnarray}である。

共通部分は上述の内包的記法で表現できるので分出公理よりその存在は証明される。まず簡単なものを書いておくと\[y\cap z =\{w\in y\mid w\in z\}\]のように2つの集合の共通部分を内包的記法で書ける。より一般に $\bigcap x$ も次のように内包的記法で書ける。$x$ は空でないので、少なくとも一つのモノが $x$ に属している。それを $y$ とする (つまり $y\in x$ とする) と\[\bigcap x=\{w\in y \mid \forall z[z\in x \to w\in z]\}\]のように $\bigcap x$ も内包的記法で書ける。したがって、共通部分 $\bigcap x$ は分出公理より存在する。

差集合

また、差集合も内包的記法で表現することができる。差集合は以下のように定義される。

定義$x$ と $y$ がモノ (集合) であるとする。「$x$ に属して $y$ に属さないモノがすべて属し、それ以外のモノが属さない集合」を差集合とよび、 $x\setminus y$ と書き表す。

例えば、$3=\{0,1,2\}$ であって $5=\{0,1,2,3,4\}$ であるので $5\setminus 3$ は $\{3,4\}$ である。たまに差集合のことを $x-y$ と書く場合もあるが、我々の論理では $2=\{0,1\}$ であるので、差集合 $5\setminus 3$ のことを $5-3$ と書くと外延性の公理より\[5-3\neq 2\]とかなりややこしいことになる。なので、差集合のことを引き算の記号で表すことはしないと固く心に決める。

もう一つ例を出しておく。$\{1,2,3\}\setminus\{2,3,4\}$ を考えると、これは「1 か 2 か 3 であって 2 か 3 か 4 ではないモノがすべて属し、それ以外のモノが属さない集合」なので、1 だけが属することになり\[\{1,2,3\}\setminus\{2,3,4\} = \{1\}\]である。

さて、このような差集合 $x\setminus y$ は $x$ の部分集合として\[\{z\in x \mid z\not\in y\}\]のように内包的記法で書けるので、分出公理により存在する。