# Injective function from $\mathbb{R}^2$ to $\mathbb{R}$?

Is there an injective function $f :\mathbb{R}^2\rightarrow\mathbb{R}$?

I approached this problem from the perspective of $f^{-1}$, from which I showed there exists a surjective function $f^{-1}:\mathbb{R}\rightarrow\mathbb{R}^2$. Would this imply that there exists an injective function for the inverse mapping?

-
This is the kind of question that allows one to find out who is a constructivist, and who is not. I love it! – Rod Carvalho Sep 16 '12 at 21:46
There is such an injective function, but not a continuous one. – GEdgar Sep 16 '12 at 22:34
– MJD Sep 17 '12 at 6:04

Let's construct an injective function $f : (0,1) \times(0,1) \to (0,1)$. Since there exist bijections between $\mathbb{R}$ and $(0, 1)$, the proposed function $f$ is sufficient to prove the existence of an injective function from $\mathbb{R}^2$ to $\mathbb{R}$.

Let the decimal representation of $x$ be $0.x_1x_2x_3\cdots$, and that of $y$ be $0.y_1y_2y_3\cdots$. Let $f(x, y)$ be $0.x_1y_1x_2y_2x_3y_3\cdots$.

To make this function well-defined, we should avoid decimal representations that end with infinite successive $9$s. Once this is taken care of, it's easy to show that this function is injective.

-

Hint: Take the interval $[0, 1]$ and think how we might try to map pairs of numbers from that interval 1-1 into the interval by 'interleaving' binary representations. In other words if $a = \cdot a_1a_2a_3a_4\ldots$ and $b = \cdot b_1b_2b_3b_4\ldots$, then send $\langle a, b \rangle$ to $\cdot a_1b_1a_2b_2a_3b_3\dots$ ....

-
Fumbling on an iPad, I've just deleted someone's comment by accident. Sorry! The comment was that "this doesn't work" because of the non-uniqueness of binary representations. And my comment on the comment was going to be that this is a hint, an idea to start with! (And I thought that hints are the name of the game when it comes to homework-style questions.) – Peter Smith Sep 17 '12 at 6:25

Whether or not this is sufficient will depend on what framework you are working in. The axiom of choice is equivalent to the statement that every surjective function $g$ has a right inverse. If you can find a surjection $g: \mathbb{R} \rightarrow \mathbb{R}^2$, you can just take $f$ to be a right inverse of $g$, which will necessarily be injective since $g \circ f$ is injective. If you don't have the axiom of choice, then you can't do this.

However, the assertion can be proved without appealing to the axiom of choice. As a hint, think about interweaving the digits of the number. You might have to do a bit of work to deal with non-uniqueness of decimal representations.

-