$A$ を集合, $\mathfrak{P}(A)$ を $A$ の冪集合, $\mathrm{Map}(A, \{0, 1\})$ を $A$ から $2$ 元集合 $\{0, 1\}$ への写像の全体とする. このとき, $\mathfrak{P}(A)$ は $\mathrm{Map}(A, \{0, 1\})$ と対等であることを証明せよ.
解答例 1
写像 $\Phi:\mathfrak{P}(A)\rightarrow\mathrm{Map}(A, \{0, 1\})$ を, 各 $B\in\mathfrak{P}(A)$ に対し, $\Phi(B)=\chi_B$ とおくことによって定める. ただし, $$ \chi_B:A\longrightarrow\{0, 1\},\quad x\longmapsto\begin{cases} 1, & x\in B \\ 0, & x\in A\setminus B \end{cases} $$ は $A$ における $B$ の定義関数である. 任意の $B$, $B'\in\mathfrak{P}(A)$ に対して, $\Phi(B)=\Phi(B')$ ならば $$ B = \{ x\in A \mid \chi_{B}(x)=1 \} = \{ x\in A \mid \chi_{B'}(x)=1 \} = B'. $$ ゆえに, $\Phi$ は単射である. また, 任意の $f\in\mathrm{Map}(A, \{0, 1\})$ に対して, $$ C = \{ x\in A \mid f(x) = 1 \} $$ とおくと, $f=\chi_C=\Phi(C)$ となる. ゆえに, $\Phi$ は全射である. したがって, $\Phi$ は全単射である.
最終更新日：2011年11月02日