べき集合の濃度

命題
集合Xとそのべき集合2^{X}=\{ A \mid A \subset X \}の濃度について次の不等式が成り立つ.
  {\rm card} X < {\rm card} 2^{X}.□

(証明)
単射X \ni x |\to \{ x \} \in 2^{X}により,{\rm card} X \leq {\rm card} 2^{X}である.
背理法{\rm card} X = {\rm card} 2^{X}と仮定すると,全単射写像f:X \to 2^{X}が存在する.
集合A:=\{ x \in X \mid x \not{\in} f(x) \} \in 2^{X}を考える.
写像f全単射であるから,あるy \in Xが一意的に存在してf(y)=Aが成立する.
このときy \in Aまたはy \not{\in} Aのいずれかが成立する.
y \in Aならば集合Aの作り方からy \not{\in} f(y) = Aで矛盾する.
y \not{\in} Aならば同様にしてy \in f(y) = Aで矛盾する.
いずれにしても矛盾する.したがって,{\rm card} X < {\rm card} 2^{X}が示された.(証明終)

一行目の単射写像の矢印は要素から要素への写像を表す\mapstoを使ったのだが表示されず.
というわけでちょっとごまして記述してある.

広告を非表示にする