Easy proof that $\mathfrak c=\lvert P(\mathbb Z)\rvert$...

Question

What is a nice way to prove that the cardinality of $\mathbb R$ is equal to that of the power set, $P(\mathbb Z)$, of the integers...

This is something I figured out while an undergraduate at Berkeley. I remember Spanier taught it to us in his course Intro to the theory of functions and point set topology.

My favorite part is that there's a natural way to associate a binary number with a subset of the integers, and vice-versa. The only technicality being that some numbers have two binary representations. Luckily those are all rational, so there are only countably many.

Of course, by Cantor's diagonalization argument, we know $|P(\Bbb Z)|\gt \aleph_0$. It is not that much of a stretch, the continuum hypothesis notwithstanding, that it would be $\mathfrak c$. See my answer for a little rigor.

Answer 1

$Y^X$ is typically used to denote the space of all functions $f:X\rightarrow Y$. Consider $2^X$, the space of all functions f from $X$ to a two element set, $f:X\rightarrow \{0,1\}$.

Evidently this is just the power set of $X$, $P(X)$... (for $x\in X$ let $x\in S $ if $f(x)=1$, and $x\notin S$ if $f(x)=0$).

We will need that the positive reals have the same cardinality as the reals: $\lvert \mathbb R^+\rvert=\lvert \mathbb R\rvert$

Next note that every $r\in \mathbb R^+$ can be expressed in binary.

This gives a function into $2^{\mathbb Z}$ in that the $n$-th place will have a $1$ or a $0$... This correspondence is $1-1$...

Thus $\lvert \mathbb R\rvert \le \lvert 2^{\mathbb Z}\rvert $.

Now the reverse inequality...

Note that $\lvert \mathbb N\rvert=\lvert \mathbb Z\rvert$.

So we can restrict our attention to binary numbers* between $0$ and $1$... This gives us a $1-1$ mapping from ${2^{\mathbb N}}'\to [0,1]\subset \mathbb R$...

*Note: we exclude duplicate binary representations; namely those ending in all $1$ 's... these are all rational, so constitute a countable set... taking out the elements of $2^{\mathbb N}$ corresponding to these binary representations results in a set, ${2^{\mathbb N}}'$, with the same cardinality...

Answer 2

Given a real number, $\alpha,$ take the set of all integers:

$$I_\alpha=\left\{2^{n+1}\lfloor n\alpha\rfloor +2^n \mid n\in\mathbb N\right\}$$

Show the function $\mathbb R\to\mathbb P(\mathbb Z)$ defined as $\alpha\mapsto I_\alpha$ is one-to-one. This is because every non-zero integer can be written uniquely in the form $2^{n+1}k+2^n$, so $I_{\alpha}$ encodes the pairs $(n,\lfloor n\alpha\rfloor)$, and $\lim_{n\to\infty} \frac{\lfloor n\alpha\rfloor}{n}=\alpha$, so if $I_\alpha=I_\beta$, then $\alpha=\beta.$

The reverse direction: Given $I\subseteq \mathbb N$, define:

$$\alpha_{I}=\sum_{n\in I} 10^{-n}$$

Prove that $I\mapsto \alpha_I$ is a one-to-one function $P(\mathbb N)\to\mathbb R.$

Then use a simple argument to prove that $|P(\mathbb N)|=|P(\mathbb Z)|.$

Answer 3

Here is a way to show an equivalent, but different statement. SHow that the power of positive integers has the same cardinality as the set of real numbers in the interval $[0,1]$.

Represent each real number in this interval in base 2: a typical element will look something like $0.100100011011101\ldots$ Consider the set of position numbers after the decimal point for every 1 in the above expansion. For the above example it goes like $\{1,4,8,9,11,12,13,15,\ldots\}$. Clearly given a subset of positive integers one can consider the corresponding infinite binary string having 1's at the appropriate slots as specified by this subset.

Of course there are minor issues coming from the fact that the expansion for a number is not unique. But this should not be a problem with some modification