カントールの定理

Cantor's theorem

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

定理

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

有限集合について

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

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

無限集合について

方針

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

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

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

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

https://gyazo.com/5dd8940f7573e00ad03de77d47e74ba3

証明

$ 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)でもあるmrsekut.icon

この時、$ 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となり矛盾