25
$\begingroup$

There is an example of a function that is unbounded on every open set. Just take $f(n/m) = m$ for coprime $n$ and $m$ and $f(irrational) = 0$.

I want to generalize this in a way to get a function which is not just unbounded on every open set, but whose range is equal to $\mathbb{R}$ on every open set. The latter construction clearly doesn't work.

I'm interested whether such function exists and if it exists is there any constructive way to define it?

$\endgroup$
2

9 Answers 9

44
$\begingroup$

See Conway's base 13 function.

$\endgroup$
9
  • 2
    $\begingroup$ Wow, that is a fabulous example. $\endgroup$ Jul 16, 2010 at 11:06
  • 2
    $\begingroup$ Why does everything Conway does end up making me cry? ^_^ p.s. I think that function definitely belongs here: mathoverflow.net/questions/22189/… $\endgroup$
    – Vectornaut
    Jul 16, 2010 at 16:50
  • $\begingroup$ OK, I don't have anything to add here, other than to say that this was the coolest thing I learned today. Wow! $\endgroup$ Jul 17, 2010 at 5:23
  • 2
    $\begingroup$ These comments make me feel a bit slow: what does Conway's function have over the simpler functions given in several of the answers below? $\endgroup$
    – gowers
    Dec 11, 2010 at 14:50
  • 1
    $\begingroup$ @gowers The ease with which one can specify an explicit pre-image of any real in any target domain interval. $\endgroup$ Dec 11, 2010 at 17:01
46
$\begingroup$

For a non-constructive solution, let $\pi : \mathbb{R} \to \mathbb{R}/\mathbb{Q}$ be the projection homomorphism, and let $g : \mathbb{R}/\mathbb{Q} \to \mathbb{R}$ be a bijection. Then the composition $g\circ \pi$ has the desired property.

$\endgroup$
6
  • $\begingroup$ What a coincidence! This one also makes me cry. Where did you get the idea to play with R/Q? In hindsight, it obviously exists, but it never would have popped into my mind uninvited. Does it have any, uh, "practical applications"? $\endgroup$
    – Vectornaut
    Jul 16, 2010 at 16:58
  • $\begingroup$ Does the existence of the bijection $g$ require the continuum hypothesis? $\endgroup$ Jul 16, 2010 at 17:20
  • 2
    $\begingroup$ Dear Nate: I don't think so. The equality |R/Q| |Q|=|R| implies |R/Q|=|R|. (Use a section of the canonical projection R -> R/Q to prove |R/Q| |Q|=|R|. Other wording: take a system of coset representatives.) $\endgroup$ Jul 16, 2010 at 18:26
  • 1
    $\begingroup$ I should have said that the equality |G/H| |H|=|G| between cardinal numbers holds for any subgroup H of any group G. (This has nothing to do with R and Q.) $\endgroup$ Jul 17, 2010 at 9:59
  • 1
    $\begingroup$ @Pierre-YvesGaillard Is there a proof of this equality of cardinalities that does not resort to representatives of (left) cosets? I suspect that this assertion is equivalent to $\mathsf{AC}$. $\endgroup$ Oct 8, 2023 at 18:24
6
$\begingroup$

This is not really a new solution, but just a way to see one can come up with Jim's answer. The problem is equivalent to finding an equivalence relation on $\mathbb{R}$ such that each equivalence class is dense and there are $2^{\aleph_0}$ equivalence classes. To see this, suppose you have such an equivalence class $\equiv$. Consider the natural map $\pi: \mathbb{R} \to \mathbb{R}/\equiv$. Clearly the pre-image of every point is dense and now, you can post-compose $\pi$ with a bijection between $\mathbb{R}/\equiv $ and $\mathbb{R}$. The converse is similar.

Now, as $\mathbb{R}$ has the structure of an additive group, one can define equivalence relations by using subgroups: $x \equiv y$ iff $x-y$ is in a given subgroup $H$. Now if you use $H=\mathbb{Q}$, then you get the answer given by Jim Belk. You can use $H$ to be the subgroup of $2$-adic rationals. Then the $x$ is equivalent to $y$, if all but finitely many of their binary digits are equal, from which you can define

$\endgroup$
6
$\begingroup$

