第１３回 濃度の大小

第１３回　濃度の大小

§１　濃度の大小関係

A、Bを有限集合とする。Aの濃度がBより小さいことは、Bの中にAと対等な真部分集合があることに他ならない。

すなわち、

であるB₁が存在するとき、

が成立する。

しかし、無限集合のとき、

は一般に成立しない。

たとえば、Aを自然数全体の集合、Bを偶数全体の集合とするとき、BはAの真部分集合でB〜Bが成立するが、A〜Bで、A、Bの濃度はともに可算濃度であって、

は成り立たないからである。

このように矛盾した事態が発生しないように、濃度の大小関係を次のように定義する。

濃度の大小の定義

集合A、Bについて

であるB₁があるならば、｜A｜は｜B｜よりも大きくない、あるいは、｜B｜は｜A｜より小さくないといい、

と記される。

さらに、｜A｜≦｜B｜かつ｜A｜≠｜B｜のとき、｜A｜は｜B｜より小さい、あるいは、｜B｜は｜A｜より大きいといい、

と書く。

なお、（２）と「AからBへの単射が存在する」と同じことなので、これを濃度の大小の定義としてもよい。

選択公理を認めると、

BからAの全射が存在するとき

である、ことが証明できる。

例　自然数全体の集合Nは、実数全体の集合Rの部分集合であり、かつ、NとRは対等でないので、である。したがって、

また、実数全体の集合RからRへの関数全体の集合Fとすると、Fの中にRと対等な部分集合があり、かつ、RとFは対等でないので、関数の濃度をfで表すと、

である。

定理１　｜A｜≦｜B｜、｜B｜≦｜C｜ならば｜A｜≦｜C｜である。

【証明】

｜A｜≦｜B｜、｜B｜≦｜C｜だから

であるB₁、C₁がある。

BからC₁への全単射をf、B₁のfによる像をf(B₁)とすると、

よって、

ゆえに、

（証明終）

定理２　（ベルンシュタインの定理）

ベルンシュタインの定理の証明は大変なので、ここでは定理だけを紹介する。

以上のことをまとめると、次のようになる。

§２　冪集合の濃度（カントールの定理）

集合Aの部分集合の全体からなる集合をAの冪集合（べきしゅうごう）といい、記号

で表す。

例　A=｛1, 2, 3｝とすると、Aの部分集合は

の８個で、Aの冪集合は

である。

有限集合Aの要素の数がn、すなわち、Aの濃度｜A｜=nであるとき、の要素の数はで、その濃度はである。

したがって、有限集合Aの場合、次の関係が成立する。

【証明】

n=0あるいはn=1ならば、0<1=2⁰、1<2=2¹だから、

n=kのとき

が成り立つと仮定する。

n=k+1のとき

数学的帰納法により、

ゆえに、

（証明終）

Aが有限集合のとき、Aの濃度はAの冪集合の濃度より小さい。

Aが無限集合の場合も、が成り立つというのが、次のカントールの定理である。

定理３　（カントールの定理）

任意の集合Aに対して

【証明】

Aの部分集合のうちで、要素を一つしか含まない集合全体をA₁とすれば、

である。

Aの任意の要素aに｛a｝∈A₁を対応させれば、これはAからA₁への全単射になる。

よって、

次に、であることを示す。

を全単射と仮定し、

とおく。

であるから、f(a)=Xとなるa∈Aが存在する。

しかし、

Xの定義から

となり矛盾が生じる。

よって、Aからの全単射は存在しない。

ゆえに、

（証明終）