無限集合とその真部分集合の濃度

$X$ を任意の無限集合とする。
このとき、$X$ は加算無限部分集合 $A=\{x_n|n\in \mathbb{N}\}$ を含む(実際にこの事実を証明するには、選択公理を用いる必要がある)ので
$$\begin{array}{rl}X& =(X\mathrm{\setminus }A)\cup A\end{array}$$
となる。
ここで
$$\begin{array}{rl}Y& =(X\mathrm{\setminus }A)\cup \{x_{2n}|n\in \mathbb{N}\}\end{array}$$
とおくと、$Y$ は $X$ の真部分集合となる。

さらに、写像 $f:X\to Y$ を
$$\begin{array}{rl}f(x)& =x(x\in X\mathrm{\setminus } A)\\ f(x)& =x_{2n}(\mathrm{\exists }n\in \mathbb{N},x=x_n)\end{array}$$
と定めれば、$f$ は全単射となる。従って $X\sim Y$ となり、題意が示された。