As suggested by Gerry, Example 27 in Chapter 8 of Gelbaum and Olmstead's Counterexamples in Analysis is such a function.

$\endgroup$
6
$\begingroup$

A couple more ways of thinking about it. (There are connections with some of the answers above.)

  1. The graph of the function has to have the property that it intersects every horizontal line segment of positive length in the plane. Well-order these line segments such that each one has fewer predecessors than the cardinality of the reals, and then stick a point in them one at a time. At each stage, one has put fewer points into the graph than there are points in a line segment, so there will be points in the segment that are not vertically above or below points that are already chosen. When you've covered all the line segments, choose the remainder of the function arbitrarily.

  2. Enumerate all open intervals with rational end points. Now inductively create a graph as follows. Pick the first interval, and take a copy of the Cantor set inside it. Biject that copy of the Cantor set to the reals. Pick the second interval and find inside it an open interval disjoint from the Cantor set chosen earlier. Inside that, take a copy of the Cantor set and biject it to the reals. Keep going. The complement of the set where you've defined the function so far is always open and dense, so you can always continue. (It goes without saying that there's nothing special about copies of the Cantor set: any class of sets with cardinality that of the reals that is closed under countable intersections and does not include any open intervals will do the job.)

$\endgroup$
4
$\begingroup$

My instinct is to reach for Gelbaum and Olmstead, Counterexamples in Analysis, but it's in my office, and I'm at home.

$\endgroup$
1
$\begingroup$

Once we have the idea of prodding the decimal expansion, there are any number of things we can do. Here are a few. We may assume we're starting with $0.a_1a_2a_3...$, e.g. by taking the fractional part of the input. If any of the sums/limits mentioned below fails to exist, map the input to $0$.

  1. We construct the decimal digits of the image $b_0.b_1b_2b_3...$ one at a time. Consider the alternating sum of the $a_i$ for $i$ odd. If this converges (i.e. these $a_i$ are $0$ from some point on), then define $b_0$ to be this. Next, look at the alternating sum of the $a_i$ with $i\equiv 2 \mod 4$. If this converges to a number in $\{0,...,9\}$, then define $b_1$ to be this. Then construct $b_2$ using the $a_i$ with $i\equiv 4 \mod 8$, and so on.

  2. Map the number to $\sum \frac{(-1)^{a_n}}{n}$.

  3. Map the number to $\lim_{n\to\infty} (a_1+...+a_n)/n$. This will give us results only in $[0,9]$, but that's sufficient.

In each case, whatever tiny interval we're forced to start in, we can always get any output we like by using later digits.

$\endgroup$
1
$\begingroup$

You can even say something much stronger. As Gowers points out, you can reformulate the question as: Does there exist a function that intersect any vertical line, in any open interval? Here you can substitute "vertical line" with "continuous function" and "open interval" with "set with positive measure". The construction is exactly as Gowers point 1. You only have to use that the set of continuous function and the Borel $\sigma$-algebra each have the same cardinality as $\mathbb{R}$.

I wonder if you could substitute "continuous function" with "measureable function" in the above? How many measureable function are there?

$\endgroup$
2
  • $\begingroup$ Is this really stronger? That is, does there exist a function that intersects any vertical line in any open interval, but does not intersect some continuous function in some open interval? $\endgroup$ Dec 26, 2015 at 19:48
  • $\begingroup$ Yes. Let f be a function that intersects any vertical line in any open interval and define g(x)= f(x) for values x with g(x) != x and g(x) = x+1 for all other x. Clearly g does not intersect the continuous function that sends x to x but g intersects any vertical line in any open interval. $\endgroup$ Dec 27, 2015 at 8:50
1
$\begingroup$

Here is an explicit construction that uses only elementary functions and limits: define $f(x)=\lim_{n\rightarrow \infty}(n!\pi x)$ when that limit exists, and e.g. 0 otherwise. Notice that this $f$ is periodic with every rational number as its period. So it is enough to show that $f$ is surjective (and then you can take any preimge of any point and move it into any interval). To show that it's surjective, let $y\in \mathbb{R}$, and take $r\in \mathbb{R}$ to be such that $\tan(r\pi)=y$. Then one can check that the limit $\sum_{n=0}^\infty \frac{\lfloor rn\rfloor}{n!}$ is mapped by $f$ to $y$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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