Prove that for any set A, if $\vert \Bbb N \times \Bbb R \vert \geqslant \vert A \vert$, then $\vert \Bbb R \vert \geqslant \vert A \vert$.

Question

Prove that for any set A, if $\vert \Bbb N \times \Bbb R \vert \geqslant \vert A \vert$, then $\vert \Bbb R \vert \geqslant \vert A \vert$.

I am considering proving $\vert \Bbb N \times \Bbb R \vert =\vert \Bbb R \vert$, but cannot generate a function $f: \Bbb N \times \Bbb R \to \Bbb R$ bijective.

Answer 1

Although it is not easy to generate the bijective function $f\colon\mathbb{N}\times\mathbb{R}\to\mathbb{R} $, we can instead use Cantor-Bernstein theorem which states that, if there are injections $\mathbb{N}\times\mathbb{R}\to\mathbb{R} $ and $\mathbb{R}\to\mathbb{N}\times\mathbb{R} $, then they have the same cardinal number. Therefore it suffices for us to construct an injection $\mathbb{R}\times\mathbb{N}\to\mathbb{R} $. This is constructed as follows: we know that there is a natural bijection $\mathbb{R}\leftrightarrow (0,1)$ via the function $\arctan $, and since we have an injection $\mathbb{N}\times (0,1)\to\mathbb{R} $ given by $(n,x)\mapsto n+x$, the composition $\mathbb{N}\times\mathbb{R}\to\mathbb{N}\times (0,1)\to\mathbb{R} $ gives the injection of $\mathbb{N}\times\mathbb{R} $ into $\mathbb{R} $.

Answer 2

You want to prove that, for any set $A$, if $|\mathbb N\times\mathbb R|\ge|A|$, then $|\mathbb R|\ge|A|$.

No bijections are needed. You just have to show that $|\mathbb R|\ge|\mathbb N\times\mathbb R|$; then you will have $|\mathbb R|\ge|\mathbb N\times\mathbb R|\ge|A|$.

In order to show that $|\mathbb R|\ge|\mathbb N\times\mathbb R|$, you need an injection $f:\mathbb N\times\mathbb R\to\mathbb R$. Here is an easy one: $$f(n,x)=n+\frac1{1+e^x}$$
By the way, it can also be shown that $|\mathbb R\times\mathbb R|\le|\mathbb R|$, but that is more difficult and is not needed here. Of course, using the Cantor-Bernstein theorem, from these inequalities you can get the equalities $|\mathbb R|=|\mathbb N\times\mathbb R|=|\mathbb R\times\mathbb R|$.

Since you asked, here's how you can construct an explicit bijection between $\mathbb N\times\mathbb R$ and $\mathbb R$. You can do that by composing a series of bijections like this: $$\mathbb N\times\mathbb R\to\mathbb N\times(\mathbb Z\times[0,1))\to(\mathbb N\times\mathbb Z)\times[0,1)\to\mathbb Z\times[0,1)\to\mathbb R.$$ The nontrivial steps are constructing a bijection $\mathbb R\to\mathbb Z\times[0,1)$ and a bijection $\mathbb N\times\mathbb Z\to\mathbb Z$.
A bijection $\mathbb R\to\mathbb Z\times[0,1)$ is easy: $x\mapsto(\lfloor x\rfloor,\ x-\lfloor x\rfloor)$. A bijection $\mathbb N\times\mathbb Z\to\mathbb Z$ can obviously be constructed, but I don't know of an elegant way to define one explicitly, so I leave that part as an exercise.