Visualizing an "As Discontinuous As Possible" Function

[castor28]

Exhibit a function from $\mathbb{R}$ to $\mathbb{R}$ such that the image of any open interval is the whole of $\mathbb{R}$. (In some sense, such a function is "as discontinuous as possible").

 

[Opalg]

Exhibit a function from $\mathbb{R}$ to $\mathbb{R}$ such that the image of any open interval is the whole of $\mathbb{R}$. (In some sense, such a function is "as discontinuous as possible").

Laborious attempt at a solution:

[sp]Start with the equivalent problem over the rationals, namely to exhibit a function from $\mathbb{Q}$ to $\mathbb{Q}$ such that the image of any open interval is the whole of $\mathbb{Q}$.

For this, let $p_n\ (n\geqslant1)$ be the $n$th prime number. For each integer $s\geqslant2$, let $\theta(s)$ be the smallest $n$ for which $p_n$ divides $s$.

Let $\{r_n\}_{n\geqslant1}$ be an enumeration of the rational numbers.

For a rational number $q$, define $f(q) = 0$ if $q$ is an integer. If $q$ is not an integer then $q = \dfrac rs$ (where $r,s$ are coprime integers and $s>0$). In that case, define $f(q) = r_{\theta(s)}$.

Then $f:\mathbb{Q} \to \mathbb{Q}$ has the required property. In fact, if $J$ is an open interval and $n$ is a positive integer, choose $k$ so that $\dfrac1{p_n^k}$ is less than half the length of $J$. Then $J$ will contain a rational number of the form $q = \dfrac t{p_n^k}$ (where $t$ is an integer not divisible by $p_n$). It follows that $f(q) = r_n$. Thus $f(J)$ contains $r_n$ for every $n$.

Now, having completed the result for rational numbers, what about real numbers?

For that, choose an element $x_\alpha$ in each coset $x+ \mathbb{Q}$ in the additive group $\mathbb{R}$. Extend the above definition of the function $f$ from $\mathbb{Q}$ to $\mathbb{R}$ by $f(x_\alpha + q) = x_\alpha + f(q)$.

Each interval $J$ in $\mathbb{R}$ contains a representative $x_\alpha + q$ of the coset containing $x_\alpha$. The above argument for the rational case shows that $f(J)$ contains $x_\alpha + r_n$ for every $n$. In other words, $f(J)$ contains the whole coset. Since that holds for every $\alpha$, it follows that $f(J)$ is the whole of $\mathbb{R}$, as required.

Note: The Axiom of Choice is needed to choose the numbers $x_\alpha$. Is it possible to answer the question without using the Axiom of Choice?
[/sp]

 

[topsquark]

Laborious attempt at a solution:

[sp]Start with the equivalent problem over the rationals, namely to exhibit a function from $\mathbb{Q}$ to $\mathbb{Q}$ such that the image of any open interval is the whole of $\mathbb{Q}$.

For this, let $p_n\ (n\geqslant1)$ be the $n$th prime number. For each integer $s\geqslant2$, let $\theta(s)$ be the smallest $n$ for which $p_n$ divides $s$.

Let $\{r_n\}_{n\geqslant1}$ be an enumeration of the rational numbers.

For a rational number $q$, define $f(q) = 0$ if $q$ is an integer. If $q$ is not an integer then $q = \dfrac rs$ (where $r,s$ are coprime integers and $s>0$). In that case, define $f(q) = r_{\theta(s)}$.

Then $f:\mathbb{Q} \to \mathbb{Q}$ has the required property. In fact, if $J$ is an open interval and $n$ is a positive integer, choose $k$ so that $\dfrac1{p_n^k}$ is less than half the length of $J$. Then $J$ will contain a rational number of the form $q = \dfrac t{p_n^k}$ (where $t$ is an integer not divisible by $p_n$). It follows that $f(q) = r_n$. Thus $f(J)$ contains $r_n$ for every $n$.

Now, having completed the result for rational numbers, what about real numbers?

For that, choose an element $x_\alpha$ in each coset $x+ \mathbb{Q}$ in the additive group $\mathbb{R}$. Extend the above definition of the function $f$ from $\mathbb{Q}$ to $\mathbb{R}$ by $f(x_\alpha + q) = x_\alpha + f(q)$.

Each interval $J$ in $\mathbb{R}$ contains a representative $x_\alpha + q$ of the coset containing $x_\alpha$. The above argument for the rational case shows that $f(J)$ contains $x_\alpha + r_n$ for every $n$. In other words, $f(J)$ contains the whole coset. Since that holds for every $\alpha$, it follows that $f(J)$ is the whole of $\mathbb{R}$, as required.

Note: The Axiom of Choice is needed to choose the numbers $x_\alpha$. Is it possible to answer the question without using the Axiom of Choice?
[/sp]

