第１３回 濃度の大小
§１ 濃度の大小関係
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₁への全単射になる。
よって、
次に、
を全単射と仮定し、
とおく。
しかし、
Xの定義から
となり矛盾が生じる。
よって、Aから
ゆえに、
（証明終）