「冪集合」の版間の差分
削除された内容 追加された内容
62行目:
冪集合の濃度は元の集合の濃度より常に大きい。有限集合のときにはこれは当たり前である。一般の場合は、[[カントールの対角線論法]]によって示される。
===冪集合の濃度の大きさ===
上にも述べたが， 全体集合 <math>X</math> に対して， <math>S \subset X</math> を集合とする時， <math>\mathcal{P}(S)</math> の濃度は <math>S</math> より真に大きい．このことは次を示すことで保証される：
（１）[[単射]] <math>f : S \to \mathcal{P}(S)</math> が存在する．
（２）[[全射]] <math>f : S \to \mathcal{P}(S)</math> は存在しない．
（１）の証明： <math>S</math> が空の時は， <math>f : S \to \mathcal{P}(S)</math> は単射である（単射の定義から分かる）． <math>S</math> が空でないとする．このとき， <math>a \in S</math> をとることができる．この <math>a</math> に対して， <math>f(a):=\{a\} \in \mathcal{P}(S)</math> と決めれば， <math>f</math> は単射である．これで（１）が示せた．
（２）の証明：<math>A:=\{x \in S\ ;\ x \notin f(x)\}</math> とおく．このとき， <math>A</math> の定義より <math>x \in A \iff x \notin f(x)</math> である．よって， <math>\mathcal{P}(S) \ni A \neq f(x) \in f[S]:=\{f(s)\ ;\ s \in S\}</math> となるので， <math>f[S] \neq \mathcal{P}(S)</math> である．これは <math>f</math> が全射でないことを意味する．
==関連項目==
| |||