Introduction
ここでは,部分集合やべき集合といった概念について説明する。
部分集合とべき集合
集合の元がすべて集合にも含まれるとき,はの部分集合(subset)と言いで表す。
空集合や自身もまたの部分集合とみなされる。
すると,例えば集合の部分集合は
となる。
また,集合の8つの部分集合全体から成る集合
\begin{align}
\{ \emptyset, \{a \}, \{b\}, \{c\}, \{a,b\}, \{a,c\}, \{b,c\}, \{a,b,c\} \}
\end{align}
をと表し,のべき集合(power set)と呼ぶ。
部分集合の個数とべき集合の濃度
一般に,個の要素を持つ有限集合の部分集合の個数は,となる。
このことは以下のようにして示すことができる。
まず,引き続きの例で考えよう。
の各要素がある集合の要素であれば,そうでなければを返す関数を考える。
集合から部分集合を構成するというのは,から特定の要素を選び出して,それ以外を捨てる操作に対応する。
そして,要素を選択することを,捨てることをと対応付けることができる。
つまり,()においては
\begin{equation}
\begin{split}
\emptyset & \leftrightarrow f(a)=0, \ f(b)=0, \ f(c)=0
\
\{ a \} & \leftrightarrow f(a)=1, \ f(b)=0, \ f(c)=0
\
\{a,b \}& \leftrightarrow f(a)=1, \ f(b)=1, \ f(c)=0
\
...
\end{split}
\end{equation}
といった具合である。
対応付けの数は,各要素ごとにかの通りずつあるため,となる。
これを個の要素を持つ集合のケースに一般化できることは明らかだろう。
よってまた,べき集合(power set)の濃度についての公式
が得られる。
自然数のべき集合の濃度
自然数の集合についても式()を適用することができ
となる。
また,この濃度は,連続体の濃度と等しい。
すなわち
である。
このことは以下のように示される。
区間の実数の集合を考える。
2進数で表せば,に含まれる任意の実数は,小数点以下のとの羅列で表現することができる。
そこで,例えば
なような要素を取り出したとき,小数点以下1桁目を番目とし,が現れる桁の番数を自然数に対応させることで
\begin{equation}
\begin{split}
\{ 0, 2, 5,...\}
\
\{ 1,5,...\}
\
\{3,4,6,7,... \}
\end{split}
\end{equation}
という集合を作ることができる。
これらはみな,自然数の集合の部分集合であり,すなわち自然数のべき集合の要素となっている。
このようにして,の任意の要素に,自然数のべき集合の要素を1対1に対応付けられる。
『連続体の濃度:対角線論法と連続体仮説』での議論より,の濃度も連続体の濃度を持つため,これより自然数のべき集合の濃度は,実数の濃度と等しいことがいえる。