$A$ を集合とし, $\mathfrak{P}(A)$ を $A$ の冪集合とする. このとき, $A$ から $\mathfrak{P}(A)$ への全射は存在しないことを証明せよ.
解答例 1
全射 $f:A\rightarrow\mathfrak{P}(A)$ が存在すると仮定する. $$ X = \{ x\in A \mid x\not\in f(x) \} $$ とおくと, $X\in\mathfrak{P}(A)$ である. $f$ は全射だから, ある $a\in A$ が存在して, $f(a)=X$ となる.
$a\in X$ と仮定すると, $X$ の定め方から $$ a\not\in f(a) = X $$ となって矛盾が生じる.
$a\not\in X$ と仮定すると, $X$ の定め方から $$ a\in f(a) = X $$ となり, いずれにせよ矛盾が生じる.
最終更新日：2011年11月02日