部分集合と冪集合

前回は自然数を集合として定義した。これによって、外延的記法を用いればいくつかの自然数だけが属する集合をいろいろ作れるようになった。そこで、この記事では集合同士の関係を新たに一つ導入する。

部分集合

これまで、モノ (集合) 同士の関係として2つの関係を説明した。一つは記号 $\in$ で表される関係であり\[x \in y\]を「$x$ が $y$ に属する」と解釈することにしている。たとえば $1\in\{0,1,2\}$ である。もう一つは記号 $=$ で表される「等しい・同じ」を表す関係であり\[x=y\]は「$x$ に属するモノがすべて $y$ にも属し、$y$ に属しているモノがすべて $x$ に属する」ことであると定めた (外延性の公理)。たとえば $0=0$ であり $\{3\}=\{3,3\}$ である。

今回は新たに $\subset$ で表される関係を次のように定める。

定義モノ (集合) $x$, $y$ が\[\forall z[z\in x \to z\in y]\]を満たすとき、つまり $x$ に属するモノがすべて $y$ にも属するとき、$x$ は $y$ の部分集合であり、そのことを $x\subset y$ と表す。

具体例を見てみよう。たとえば $\{1,2\}$ と $\{1,2,4\}$ について考えてみると、$\{1,2\}$ に属するモノは1と2である。そして、これらはすべて $\{1,2,4\}$ にも属している。したがって、$\{1,2\}$ は $\{1,2,4\}$ の部分集合であり\[\{1,2\}\subset \{1,2,4\}\]である。一方で、$\{1,2,4\}$ に属するモノは1と2と4であり、これらのすべてが $\{1,2\}$ に属しているわけではない (具体的には4が属していない)。したがって、$\{1,2,4\}$ は $\{1,2\}$ の部分集合ではない。このことはたいてい\[\{1,2,4\}\not\subset \{1,2\}\]と表す。

見落としがちな部分集合

この定義通りにとらえれば、部分集合について次のことが言える。

定理\[\forall x[\emptyset\subset x]\]

すなわち、空集合 $\emptyset$ はあらゆるモノ (集合) の部分集合である。

なぜなら、「空集合に属しているのに $x$ には属していないモノがある (つまり $\emptyset\not\subset x$)」という状況は起こりえないからである。したがって、たとえば\[\begin{array}{rcll}\emptyset&\subset& \{1,3\}&\\ \emptyset&\subset& 1&\text{($1$ とは $\{0\}$ のことである)}\\ \emptyset&\subset& \emptyset&\end{array}\]である。

また同じ集合同士でもこの関係は成立する。つまり $x$, $y$ がどんなモノ (集合) であっても\[x\subset x\]であり、$x=y$ であれば\[x\subset y,\;\;y\subset x\]である。このことは等しいとは何かを規定する外延性の公理と部分集合の定義をよく見比べるとわかる。実際、外延性の公理に書いてあることを「部分集合」という言葉を使って読み替えると次のようになる。

定理\[\forall x\forall y[x=y \leftrightarrow x\subset y \land y\subset x]\]

すなわち、いかなるもの $x$ と $y$ に対しても、「$x$ が $y$ の部分集合であり $y$ が $x$ の部分集合である」とき $x=y$ であり、そうでないときは $x\neq y$。

したがって、$x=y$ であれば $x\subset y$ と $y\subset x$ が共に成立するのであり、$x=x$ は当たり前に成立するからそこから直ちに $x\subset x$ も成立する。逆も言えるので、$x=y$ であることを証明したければ $x$ に属するモノがすべて $y$ に属している ($x\subset y$) ことと $y$ に属するものがすべて $x$ に属している ($y\subset x$) ことを証明すればよい

以上のことから、たとえば $\{1,2,3\}$ の部分集合を探そうとすると $\{1\}$, $\{2\}$, $\{3\}$, $\{1,2\}$, $\{1,3\}$, $\{2,3\}$ のほかに $\emptyset$ と $\{1,2,3\}$ も挙げられ、全部で8つの部分集合が挙げられることになる。厳密な証明は後の記事で「個数とは何か」を定義してから行うが、$n$ 個のモノだけが属する集合の部分集合は $2^n$ 個だけある。試しに $\{2,3,4,5\}$ の部分集合をすべて書き出してみて $2^4 = 16$ 個あることを確かめてみるとよいだろう。

包含関係の性質

$\subset$ で表される「部分集合である」という関係は包含関係と呼ばれる。この関係について成立することは上でも少し述べたが、ここで改めてまとめて書いておく。

定理任意のモノ $x$ について $x\subset x$。

(証明) $y$ がどんなモノであっても $y\in x$ であれば $y\in x$ であるので、$x\subset x$。

定理任意のモノ $x$, $y$ について $x\subset y$, $y\subset x$ であれば $x=y$。