Dear Lord! I was actually able to understand that! :)

-Dan

 

[I like Serena]

Dear Lord! I was actually able to understand that! :)

-Dan

I didn't. I got to about half before I lost track. (Worried)
It is mighty impressive though, so perhaps I'll try again.

-ILSe

 

[castor28]

Laborious attempt at a solution:

[sp]Start with the equivalent problem over the rationals, namely to exhibit a function from $\mathbb{Q}$ to $\mathbb{Q}$ such that the image of any open interval is the whole of $\mathbb{Q}$.

For this, let $p_n\ (n\geqslant1)$ be the $n$th prime number. For each integer $s\geqslant2$, let $\theta(s)$ be the smallest $n$ for which $p_n$ divides $s$.

Let $\{r_n\}_{n\geqslant1}$ be an enumeration of the rational numbers.

For a rational number $q$, define $f(q) = 0$ if $q$ is an integer. If $q$ is not an integer then $q = \dfrac rs$ (where $r,s$ are coprime integers and $s>0$). In that case, define $f(q) = r_{\theta(s)}$.

Then $f:\mathbb{Q} \to \mathbb{Q}$ has the required property. In fact, if $J$ is an open interval and $n$ is a positive integer, choose $k$ so that $\dfrac1{p_n^k}$ is less than half the length of $J$. Then $J$ will contain a rational number of the form $q = \dfrac t{p_n^k}$ (where $t$ is an integer not divisible by $p_n$). It follows that $f(q) = r_n$. Thus $f(J)$ contains $r_n$ for every $n$.

Now, having completed the result for rational numbers, what about real numbers?

For that, choose an element $x_\alpha$ in each coset $x+ \mathbb{Q}$ in the additive group $\mathbb{R}$. Extend the above definition of the function $f$ from $\mathbb{Q}$ to $\mathbb{R}$ by $f(x_\alpha + q) = x_\alpha + f(q)$.

Each interval $J$ in $\mathbb{R}$ contains a representative $x_\alpha + q$ of the coset containing $x_\alpha$. The above argument for the rational case shows that $f(J)$ contains $x_\alpha + r_n$ for every $n$. In other words, $f(J)$ contains the whole coset. Since that holds for every $\alpha$, it follows that $f(J)$ is the whole of $\mathbb{R}$, as required.

Note: The Axiom of Choice is needed to choose the numbers $x_\alpha$. Is it possible to answer the question without using the Axiom of Choice?
[/sp]

That looks correct, congratulations.

Concerning your last question, the answer is yes, but you probably need a different approach.

 

[I like Serena]

My attempt, which is admittedly a bit lame, but if I'm not mistaken it does satisfy the conditions of the problem.

Spoiler

The function given by
$$f(x)=\text{random}(x)$$
Where the $\text{random}$ function assigns a given $x$ to a random real number.

 

[Opalg]

My attempt, which is admittedly a bit lame, but if I'm not mistaken it does satisfy the conditions of the problem.

Spoiler

The function given by
$$f(x)=\text{random}(x)$$
Where the $\text{random}$ function assigns a given $x$ to a random real number.

[sp]Nice try! I think that the objection to it is that it does not satisfy the definition of a function because it is not reproducible. If you want to find, for example, $f(0.5)$, it will give you a value. But if you then ask for $f(0.5)$ again, it will almost surely give you a different value.

The definition of a function requires that for every $x$ in the domain of the function there should exist a unique $f(x)$.

[/sp]

 

[I like Serena]

[sp]Nice try! I think that the objection to it is that it does not satisfy the definition of a function because it is not reproducible. If you want to find, for example, $f(0.5)$, it will give you a value. But if you then ask for $f(0.5)$ again, it will almost surely give you a different value.

The definition of a function requires that for every $x$ in the domain of the function there should exist a unique $f(x)$.

[/sp]

Spoiler

The random function I'm proposing is a one-shot random function.
I should have made that clearer.
Say:
$$f(x)=\begin{cases}\text{random real number} &\text{if this is the first time $f(x)$ is evaluated} \\
\text{previous value of }f(x)&\text{otherwise}\end{cases}
$$

 

[I like Serena]

Here's another attempt.

Spoiler

I found that the Weierstrass function is continuous everywhere and differentiable nowhere.
So I propose a variant:
$$f(x)=\sum_{n=0}^\infty 2^n\cos(3^n\pi x)$$
It gets as positive and negative as you want on any open interval however small.

 

[castor28]

Here's another attempt.

Spoiler

I found that the Weierstrass function is continuous everywhere and differentiable nowhere.
So I propose a variant:
$$f(x)=\sum_{n=0}^\infty 2^n\cos(3^n\pi x)$$
It gets as positive and negative as you want on any open interval however small.

