📂Set Theory

Comparison of the Cardinality of Real Numbers and the Cardinality of Rational Numbers

Theorem ¹

Regarding $\operatorname{card}(\mathbb{Q})={{ \aleph }_{ 0 }}, \operatorname{card}(\mathbb{R})=c$, $$ { 2 }^{ {{ \aleph }_{ 0 }} } =c \\ {{ \aleph }_{ 0 }}<c $$

Explanation

As you might guess from seeing Cantor’s diagonal argument, the set of real numbers has far more elements than the set of rational numbers. The cardinality of these can be explicitly shown by establishing an inequality.

Proof

Part 1. $c \le 2^{\aleph_{0}}$

Let’s define the function $f : \mathbb{R} \to \wp (\mathbb{Q})$ as $f(a):={x\in \mathbb{Q}|x<a, a\in \mathbb{R}}$. Due to the density of real numbers, for two real numbers $a<b$, there exists a rational number $r$ satisfying $a<r<b$. Since $r<b$ holds, $r\in f(b)$ but since $a<r$, therefore $r\notin f(a)$, that is, $f(a)\neq f(b)$. Therefore, $f$ is injective, and by the lemma, $$ \operatorname{card}(\mathbb{R})\le \operatorname{card}(\wp (\mathbb{Q})) $$ Since $\operatorname{card}(\wp (\mathbb{Q}))= { 2 }^{ \operatorname{card}(\mathbb{Q}) }= { 2 }^{ {{ \aleph }_{ 0 }} }$, $$ c=\operatorname{card}(\mathbb{R})\le \operatorname{card}(\wp (\mathbb{Q}))= { 2 }^{ {{ \aleph }_{ 0 }} } $$

---

Part 2. $ 2^{\aleph_{0}} \le c$

Let’s define the function $g : { {0,1} }^{ N } \to \mathbb{R}$ as $g(a):=0. { a }_{ 1 } { a } _{ 2 } { a }_{ 3 }\cdots$, ($a$ is an element of ${ {0,1} }^{ N }$). The function value of $g$ can be represented in decimal notation composed of $0$ and $1$.

For two elements $a,b$ of ${ {0,1} }^{ N }$, if $a\neq b$ then $g(a)\neq g(b)$, so $g$ is injective, $$ \operatorname{card}\left( { {0,1} }^{ N } \right) \le \operatorname{card}(\mathbb{R}) $$ Since $\operatorname{card}\left( { {0,1} }^{ N } \right) = { 2 }^{ \operatorname{card}(N) }= { 2 }^{ {{ \aleph }_{ 0 }} }$, $$ { 2 }^{ {{ \aleph }_{ 0 }} } =\operatorname{card}\left( { {0,1} }^{ N } \right) \le \operatorname{card}(\mathbb{R})=c $$

---

Part 3. $\aleph_{0} < 2^{\aleph_{0}}$

Since ${ 2 }^{ {{ \aleph }_{ 0 }} } \ge c$ and ${ 2 }^{ {{ \aleph }_{ 0 }} } \le c$, $$ { 2 }^{ {{ \aleph }_{ 0 }} } =c $$

Cantor’s theorem: For any set $X$ and its power set $\wp (X)$, $\operatorname{card}(X)<\operatorname{card}(\wp (X))$ holds

By Cantor’s theorem, ${{ \aleph }_{ 0 }}< { 2 }^{ {{ \aleph }_{ 0 }} }$ holds, thus ${{ \aleph }_{ 0 }}<c$, and $$ \aleph_{0} < 2^{\aleph_{0}} $$

■