Ryo Nakagami
2025-07-05
2025-07-09
Definition 1 べき集合
集合 \(M\) があたえられたとき，\(M\) の部分集合全体の作る集合を \(\mathfrak{B}(M)\) と表し，\(M\) のべき集合と呼ぶ．
\(M = \{1, 2\}\) のとき，\(M\)の部分集合全体の作る集合は
\[ \mathfrak{B}(M) = \{\emptyset, \{1\}, \{2\}, \{1,2\}\} \]
また，冪集合も集合なので，
\[ \begin{align*} \mathfrak{B}(\mathfrak{B}(M)) =& \{ \emptyset,\{\emptyset\}, \{\{1\}\}, \{\{2\}\}, \{\{1, 2\}\}, \\ & \{\emptyset, \{1\}\}, \{\emptyset, \{2\}\}, \{\emptyset, \{1,2\}\}, \{\{1\}, \{2\}\}, \{\{1\}, \{1,2\}\}, \{\{2\}, \{1,2\}\}, \\ & \{\emptyset, \{1\}, \{2\}\}, \{\emptyset, \{1\}, \{1,2\}\}, \{\emptyset, \{2\}, \{1,2\}\}, \{\{1\}, \{2\}, \{1,2\}\}\\ & \{\emptyset, \{1\}, \{2\}, \{1, 2\}\} \end{align*} \]
これらを元の個数の観点から見てみると
\[ \begin{align} |M| &= |\{1, 2\}| = 2\\ |\mathfrak{B}(M)| &= 2^2 = 4\\ |\mathfrak{B}(\mathfrak{B}(M))| &= 2^4 = 16 \end{align} \]
Definition 2 直積集合
2つの有限集合 \(M, N\) が与えられたとき，\(a\in M, b\in N\) からなる対 \((a, b)\) を考える．このような１つ１つの対を元と考え，この全体を１つの集合と考えたものを \(M\) と \(N\) の直積集合といい
\[ M\times N \]
と表す
Theorem 1 直積集合の濃度
集合 \(M\), \(N\) を有限集合とする．このとき，
\[ |M\times N| = |M| \times |N| \]
証明は直積集合の濃度を参照してください．
有限集合 \(M，N\) が与えられたとき，
\[ M^N \]
という集合を考えることができます．この集合は，\(N\) の元の個数だけ，\(M\) を直積させたものとして定義します．つまり， \(N = \{b_1, \cdots, b_n\}\) であるならば，
\[ M^N = \underbrace{M\times \cdots \times M}_{n個} \]
また，濃度についても以下のように計算ができます
\[ |M^N| = \underbrace{|M|\times \cdots \times |M|}_{n個} = m^n \]
Definition 3 写像
\(M, N\) を有限集合とします．\(M\) の各元から，\(N\) の各元を対応させる仕方が与えられているとき， \(M\) から \(N\) の写像 \(\varphi\) が与えられたという．
写像 \(\varphi\) によって \(a\in M\) が \(b\in N\) にうつされるとき
\[ b= \varphi(a) \]
とあらわす．
\(M = \{x, y, z\}\), \(N = \{0, 1\}\) のとき，MからNへの写像は以下のように \(2^3\) 個考えることができます．
| x | y | z | |
|---|---|---|---|
| 1 | 0 | 0 | 0 |
| 2 | 0 | 0 | 1 |
| 3 | 0 | 1 | 0 |
| 4 | 0 | 1 | 1 |
| 5 | 1 | 0 | 0 |
| 6 | 1 | 0 | 1 |
| 7 | 1 | 1 | 0 |
| 8 | 1 | 1 | 1 |
Definition 4 写像全体の集合
有限集合 \(M\) から 有限集合 \(N\) への写像の１つ１つを元と考えて，その全体を１つのまとまった集合と考えたものを
\[ \operatorname{Map}(M, N) \]
と表す．
Theorem 2 \[ |\operatorname{Map}(M, N)| = |N^M| \]
\(M = \{a_1, \cdots, a_m\}, N = \{b_1, \cdots, b_n\}\) とする．\(\varphi\) を \(\operatorname{Map}(M, N)\) の元とする．\(\varphi\) がきまるということは \(M\) の元の移り先が決まっていること，つまり
\[ (\varphi(a_1), \varphi(a_2), \cdots, \varphi(a_m)) \]
によって決まる．\(i=1, 2, \cdots, m\) について \(\varphi(a_i) \in N\) であるので
\[ (\varphi(a_1), \varphi(a_2), \cdots, \varphi(a_m)) \in N\times N\times \cdots \times N = N^M \]
逆に \(N^M\) の元 \((b_{i_1}, b_{i_2}, \cdots, b_{i_m})\) があたえられると
\[ \varphi(a_k) = b_{i_k} \]
で，\(M \to N\) の写像が定まる．従って，\(\operatorname{Map}(M, N)\) の元 \(\varphi\) と \(N^M\) の元が1対1対応している．従って，
\[ |\operatorname{Map}(M, N)| = |N^M| \]
べき集合との関係
有限集合 \(M\) に対して，その部分集合 \(S\) を１つとるということは \(x\in M\) に対して
であるので \(M\) から \(\{0, 1\}\) への写像 \(\varphi\) を１つ決めることと1対1対応します． 従って，\(\mathfrak{B}(M)\) の元と，\(\operatorname{Map}(M, \{0, 1\})\) が1対1に対応することから．\(m = |M|\) とすると
\[ |\operatorname{Map}(M, \{0, 1\})| = |\mathfrak{B}(M)| = 2^m \]
Example 1
\(M = \{a, b, c\}\) とするとそのすべての部分集合と対応する写像は
| 部分集合 \(S\) | 写像 \(\varphi: M \to \{0,1\}\) |
|---|---|
| \(\emptyset\) | \(\varphi(a)=0, \varphi(b)=0, \varphi(c)=0\) |
| \(\{a\}\) | \(\varphi(a)=1, \varphi(b)=0, \varphi(c)=0\) |
| \(\{b\}\) | \(\varphi(a)=0, \varphi(b)=1, \varphi(c)=0\) |
| \(\{c\}\) | \(\varphi(a)=0, \varphi(b)=0, \varphi(c)=1\) |
| \(\{a, b\}\) | \(\varphi(a)=1, \varphi(b)=1, \varphi(c)=0\) |
| \(\{a, c\}\) | \(\varphi(a)=1, \varphi(b)=0, \varphi(c)=1\) |
| \(\{b, c\}\) | \(\varphi(a)=0, \varphi(b)=1, \varphi(c)=1\) |
| \(\{a, b, c\}\) | \(\varphi(a)=1, \varphi(b)=1, \varphi(c)=1\) |
Definition 5 高々加算集合
集合 \(M\) が，有限集合か，加算集合のとき，\(M\) を高々加算集合という
\(M\) を加算集合として，\(S\subset M\) となるような無限集合を考えます．\(M\) は加算集合であるので
\[ M = \{a_1, a_2, \cdots, a_n, \cdots\} \]
と集合を \(\mathbb N\) と対応させて表現することができます．次に，\(S\) の元について，\(M\) の元の並び方のうち最初に \(S\) の元として現れるものを \(a_{i_1}\), 次は \(a_{i_2}, \cdots\) とすると
\[ S = \{a_{i_1}, a_{i_2}, \cdots\} \]
となります．\(S\) は定義より無限集合であり，また写像 \(\varphi: \mathbb N\to S\) を
\[ \varphi(n) = a_{i_n} \]
とすると，\(\varphi\) は1対1写像となります．従って，\(S\) は加算集合となります．つまり，\(M\) を加算集合とすると，\(M\) の任意の部分集合は高々加算集合ということになります．
Theorem 3
\(M\) を無限集合，\(A\) を高々加算集合とする．このとき，\(M\) と \(M\sqcup A\) の間には１対１の対応があり，そのため，２つの濃度は等しい:
\[ |M| = |M \sqcup A| \]
\(M\) から１つの元 \(b_1\) をとると，\(M - \{b_1\}\) は空襲号ではないので，同じ操作を繰り返すことができます．また，\(M\) は無限集合であるので，無限回繰り返して，その結果得られた \(b_i\) を以下のような集合で表現する
\[ B = \{b_1, b_2, \cdots, b_n, \cdots \} \]
このとき，\(B\subset M\) かつ \(B\) は加算集合です．加算集合と加算集合の和は加算集合なので \(B\sqcup A\) も加算集合となります．従って，\(B\) と \(B\sqcup A\) はある写像 \(\varphi\) によって1対1に対応します．
次に
\[ \tilde\varphi: (M-B) \sqcup B\to (M-B)\sqcup (B\sqcup A) \]
を考えます．
とすると，\(\tilde\varphi\) も1対1写像となります．
\[ \begin{align} M-B \sqcup B &= M\\ (M-B)\sqcup (B\sqcup A) &= M \sqcup A \end{align} \]
であることから
\[ |M| = |M| + |A| \]
これまでは有限集合を前提に話してきましたが，ここからは自然数集合 \(\mathbb N\) という加算無限集合を取り扱います．
\[ |\mathbb N| = \aleph_0 \]
であることに留意すると，
\[ |\mathfrak{B}(\mathbb N)| = 2^{\aleph_0} \]
これがどれくらいの濃度を持つのか考えてみます．
Theorem 4 \[ 2^{\aleph_0} = \aleph \]
濃度 \(2\) を持つ集合として \(\{0, 1\}\) を考えます．このとき，\(2^{\aleph_0}\) は，直積集合
\[ P = \{0, 1\}\times \{0, 1\}\times \{0, 1\}\times \cdots \]
の濃度と等しくなります．\(\aleph\) が実数集合の濃度と等しいので，\(|(0, 1]|= \aleph\) であることから
\[ |P| = |(0, 1]| \]
を示せれば良いとなります．
\(P\) の元は 0と1 からなる数列として，\((a_1, a_2, \cdots)\) と表せるので，これを2進小数で表現された実数と対応させることができます．つまり，
\[ 0.a_1a_2\cdots \]
\((0, 1]\) に属する実数を無限２進小数で表現すると，その表し方はただ１通りとなります．
次に，\((0, 1]\) に属する実数について，有限2進小数に表せる集合 \(S\) を考えてみます．このとき，\(S \subset \mathbb Q\) であることから
\[ |S| = \aleph_0 \]
次に，写像 \(\varphi: P\to (0, 1] \sqcup S\) を考えてみます．\(x\in P\) について，
\[ x = (a_1, \cdots, a_n, 0, 0, \cdots) \]
とあるところから先すべてが0になっているものについて，
\[ \varphi(x) = 0.a_1a_2\cdots a_n \in S \]
と対応させます．また，それ以外の場合は
\[ \varphi(x) = 0.a_1a_2\cdots a_n\cdots \in (0, 1] \]
となるので，\(x\in P \Rightarrow \varphi(x) \in ((0, 1] \sqcup S)\)，また \(\varphi\) は \(P\) から \((0, 1] \sqcup S\) に対して１対１の対応を与えてます．つまり，
\[ |P| = |(0, 1] \sqcup S| \]
また無限集合 Aと高々加算集合 B について Theorem 3 より
\[ |A| = |A\sqcup B| \]
であることから
\[ |P| = |(0, 1] \sqcup S| = |(0, 1]| \]
従って，
\[ 2^{\aleph_0} = \aleph \]