集合論 2020-12-25

部分集合とべき集合

ScienceTime Team
274 views
部分集合とべき集合

Introduction

ここでは,部分集合やべき集合といった概念について説明する。

部分集合とべき集合

集合Bの元がすべて集合Aにも含まれるとき,BA部分集合(subset)と言いBAで表す。 空集合やA自身もまたAの部分集合とみなされる。 すると,例えば集合A={a,b,c}の部分集合は

(1),{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}

となる。

また,集合Aの8つの部分集合全体から成る集合

\begin{align}

\{ \emptyset, \{a \}, \{b\}, \{c\}, \{a,b\}, \{a,c\}, \{b,c\}, \{a,b,c\} \} \end{align}

B(A)と表し,Aべき集合(power set)と呼ぶ。

部分集合の個数とべき集合の濃度

一般に,m個の要素を持つ有限集合Aの部分集合の個数は,2mとなる。 このことは以下のようにして示すことができる。 まず,引き続きA={a,b,c}の例で考えよう。 xAの各要素がある集合Sの要素であれば1,そうでなければ0を返す関数f(x)を考える。 集合Aから部分集合を構成するというのは,Aから特定の要素を選び出して,それ以外を捨てる操作に対応する。 そして,要素を選択することをf(x)=1,捨てることをf(x)=0と対応付けることができる。 つまり,(1)においては

\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}

といった具合である。 対応付けの数は,各要素ごとに012通りずつあるため,2×2×2=23となる。 これをm個の要素を持つ集合のケースに一般化できることは明らかだろう。 よってまた,べき集合(power set)B(A)の濃度についての公式

(2)|B(A)|=2|A|

が得られる。


自然数のべき集合の濃度

自然数の集合Nについても式(2)を適用することができ

(3)|B(N)|=2|N|=20

となる。 また,この濃度は,連続体の濃度と等しい。 すなわち

(4)20=

である。 このことは以下のように示される。

区間[0,1)の実数の集合を考える。 2進数で表せば,[0,1)に含まれる任意の実数は,小数点以下の01の羅列で表現することができる。 そこで,例えば

(5)0.10100100...0.01000100...0.00011011...

なような要素を取り出したとき,小数点以下1桁目を0番目とし,1が現れる桁の番数を自然数に対応させることで

\begin{equation} \begin{split}

\{ 0, 2, 5,...\} \

\{ 1,5,...\} \

\{3,4,6,7,... \} \end{split} \end{equation}

という集合を作ることができる。 これらはみな,自然数の集合の部分集合であり,すなわち自然数のべき集合の要素となっている。 このようにして,[0,1)の任意の要素に,自然数のべき集合の要素を1対1に対応付けられる。 『連続体の濃度:対角線論法と連続体仮説』での議論より,[0,1)の濃度も連続体の濃度を持つため,これより自然数のべき集合の濃度は,実数の濃度と等しいことがいえる。


References

  • 松村 英之. (2005). 集合論入門(復刊版). 朝倉書店.
  • 志賀 浩二. (1988). 集合への30講. 朝倉書店.
  • 内田 伏一. (2020). 集合と位相(増補新装版). 裳華房.