Exercise 1563Logic, sets and proofs › Countability and cardinalityL1Added 3 Nov 2026

$|\mathcal{P}(\mathbb{N})|=|\mathbb{R}|$

#power set#reals#cardinality

Statement

Show that $\mathcal{P}(\mathbb{N})$ and $\mathbb{R}$ have the same cardinality.

Hint

Binary expansions give a bijection between subsets of $\mathbb{N}$ and reals in $[0,1]$ .

Show solutionHide solution

Solution

Injection $\mathcal{P}(\mathbb{N})\to\mathbb{R}$ . $S\mapsto\sum_{n\in S}2^{-n}$ (binary expansion). Injective (up to the standard ambiguity $0.0\overline{1}=0.1$ ).

Injection $\mathbb{R}\to\mathcal{P}(\mathbb{N})$ .
$\mathbb{R}\hookrightarrow\mathcal{P}(\mathbb{Q})\cong\mathcal{P}(\mathbb{N})$ via Dedekind cuts.

Cantor–Bernstein. Both injections give a bijection.

Conclusion. $|\mathcal{P}(\mathbb{N})|=|\mathbb{R}|=2^{\aleph_0}$ .

$|\mathcal{P}(\mathbb{N})|=|\mathbb{R}|$

Statement

Solution

More problems in Countability and cardinality