集合 (0,1)^N の濃度 – regmonkey datascience blog

べき集合

定義 1 べき集合

集合 M があたえられたとき，M の部分集合全体の作る集合を 𝔅(M) と表し，M のべき集合と呼ぶ．

M = {1, 2} のとき，Mの部分集合全体の作る集合は

𝔅(M) = {∅, {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} $$

直積集合

定義 2 直積集合

2つの有限集合 M, N が与えられたとき，a ∈ M, b ∈ N からなる対 (a, b) を考える．このような１つ１つの対を元と考え，この全体を１つの集合と考えたものを M と N の直積集合といい

M × N

と表す

定理 1 直積集合の濃度

集合 M, N を有限集合とする．このとき，

|M × N| = |M|×|N|

Proof

証明は直積集合の濃度を参照してください．

集合 M^N

有限集合 M，N が与えられたとき，

M^N

という集合を考えることができます．この集合は，N の元の個数だけ，M を直積させたものとして定義します．つまり， N = {b₁, ⋯, b_n} であるならば，

$$ M^N = \underbrace{M\times \cdots \times M}_{n個} $$

また，濃度についても以下のように計算ができます

$$ |M^N| = \underbrace{|M|\times \cdots \times |M|}_{n個} = m^n $$

M から N への写像全体の作る集合

定義 3 写像

M, N を有限集合とします．M の各元から，N の各元を対応させる仕方が与えられているとき， M から N の写像 φ が与えられたという．

写像 φ によって a ∈ M が b ∈ N にうつされるとき

b = φ(a)

とあらわす．

M = {x, y, z}, N = {0, 1} のとき，MからNへの写像は以下のように 2³ 個考えることができます．

コード

from itertools import product
import pandas as pd

# 集合の定義
M = ['x', 'y', 'z']
N = [0, 1]

# 写像の全列挙
mappings = list(product(N, repeat=len(M)))

# DataFrameに変換
df = pd.DataFrame(mappings, columns=M)
df.index = df.index + 1  # 1始まりにする

# 表示
df

	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

定義 4 写像全体の集合

有限集合 M から有限集合 N への写像の１つ１つを元と考えて，その全体を１つのまとまった集合と考えたものを

Map (M, N)

と表す．

定理 2 |Map (M, N)| = |N^M|

Proof

M = {a₁, ⋯, a_m}, N = {b₁, ⋯, b_n} とする．φ を Map (M, N) の元とする．φ がきまるということは M の元の移り先が決まっていること，つまり

(φ(a₁), φ(a₂), ⋯, φ(a_m))

によって決まる．i = 1, 2, ⋯, m について φ(a_i) ∈ N であるので

(φ(a₁), φ(a₂), ⋯, φ(a_m)) ∈ N × N × ⋯ × N = N^M

逆に N^M の元 (b_i₁, b_i₂, ⋯, b_{i_m}) があたえられると

φ(a_k) = b_{i_k}

で，M → N の写像が定まる．従って，Map (M, N) の元 φ と N^M の元が1対1対応している．従って，

|Map (M, N)| = |N^M|

べき集合との関係

有限集合 M に対して，その部分集合 S を１つとるということは x ∈ M に対して

「含める」か「含めない」かをきめる
「含めるを1」「含めないを0」とするならば写像 φ : M → {0, 1} を１つ決めることと同じ

であるので M から {0, 1} への写像 φ を１つ決めることと1対1対応します．従って，𝔅(M) の元と，Map (M, {0, 1}) が1対1に対応することから．m = |M| とすると

|Map (M, {0, 1})| = |𝔅(M)| = 2^m

例 1

M = {a, b, c} とするとそのすべての部分集合と対応する写像は

部分集合 S	写像 φ : M → {0, 1}
∅	φ(a) = 0, φ(b) = 0, φ(c) = 0
{a}	φ(a) = 1, φ(b) = 0, φ(c) = 0
{b}	φ(a) = 0, φ(b) = 1, φ(c) = 0
{c}	φ(a) = 0, φ(b) = 0, φ(c) = 1
{a, b}	φ(a) = 1, φ(b) = 1, φ(c) = 0
{a, c}	φ(a) = 1, φ(b) = 0, φ(c) = 1
{b, c}	φ(a) = 0, φ(b) = 1, φ(c) = 1
{a, b, c}	φ(a) = 1, φ(b) = 1, φ(c) = 1

無限集合と高々加算集合の直和

定義 5 高々加算集合

集合 M が，有限集合か，加算集合のとき，M を高々加算集合という

M を加算集合として，S ⊂ M となるような無限集合を考えます．M は加算集合であるので

M = {a₁, a₂, ⋯, a_n, ⋯}

と集合を ℕ と対応させて表現することができます．次に，S の元について，M の元の並び方のうち最初に S の元として現れるものを a_i₁, 次は a_i₂, ⋯ とすると

S = {a_i₁, a_i₂, ⋯}

となります．S は定義より無限集合であり，また写像 φ : ℕ → S を

φ(n) = a_{i_n}

とすると，φ は1対1写像となります．従って，S は加算集合となります．つまり，M を加算集合とすると，M の任意の部分集合は高々加算集合ということになります．

定理 3

M を無限集合，A を高々加算集合とする．このとき，M と M ⊔ A の間には１対１の対応があり，そのため，２つの濃度は等しい:

|M| = |M ⊔ A|

Proof

M から１つの元 b₁ をとると，M − {b₁} は空襲号ではないので，同じ操作を繰り返すことができます．また，M は無限集合であるので，無限回繰り返して，その結果得られた b_i を以下のような集合で表現する

B = {b₁, b₂, ⋯, b_n, ⋯}

このとき，B ⊂ M かつ B は加算集合です．加算集合と加算集合の和は加算集合なので B ⊔ A も加算集合となります．従って，B と B ⊔ A はある写像 φ によって1対1に対応します．

次に

φ̃ : (M − B) ⊔ B → (M − B) ⊔ (B ⊔ A)

を考えます．

x ∈ M − B ならば φ̃(x) = x
x ∈ B ならば φ̃(x) = φ(x)

とすると，φ̃ も1対1写像となります．

$$ \begin{align} M-B \sqcup B &= M\\ (M-B)\sqcup (B\sqcup A) &= M \sqcup A \end{align} $$

であることから

|M| = |M|+|A|

𝔅(ℕ) の濃度

これまでは有限集合を前提に話してきましたが，ここからは自然数集合 ℕ という加算無限集合を取り扱います．

|ℕ| = ℵ₀

であることに留意すると，

|𝔅(ℕ)| = 2^ℵ₀

これがどれくらいの濃度を持つのか考えてみます．

定理 4 2^ℵ₀ = ℵ

Proof

濃度 2 を持つ集合として {0, 1} を考えます．このとき，2^ℵ₀ は，直積集合

P = {0, 1} × {0, 1} × {0, 1} × ⋯

の濃度と等しくなります．ℵ が実数集合の濃度と等しいので，|(0, 1]| = ℵ であることから

|P| = |(0, 1]|

を示せれば良いとなります．

P の元は 0と1 からなる数列として，(a₁, a₂, ⋯) と表せるので，これを2進小数で表現された実数と対応させることができます．つまり，

0.a₁a₂⋯

(0, 1] に属する実数を無限２進小数で表現すると，その表し方はただ１通りとなります．

次に，(0, 1] に属する実数について，有限2進小数に表せる集合 S を考えてみます．このとき，S ⊂ ℚ であることから

|S| = ℵ₀

次に，写像 φ : P → (0, 1] ⊔ S を考えてみます．x ∈ P について，

x = (a₁, ⋯, a_n, 0, 0, ⋯)

とあるところから先すべてが0になっているものについて，

φ(x) = 0.a₁a₂⋯a_n ∈ S

と対応させます．また，それ以外の場合は

φ(x) = 0.a₁a₂⋯a_n⋯ ∈ (0, 1]

となるので，x ∈ P ⇒ φ(x) ∈ ((0, 1] ⊔ S)，また φ は P から (0, 1] ⊔ S に対して１対１の対応を与えてます．つまり，

|P| = |(0, 1] ⊔ S|

また無限集合 Aと高々加算集合 B について定理 3 より

|A| = |A ⊔ B|

であることから

|P| = |(0, 1] ⊔ S| = |(0, 1]|

従って，

2^ℵ₀ = ℵ

べき集合

直積集合

集合 MN

M から N への写像全体の作る集合

無限集合と高々加算集合の直和

𝔅(ℕ) の濃度

集合 M^N