# 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$.

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.

• Instead of $\mathrm x$, you should use $\times$ to denote Cartesian product. – Abstract Analysis Jul 19 '19 at 0:40
• Are you aware (and allowed to use) that $|\Bbb{R}| = \left|2^{\Bbb{N}}\right|$? I often find working with subsets of $\Bbb{N}$/infinite binary sequences easier than working with $\Bbb{R}$ specifically. – Theo Bendit Jul 19 '19 at 0:46
• $|\mathbb{N} \times \mathbb{R}| = \max(|\mathbb{N}|, |\mathbb{R}|)=|\mathbb{R}|$, by standard cardinal arithmetic. – Henno Brandsma Jul 19 '19 at 4:26

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}$$.

• The sentence beginning "Therefore it suffices" isn't what you meant. – Andreas Blass Jul 19 '19 at 0:55
• @AndreasBlass Oh, it is a typo. Thanks – TheWildCat Jul 19 '19 at 1:00
• @CTW Hi, isn't your injection in your proof has already shown a bijection? Since $(n,x) \to n+x$ is a bijection. And $x$ in $(0,1)$ has bijection with $\Bbb R$ – WaterBro Jul 19 '19 at 1:04
• @WaterBro No, the numbers $n\in\mathbb{Z}$ are not included. – TheWildCat Jul 19 '19 at 1:05
• @CTW Oh I see, once we have shown the injection in your answer, then they have same cadinality since $\Bbb R$ is a subset of $\Bbb N \times \Bbb R$ – WaterBro Jul 19 '19 at 4:48

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.