Prove that $|\mathbb{N}\times \mathbb{R}| = |\mathbb{R}|$

Question

I'm trying to prove the equality between the cardinalities: $|\mathbb{N}\times \mathbb{R}| = |\mathbb{R}|$ ($\mathbb{N}\times \mathbb{R}$ is cartesian product from $\mathbb{N}$ to $\mathbb{R}$).

I tried doing that by building injective functions first from $\mathbb{N}\times \mathbb{R}$ to $(0,1)$ and then from $(0,1)$ to $\mathbb{N}\times \mathbb{R}$ so:

$F: \mathbb{N}\times \mathbb{R} \rightarrow (0,1)$ is given by : $$F(1 , 0 .abcd....) \mapsto 0.abcd..$$ $$F(2 , 0.abcde....) \mapsto 0.abcde..$$ for example ($0.abcd..$ represents a real number in $(0,1)$

I'm not sure if that's right..

Answer 1

(I will assume $\Bbb{N}$ starts at $1$). Use the fact that $|\Bbb{R}| = \mathcal{P}(\Bbb{N})$; it suffices to show that $|\mathcal{P}(\Bbb{N})| = |\Bbb{N} \times \mathcal{P}(\Bbb{N})|$.

Clearly, $$|\Bbb{N} \times \mathcal{P}(\Bbb{N})| \ge |\{1\} \times \mathcal{P}(\Bbb{N})| = |\mathcal{P}(\Bbb{N})|,$$ so it suffices to find a surjection from $\mathcal{P}(\Bbb{N})$ onto $\Bbb{N} \times \mathcal{P}(\Bbb{N})$.

Define such a function as follows. Suppose $S \subseteq \Bbb{N}$. If $S = \emptyset$, map it to $(1, \emptyset)$. Otherwise, $S$ has a minimum element. Map $S$ to $(\min S, (S \setminus \{\min S\}) - \min S)$.

We now show that this map is surjective. If we have a pair $(n, T) \in \Bbb{N} \times \mathcal{P}(\Bbb{N})$, then let $S = \{n\} \cup (T + n)$. Since every $t \in T$ is at least $1$, we have that $n$ is the minimum element of $S$, and clearly the surjection will map $S$ to $T$.

(It's worth pointing out that the map is a bijection too, if you restrict it to $\mathcal{P}(\Bbb{N}) \setminus \{ \emptyset \}$.)

Answer 2

To begin with, try solving something simpler: find an injective function $f:\mathbb R\to\mathbb (0,1)$ (this is not trivial, but is commonly known; see, e.g., This MSE thread, or using some manipulation of the $\arctan$ function).

Once you have this, you can `cook up' a new function $F:\mathbb N\times\mathbb R\to \mathbb R$ by setting $$F(n,x)=f(x)+n\text{ for any }n\in\mathbb N\text{ and }x\in \mathbb R.$$ It should be a simple check that the new function $F$ is injective.