鈴木『ろんりの相談室』例題13.2.2

鈴木登志雄『ろんりの相談室』例題13.2.2。

【問題】$\mathbb{N}$（自然数全体）の部分集合$X$を\[\mathbb{N}\ni n\mapsto \left\{\begin{array}{c} 1\quad(n\in X)\\0\quad(n\notin X)\end{array}\right.\in\{0,1\}\]なる数列にうつす写像$f:2^\mathbb{N}\to{\rm Map}(\mathbb{N},\{0,1\})$が全単射であることを示せ。

【解答】$X\subseteq\mathbb{N}$に対して、数列$f(X)$の第$n$項を$f(X)_n$と表す。

単射性：$f(X)=f(Y)$なる$X,Y\subseteq\mathbb{N}$を任意にとると、$n\in X\Leftrightarrow f(X)_n=1\Leftrightarrow f(Y)_n=1\Leftrightarrow n\in Y$であるから$X=Y$である。

全射性：任意の数列$a:\mathbb{N}\to\{0,1\}$をとり、$X=\{n\in\mathbb{N}\mid a_n=1\}$と定める。すると$f(X)_n=1\Leftrightarrow n\in X\Leftrightarrow a_n=1$であるから$f(X)=a$である。