Monday, March 6, 2017

elementary set theory - Is there a bijection between $mathbb{N} times mathbb{R}$ and $mathbb{R}$



So I'm doing some practice on set theory, and I am having some trouble proving a lemma.



Basically I want to ask if there is there a bijection between $\mathbb{N} \times \mathbb{R}$ and $\mathbb{R}$



If yes, could someone provide a simple construction of such a bijection?




Any help or insights is deeply appreciated.


Answer



For just answering the yes/no question, the easiest way is to use the Swiss knife of bijections, the Cantor-Schröder-Bernstein theorem, which just requires us to construct separate injections in each direction $\mathbb R\to\mathbb N\times\mathbb R$ and $\mathbb N\times\mathbb R\to\mathbb R$ -- which is easy:



$$ f(x) = (1,x) $$



$$ g(n,x) = n\cdot \pi + \arctan(x) $$



Because there is an injection either way, Cantor-Schröder-Bernstein concludes that a bijection $\mathbb R\to\mathbb N\times\mathbb R$ must exist.







If you already know $|\mathbb R\times\mathbb R|=|\mathbb R|$, you can get by even quicker by restricting your known injection $\mathbb R\times\mathbb R\to \mathbb R$ to the smaller domain $\mathbb N\times\mathbb R\to\mathbb R$ instead of mucking around with arctangents.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...