集合の濃度　(4)冪集合の濃度

$X\to\mathcal{P}(X)~;~x\mapsto\{x\}~$は単射である。
よって、$|X|\le|\mathcal{P}(X)|~$である。

$f:X\to\mathcal{P}(X)~$を任意の写像とする。
このとき、$D:=\{x\in X\mid x\notin f(x)\}~$を考える。
$f(a)=D~$となる$~a\in X~$があると仮定すると、 \begin{equation*} \begin{split} a\in f(a)&\Longleftrightarrow a\in D\\ &\Longleftrightarrow a\notin f(a) \end{split} \end{equation*} となるがこれは明らかに矛盾している。
よって、$f~$は全射ではない。
つまり、$|X|\neq|\mathcal{P}(X)|~$となる。

任意の$~A\subset X~$に対して$~A~$の特徴関数 $$ \chi_A:X\longrightarrow\{0,1\}~;~x\longmapsto\left\{ \begin{array}{ll} 1 & (x\in A)\\ 0 & (x\notin A) \end{array} \right. $$ を考え $$ \varphi:\mathcal{P}(X)\longrightarrow\{0,1\}^X~;~A\longmapsto\chi_A $$ で写像$~\varphi~$を定める。

任意に$~A,B\subset X~$をとり、$A\neq B~$とする。
このとき、ある$~x~$が$~x\in A\setminus B~$または$~x\in B\setminus A~$を満たす。 $x\in A\setminus B~$なら、$\chi_A(x)=1,\chi_B(x)=0~$である。
$x\in B\setminus A~$なら、$\chi_A(x)=0,\chi_B(x)=1~$である。
どちらの場合も、$\chi_A(x)\neq\chi_B(x)~$なので$~\chi_A\neq\chi_B~$である。
よって、$\varphi(A)\neq\varphi(B)~$となり$~\varphi~$は単射である。

$f:X\to\{0,1\}~$を任意の写像とする。
$A:=f^{-1}(\{1\})~$とすると、$A\in\mathcal{P}(X)~$であり、 \begin{align} &\chi_A(x)=1\Longleftrightarrow x\in A\Longleftrightarrow f(x)=1\\ &\chi_A(x)=0\Longleftrightarrow x\notin A\Longleftrightarrow f(x)=0 \end{align} となるので、$f=\chi_A=\varphi(A)~$である。
よって、$\varphi~$は全射である。

$[0,1)\sim\{0,1\}^{\mathbb{N}}~$であることを示す。
任意の$~x\in[0,1)~$に対して、${}^{\forall}n\in\mathbb{N},I_{n+1}(x)\subset I_n(x)~$となる半開区間$~I_n(x)=[a_n,b_n)~$を次で定める。
\begin{align} I_0(x)&:=[0,1)\\ I_{n+1}(x)&:=\left\{ \begin{array}{ll} \left[a_n,\cfrac{a_n+b_n}{2}\right) & \left(x\lt\cfrac{a_n+b_n}{2}\right)\\ \left[\cfrac{a_n+b_n}{2},b_n\right) & \left(x\ge\cfrac{a_n+b_n}{2}\right) \end{array} \right. \end{align} このとき、定め方から明らかに$~{}^{\forall}n\in\mathbb{N},x\in I_n(x)~$である。
この$~I_n(x)~$全体の集合を$~A_x~$とする。 つまり $$ A_x:=\{I_n(x)\mid n\in\mathbb{Z}_{\gt}\} $$ $\mathcal{A}:=\{A_x\mid x\in[0,1)\}~$とし、写像$~f:[0,1)\to\mathcal{A}~;~x\mapsto A_x~$を考える。
$x,y\in[0,1)~$をとり、$f(x)=f(y)~$とする。
このとき、任意の$~n\in\mathbb{N}~$について$~I_n(x)=I_n(y)=[a_n,b_n)~$となっている。
半開区間$~[a_n,b_n)~$の幅は$~\cfrac{1}{2^n}~$なので、$n\to\infty~$で0になる。
かつ、数列$~\{a_n\},\{b_n\}~$は単調列であるので、$\displaystyle\lim_{n\to\infty}a_n=\lim_{n\to\infty}b_n~$となる。
${}^{\forall}n\in\mathbb{N}~$について$~x,y\in[a_n,b_n)~$なので、 $a_n\le x,y\lt b_n~$であり$~\displaystyle\lim_{n\to\infty}a_n\le x,y\le\lim_{n\to\infty}b_n~$となる。
$\displaystyle\lim_{n\to\infty}a_n=\lim_{n\to\infty}b_n~$なので、$\displaystyle x=y=\lim_{n\to\infty}a_n=\lim_{n\to\infty}b_n~$となる。
よって、$f:[0,1)\to \mathcal{A}~$は単射である。
$f~$が全射であることは明らかなので、$f~$は全単射である。

ここで、写像$~g:\mathcal{A}\to\{0,1\}^{\mathbb{N}}~$を $$ g(A_x)(n):=\left\{ \begin{array}{ll} 1 & (\sup{I_{n+1}(x)}=\sup{I_n(x)})\\ 0 & (\inf{I_{n+1}(x)}=\inf{I_n(x)}) \end{array} \right. $$ となるように定義する。
任意に$~X,Y\in \mathcal{A}~$をとり、$X\neq Y~$とする。
$X,Y\in\mathcal{A}~$なので、$X=A_x,Y=A_y~$となる$~x,y\in[0,1)~$がある。
$A_x\neq A_y~$なので$~I_n(x)\neq I_n(y)~$となる$~n\in\mathbb{Z}_{\gt}~$がある。
そのような最小の$~n\in\mathbb{Z}_{\gt}~$を$~n_0~$とする。
$I_{n_0-1}(x)=I_{n_0-1}(y)~$なのでこれを$~I=[a,b)~$とする。
$I_{n_0}(x)=\left[a,\cfrac{a+b}{2}\right)~$なら$~I_{n_0}(y)=\left[\cfrac{a+b}{2},b\right)~$である。
$I_{n_0}(x)=\left[\cfrac{a+b}{2},b\right)~$なら$~I_{n_0}(y)=\left[a,\cfrac{a+b}{2}\right)~$である。
よって、$g(X)(n_0)\neq g(Y)(n_0)~$となるので$~g(X)\neq g(Y)~$である。
したがって、$g:A\to\{0,1\}^{\mathbb{N}}~$は単射である。

$\varphi:\mathbb{N}\to\{0,1\}~$を任意の写像とする。
${}^{\forall}n\in\mathbb{N},J_{n+1}\subset J_n~$となる半開区間$~J_n=[c_n,d_n)~$を次で定める。
$$ J_0:=[0,1)\\ J_{n+1}:=\left\{ \begin{array}{ll} \left[c_n,\cfrac{c_n+d_n}{2}\right) & (\varphi(n)=0)\\ \left[\cfrac{c_n+d_n}{2},d_n\right) & (\varphi(n)=1) \end{array} \right. $$ このとき、$A=\{J_n\mid n\in\mathbb{Z}_{\gt}\}~$とすると$~A\in\mathcal{A}~$であり、 $$ g(A)=\varphi $$ となる。 よって、$g~$は全単射である。

したがって、$g:\mathcal{A}\to\{0,1\}^{\mathbb{N}}~$は全単射となる。
これらより、$g\circ f:[0,1)\to\{0,1\}^{\mathbb{N}}~$は全単射であるので、$[0,1)\sim\{0,1\}^{\mathbb{N}}~$である。
$[0,1)\sim\mathbb{R}~$かつ$~\{0,1\}^{\mathbb{N}}\sim\mathcal{P}(\mathbb{N})~$なので$~\mathbb{R}\sim\mathcal{P}(\mathbb{N})~$である。