ある集合の濃度と、その集合の冪集合の濃度は等しいかどうか

定理

任意の集合Aに対して、Aの冪集合は、A自身よりも真に大きい濃度を持つ

有限集合について

有限集合に対しては成り立つのは明らか

なぜなら冪集合濃度は2^{|A|}だから。

無限集合について

方針

写像A\to\mathscr{P}(A)を考える

これを満たすようなどんな写像fを選んでも全射になりえないことを示せばいい

全射であるならば濃度が|A|\ge|\mathscr{P}(A)|だということになる

全射fを仮定して、その像に入らないようなAの部分集合(B)の存在を示せばいい

証明

f:A\to\mathscr{P}(A):a\mapsto \{a\}とすると、これは単射になる

故に|A|\le|\mathscr{P}(A)|である

あとは|A|\ne|\mathscr{P}(A)|となること、つまりA,\mathscr{P}(A)の間に全射が存在しないことを示せばいい

全射f:A\to \mathscr{P}(A)があると仮定する

ここで以下のような集合Bを定義する

B:=\{x\in A|x\not\in f(x)\}

定義からしてB\sub A。故にB\sub\mathscr{P}(A)でもある

この時、fは全単射なので、あるb\in Aが存在して、f(b)=Bとなるはずである

b\in Bとすると、Bの定義よりb\not\in f(b)だが、f(b)=Bなのでb\not\in Bとなり矛盾

b\not\in Bのとき、Bの定義よりb\in f(b)だが、f(b)=Bなのでb\in Bとなり矛盾

関連

参考

これ読めば十分

対角線論法の示し方も簡潔

なんか異常にわかりにくいな

日本語が冗長すぎるからかな