Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Problem for fun, not homework.

Is there an injective/bijective function $f : \mathbb R \to \mathbb R$ that is dense in $\mathbb R^2$?

I am completely lost as to how to begin on this sort of problem. I was able to prove the existence of a surjective function by exploiting a fact about the Vitali set (proof is below):

Let $V$ denote an arbitrary Vitali set. We can partition $\mathbb R = \bigcup_{q \in \mathbb Q} V+q$ where $V+q = \{ v+q | v \in V \}$. Since $V$ has the cardinality of the continuum, we have a bijection $g : V \to \mathbb R$. Define $f$ such that $f(v+q) = g(v)$. It is clear that for any point $(x,y)$, $y = g(v)$ for some fixed $v$ and $x$ is arbitrarily close to $v+q$ for some rational $q$. So $f$ is dense in $\mathbb R^2$.

Edit for clarification: by being dense in $\mathbb R^2$ I mean that we’re taking a subset of $\mathbb R^2$ that has as its elements the ordered pairs $(x,y)$ such that $f(x) = y$.

share|improve this question
    
What does this mean? The function maps into $\mathbb{R}$ but then $\mathbb{R}^2$ appears. Is the question about the image of $f$ under the embedding of $\mathbb{R}\hookrightarrow \mathbb{R}^2$ along the $x$-axis? If so, then the answer is no because the image will be contained in a line. –  Matt Nov 27 '12 at 2:42
    
By dense, I mean the set $A = \{ (x,y) \in \mathbb R^2 | f(x) = y \}$ is dense in $\mathbb R^2$. –  Andrew Salmon Nov 27 '12 at 2:46
    
Ah thanks. That makes sense. –  Matt Nov 27 '12 at 3:33
add comment

2 Answers 2

up vote 3 down vote accepted

Let $(p_n,q_n)$ be an enumeration of $\mathbb{Q}^2$, and let $\alpha$ be a real number such that $\sin \alpha$ and $\cos \alpha$ are independent over $\mathbb{Q}$. Now we rotate this enumeration by $\alpha$, and realize it as a countable subset of our graph. This will automatically make it dense, and then we can extend the function to the whole real line bijectively by simple set theory. We have to check that this rotation actually gives us a graph, and that the function is one-to-one on this countable set.

Let $$ \begin{bmatrix} x_n \\ y_n \end{bmatrix} =\begin{bmatrix} \cos \alpha & \sin \alpha \\ -\sin \alpha & \cos \alpha \end{bmatrix} \begin{bmatrix} p_n \\ q_n \end{bmatrix}. $$ If $p\cos \alpha + q\sin \alpha = p' \cos \alpha + q' \sin \alpha$ for rational $p,q,p',q'$, then by the independence of $\cos \alpha$, $\sin \alpha$ over $\mathbb{Q}$ we have $p=p'$ and $q=q'$. This implies that $x_n = x_m$ if and only if $n=m$. The same argument also shows $y_n=y_m$ if and only if $n=m$.

Let $X= \{ x_n: n \in \mathbb{N} \}$ and $Y= \{ y_n: n \in \mathbb{N} \}$. Define a function $f:X \to Y$ by $f(x_n) = y_n$. By the argument above this is a well-defined bijection, and since the graph is a rotation of the enumeration of $\mathbb{Q}^2$, it is dense in the plane. Since $\mathbb{R} \setminus X$ and $\mathbb{R}\setminus Y$ both have the cardinality of the continuum, there exists a bijection between them, extending $f$ to a bijection from $\mathbb{R}$ to itself with a dense graph.

share|improve this answer
    
Wow! Did not expect something this elegant. –  Andrew Salmon Nov 27 '12 at 3:36
add comment

Here's an almost purely set theoretic construction of such a function. I'll describe the graph of a bijection function whose graph is dense in $\mathbb{R}^2$.

Begin by well ordering all the open rectangles of $\mathbb{R^2}$ with order type $\mathfrak{c}$. Also, well order $\mathbb{R}$ with order type $\mathfrak{c}$ as well, so it makes sense to talk of the "least" real number with a given property.

We'll define an injective function inductively. To begin with, choose any point in the first open subset.

Now, assume inductively that for all ordinals $\beta < \alpha$, we have chosen a point $(x_\beta, y_\beta)\in U_\beta$ such that for $\beta\neq\gamma$, we have both $x_\beta\neq x_\gamma$ (so we're still making a function) and $y_\beta \neq y_\gamma$ (so the function is $1-1$).

Consider the open recangle $U_\alpha$. The image of $U_\alpha$ on the $x$-axis is open, so has cardinality $\mathfrak{c}$. Since we have only chosen $<\alpha$ many $x$ values so far and $\alpha < \mathfrak{c}$, the collection of $x$-values we haven't yet picked is nonempty. So, there is a "least" $x$ value we haven't yet chosen. Define $x_\alpha$ to be this $x$ value. Likewise, the image of $U_\alpha$ on the $y$ axis is open, so has cardinality $\mathfrak{c}$, so it contains a $y$ value we haven't picked yet. Define $y_{\alpha}$ to be the "least" such $y$.

Thus, we can continue the induction, so by the principle of transfinite induction, we have now specified a subset $A = \{(x_\alpha, y_\alpha): \alpha < \mathfrak{c}\}\subseteq \mathbb{R}^2$. This $A$ defines a (possibly partial) function by $f(x_\alpha) = y_\alpha$ and by construction this is a function, is 1-1, and has dense graph. What remains is to show that the domain and range are both all real numbers.

To see the domain is all real numbers, pick any real number $x = x_\alpha$. Notice that there are $\mathfrak{c}$ rectangles which, when projected to the $x$ axis, contain $x_\alpha$. But there are only $\alpha$ different $x$s less than $x_{\alpha}$, so for one of these $\mathfrak{c}$ rectangles we picked $x_{\alpha}$. An analogous argument shows the range is all real numbers.

share|improve this answer
    
Lukas's answer was posted while I was typing mine. I think his answer is much nicer than my own, but I thought mine was sufficiently different to still be worth posting. –  Jason DeVito Nov 27 '12 at 3:32
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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