[sp]
The Weierstrass function is continuous everywhere. That means that, given $\varepsilon>0$, you can find an interval of width $2\delta$ whose image is contained in an interval of width $2\varepsilon$. That contradicts the fact that the image of any interval must be $\mathbb{R}$. This is what I meant by "as discontinuous as possible".
[/sp]

 

[I like Serena]

[sp]
The Weierstrass function is continuous everywhere. That means that, given $\varepsilon>0$, you can find an interval of width $2\delta$ whose image is contained in an interval of width $2\varepsilon$. That contradicts the fact that the image of any interval must be $\mathbb{R}$. This is what I meant by "as discontinuous as possible".
[/sp]

Spoiler

That's why I picked a variant with $a>1$ while the Weierstrass function requires $0<a<1$.
The Weierstrass form makes the function squeeze to continuity, while my choice makes it explode so that it's not even defined everywhere (for instance not for $x=0$).
Erm... I'm just realizing that with my choice I think the function is not defined anywhere. (Lipssealed)

 

[MountEvariste]

Laborious attempt at a solution:

[sp]Start with the equivalent problem over the rationals, namely to exhibit a function from $\mathbb{Q}$ to $\mathbb{Q}$ such that the image of any open interval is the whole of $\mathbb{Q}$.

For this, let $p_n\ (n\geqslant1)$ be the $n$th prime number. For each integer $s\geqslant2$, let $\theta(s)$ be the smallest $n$ for which $p_n$ divides $s$.

Let $\{r_n\}_{n\geqslant1}$ be an enumeration of the rational numbers.

For a rational number $q$, define $f(q) = 0$ if $q$ is an integer. If $q$ is not an integer then $q = \dfrac rs$ (where $r,s$ are coprime integers and $s>0$). In that case, define $f(q) = r_{\theta(s)}$.

Then $f:\mathbb{Q} \to \mathbb{Q}$ has the required property. In fact, if $J$ is an open interval and $n$ is a positive integer, choose $k$ so that $\dfrac1{p_n^k}$ is less than half the length of $J$. Then $J$ will contain a rational number of the form $q = \dfrac t{p_n^k}$ (where $t$ is an integer not divisible by $p_n$). It follows that $f(q) = r_n$. Thus $f(J)$ contains $r_n$ for every $n$.

Now, having completed the result for rational numbers, what about real numbers?

For that, choose an element $x_\alpha$ in each coset $x+ \mathbb{Q}$ in the additive group $\mathbb{R}$. Extend the above definition of the function $f$ from $\mathbb{Q}$ to $\mathbb{R}$ by $f(x_\alpha + q) = x_\alpha + f(q)$.

Each interval $J$ in $\mathbb{R}$ contains a representative $x_\alpha + q$ of the coset containing $x_\alpha$. The above argument for the rational case shows that $f(J)$ contains $x_\alpha + r_n$ for every $n$. In other words, $f(J)$ contains the whole coset. Since that holds for every $\alpha$, it follows that $f(J)$ is the whole of $\mathbb{R}$, as required.

Note: The Axiom of Choice is needed to choose the numbers $x_\alpha$. Is it possible to answer the question without using the Axiom of Choice?
[/sp]

This is a thing of beauty!

 

[castor28]

Here is a solution that does not use the Axiom of Choice.

[sp]
Since the interval $(0,1)$ is homeomorphic to $\mathbb{R}$ (for example, via $x\mapsto\dfrac{1-2x}{x(x-1)}$, we may replace the domain and the co-domain with $(0,1)$, i.e., we look for a function $f : (0,1)\to(0,1)$ that maps any open interval to $(0,1)$.

Given $x\in(0,1)$, we consider the decimal expansion of $x$. If there are two such expansions (like $0.5=0.499\ldots$), we can choose either one, but the rule must be fixed to ensure that the function is well defined.

If the expansion contains infinitely may 9 digits, we take $f(x)=0.5$. Otherwise, we remove all the digits up to and including the last 9 (if there is no 9, we don't remove anything), and interpret the remaining digits as the base 9 representation of a number $y$. If $y = 0$ or $y=1=0.888\ldots$, we take $f(x)=0.5$; otherwise, we take $f(x)=y$.

Conversely, given $y\in(0,1)$ and an interval $(a,b)\subset(0,1)$, we must find $x\in(a,b)$ such that $f(x)=y$. The given interval contains an interval $[n\,10^{-k}, (n+1)\,10^{-k})$ for a sufficiently large integer $k$; when written in decimal, all the numbers in that interval start with the same $k$ digits $0.x_1\ldots x_k\,$. We write $y$ in base 9 as $0.y_1y_2\ldots$ and take x as the decimal interpretation of $0.x_1\ldots x_k9y_1y_2\ldots\,$.
[/sp]