実数全体の集合と自然数全体の冪集合の対等性

数学

長らく放置していたブログの再開と同時に，これまた長らく放置していたやりかけの集合・位相演習をちょこっとやっていきます．

問題

\left| \mathbb{R} \right| = 2^{\aleph_0} を証明する．

証明

まず \left| \mathbb{R} \right| \geq 2^{\aleph_0} を示し，次に \left| \mathbb{R} \right| \leq 2^{\aleph_0} を示す．

前半

証明の前半では \left| \mathbb{R} \right| \geq 2^{\aleph_0} を示す． それには写像 F:2^{\mathbb{N}} \rightarrow \mathbb{R} を

\displaystyle F(f) = \sum_{n = 1}^\infty \frac{f(n)}{3^n}

によって定め，この F が単射であることを証明する．

f, g \in 2^{\mathbb{N}} とし， F(f) = F(g) とすると

\displaystyle F(f) - F(g) = \sum_{n = 1}^\infty \frac{f(n)}{3^n} - \sum_{n = 1}^\infty \frac{g(n)}{3^n} = \sum_{n = 1}^\infty \frac{f(n) - g(n)}{3^n} = 0

となる．

ここでもし f \neq g だったと仮定すると， f(n) \neq g(n) となるような n のうちに最小のものが存在する． それを m とすると，

\displaystyle F(f) - F(g) = \frac{f(m) - g(m)}{3^m} + \sum_{n = m + 1}^\infty \frac{f(n) - g(n)}{3^n}

である．ここで，

\displaystyle \frac{f(m) - g(m)}{3^m} = \pm \frac{1}{3^m}

であり，

\displaystyle - \frac{1}{2 \cdot 3^m} = \sum_{n = m + 1}^\infty \frac{-1}{3^n} \leq \sum_{n = m + 1}^\infty \frac{f(n) - g(n)}{3^n} \leq \sum_{n = m + 1}^\infty \frac{1}{3^n} = \frac{1}{2 \cdot 3^m}

であるから

\displaystyle \left| F(f) - F(g) \right| \geq \frac{1}{2 \cdot 3^m}

となって F(f) - F(g) = 0 と矛盾する． ゆえに f = g となる．

これで F(f) = F(g) ならば f = g であることが示された． よって F は単射である．

後半

証明の後半では \left| \mathbb{R} \right| \leq 2^{\aleph_0} を示す． それには写像 G:\mathbb{R} \rightarrow \mathfrak{P}(\mathbb{Q}) を

\displaystyle G(x) = \left\{ r \in \mathbb{Q} \mathrel{}\middle|\mathrel{} r < x \right\}

によって定め，この G が単射であることを証明する．

x, y \in \mathbb{R} とし， x \neq y とすると x \lt y または y \lt x である． どちらでも同様であるから x \lt y とすると，有理数の稠密性より x \lt q \lt yとなるような有理数 q が存在する． このとき q \not\in G(x) であり， q \in G(y) であるから G(x) \neq G(y) である． よって G は単射である．

証明の完成

\left| \mathbb{R} \right| \geq 2^{\aleph_0} かつ \left| \mathbb{R} \right| \leq 2^{\aleph_0} であるから，Cantor-Bernsteinの定理より \left\{ 0, 1 \right\}^\mathbb{N} \sim \mathbb{R} であり， \left| \mathbb{R} \right| = 2^{\aleph_0} である．