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

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

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