2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Instead of $\mathrm x$, you should use $\times$ to denote Cartesian product. $\endgroup$ – Abstract Analysis Jul 19 '19 at 0:40
  • 1
    $\begingroup$ 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. $\endgroup$ – Theo Bendit Jul 19 '19 at 0:46
  • $\begingroup$ $|\mathbb{N} \times \mathbb{R}| = \max(|\mathbb{N}|, |\mathbb{R}|)=|\mathbb{R}|$, by standard cardinal arithmetic. $\endgroup$ – Henno Brandsma Jul 19 '19 at 4:26
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ The sentence beginning "Therefore it suffices" isn't what you meant. $\endgroup$ – Andreas Blass Jul 19 '19 at 0:55
  • $\begingroup$ @AndreasBlass Oh, it is a typo. Thanks $\endgroup$ – TheWildCat Jul 19 '19 at 1:00
  • $\begingroup$ @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$ $\endgroup$ – WaterBro Jul 19 '19 at 1:04
  • $\begingroup$ @WaterBro No, the numbers $n\in\mathbb{Z} $ are not included. $\endgroup$ – TheWildCat Jul 19 '19 at 1:05
  • $\begingroup$ @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$ $\endgroup$ – WaterBro Jul 19 '19 at 4:48
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.