(証明) 上でも示したように、$x\subset y$ であれば「$x$ に属するモノがすべて $y$ にも属する」のであり、$y\subset x$ であれば「$y$ に属するモノがすべて $x$ にも属する」。したがって $x\subset y$ と $y\subset x$ が共に成立するときは、「$x$ に属するモノはすべて $y$ に属し、$y$ に属するモノはすべて $x$ に属する」ことになるので、外延性の公理より $x=y$。

定理任意のモノ $x$, $y$, $z$ について $x\subset y$, $y\subset z$ であれば $x\subset z$。

(証明) $x\subset y$ であれば「$x$ に属するモノがすべて $y$ にも属する」のであり、$y\subset z$ であれば「$y$ に属するモノがすべて $z$ にも属する」。したがって $x\subset y$ と $y\subset z$ が共に成立するときは、「$x$ に属するモノはすべて $y$ に属し、そのため $z$ にも属する」ことになるので、$x\subset z$。

冪集合の公理

部分集合と深くかかわる公理 (ルール) があるのでここで導入しておく (次以降の記事で活用する)。

公理\[\forall x\exists y\forall z[z\in y\leftrightarrow \forall w[w\in z\to w\in x]]\]

すなわち、いかなるモノ (集合) $x$ に対しても「$x$ の部分集合がすべて属し、それ以外のモノが属さない集合」が存在する。

この公理によってモノ (集合) $x$ に応じてモノ (集合) の存在が示されるが、この存在が示された「$x$ の部分集合がすべて属し、それ以外のモノが属さない集合」のことを $x$ の冪集合とよぶ。何回 $x$ の冪集合を作っても外延性の公理よりそれらは同じモノであるので $x$ の冪集合は $x$ に対してただ一つしかない。そこで $x$ の冪集合を特別に\[\mathfrak{P}(x)\]と表す (この記法に関しての補足は後述)。この記法を使うと、$x$, $y$ がどんなモノであっても\[y\subset x \leftrightarrow y\in\mathfrak{P}(x)\]である ($y\subset x$ であれば $y\in\mathfrak{P}(x)$ であり、$y\in\mathfrak{P}(x)$ であれば $y\subset x$ である)。

たとえば $\{1,2,3\}$ の冪集合を考えてみると\[\mathfrak{P}(\{1,2,3\}) = \{\emptyset, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\}\}\]である。さて、気づいた者もいるかもしれないが、じつは $\{1,2,3\}$ の冪集合は冪集合公理を使うまでもなく存在が保障される。なぜなら、対の公理と和集合の公理により、外延的記法で厳密に書けるモノ (有限個のモノだけが属するモノ) の存在が保障されるからである。したがって\[\{\emptyset, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\}\}\]の存在の証明に冪集合の公理は必要ない。

冪集合公理が力を発揮するのは、無限集合の冪集合を考えるときである。たとえば前回作った「自然数だけがすべて属し、それ以外のものが属さない集合」である $\omega$ の部分集合を考えると\[\emptyset,\{0\},\{1\},\{2\},\{3\},\dots\]のように無限にある。したがって、「$\omega$ の部分集合がすべて属する集合」である $\omega$ の冪集合には無限にモノが属することになるので外延的記法で書くことができず、対の公理と和集合の公理では存在を証明できない。ここで冪集合公理を使えばそのような集合 $\mathfrak{P}(\omega)$ が存在することが直ちにわかる。

冪集合の表記

初めて $\mathfrak{P}(x)$ という表記を見た人の最初の感想はおそらく「何この文字」だろう。この $\mathfrak{P}$ はフラクトゥールと呼ばれる書体で書かれたラテン文字の P である。冪集合 (Power set) の頭文字というわけだ。

書籍によっては冪集合のことを単に $P(x)$ と書いたり、カリグラフィ文字を使って $\mathcal{P}(x)$ と書くこともあるだろう。また、$x$ の冪集合は「$x$ から {0,1} への写像だけをすべて含む集合」としてとらえることもできるという意味で $x$ の冪集合を $2^x$ と書くこともあるが、本シリーズではまだ『写像』を説明していないのでこれ以上深くは説明しないこととする。

数学の書籍では冪集合の $\mathfrak{P}$ のように通常と異なる書体の文字を使うことが多々あり、他の書体で書かれたものとは区別する。たとえば、「$m=\{1,2\}$ とし $\mathfrak{m}=\{\{1,2\}, \{1\}, \{2\}\}$ とする」というようなことがある。印刷物やwebページ上なら書体の区別はできるはずなので、このことを知識として知っていれば見落とすことはないだろう。

余談だが、フラクトゥールは「ドイツ 新聞」でグーグル画像検索をすると実際に使われている (使われていた?) 画像が出てくる。