$\newcommand{\e}{\varepsilon}$In this post I’m going to prove the intermediate value theorem (IVT), Darboux’s theorem, and introduce the Conway base 13 function.
IVT
Let $I = [a,b]$ be a non-empty interval in $\mathbb R$ and consider a continuous $f : I\to\mathbb R$.
Result 1 (IVT): for any $y$ strictly between $f(a)$ and $f(b)$, there is some $c \in (a,b)$ such that $f(c) = y$.
Pf: I’ll follow the proof given in the IVT wikipedia article.
If $f(a) = f(b)$ then there is no $y$ strictly between the two so the statement is vacuously true, therefore WLOG I can take $f(a) \neq f(b)$.
Case I: $f(a) < f(b)$. Let $y \in (f(a), f(b))$. I need to find a $c \in (a,b)$ such that $f(c) = y$. Intuitively, I can identify such a point by thinking about all the domain points that map to things less than or equal to $y$, because then points above that set in the domain get mapped to things greater than $y$, and by continuity that crossing point where $f$ goes from mapping things below $y$ to above $y$ has to actually be mapped to $y$.
So let $S = \{x \in I : f(x) \leq y\}$. By assumption $f(a) < y$ so $a \in S$ which makes $S$ nonempty. Furthermore $y < f(b)$ so $b \notin S$, and additionally $b$ is an upper bound for $S$ since $S \subseteq [a, b)$. This means that $c := \sup S$ is defined and is in $I$.
Note that $c > a$ because $f(a) < y$ so by continuity there is a small neighborhood around $a$ that also is mapped to being less than $y$, and this means $c= \sup S > a$. Also by a similar argument $c < b$, because $c=b$ would mean $x < c \implies f(x) < y$, but there is a small neighborhood around $b$ that is mapped to values greater than $y$.
Now I will show that $f(c) = y$. Fix $\e > 0$. By the continuity of $f$ at $c$ there is a $\delta > 0$ such that
$$
|x – c| < \delta \implies |f(x) – f(c) | < \e.
$$
This is equivalent to
$$
|x – c| < \delta \implies f(x) – \e < f(c) < f(x) + \e.
$$
Now I’ll take some $\ell \in (c – \delta, c) \cap S$. Such an $\ell$ necessarily exists: first, $(c-\delta, c)$ is non-empty as $c$ is neither $a$ nor $b$ so there is a small interval around it in $I$; and secondly if there’s no element of $S$ greater than $c – \delta$, that makes $c – \delta$ also an upper bound to $S$, but this contradicts $c$ being the least upper bound.
So for this $\ell$ I have $|\ell – c| < \delta$ therefore
$$
f(\ell) – \e < f(c) < f(\ell) + \e.
$$
But by $\ell \in S$ I also have $f(\ell) \leq y$ which means
$$
f(c) < f(\ell) + \e \leq y + \e.
$$
Next, take $u \in (c, c+\delta)$. Again by $c \neq b$ I know such a $u$ exists. And furthermore $u > \sup S$ so it cannot be that $u \in S$. All together this means $f(u) – \e < f(c) < f(u) + \e$ and $f(u) > y$, so
$$
f(u) – \e < f(c) \implies y – \e < f(c).
$$
At this point I have shown
$$
|f(c) – y| < \e.
$$
But $\e$ was arbitrary so it must be that $f(c) = y$. The case for $f(b) > f(a)$ is analogous.
$\square$
So that’s the standard IVT from calculus, and it rests heavily on the completeness of $\mathbb R$. The wikipedia article on the IVT gives the example of $f : \mathbb Q \to \mathbb R$ with $f(x) = x^2 – 2$ and shows how the IVT is false here, as $f(0) = -2$ and $f(2) = 2$, yet $f$ has no root in between. $\sup \{q \in \mathbb Q : f(q) < 0\} = \sqrt 2 \notin \mathbb Q$ so the above proof would have failed at that point.
Converse of IVT
A function is called Darboux if it satisfies the conclusion of the IVT, i.e. for any $a < b$ in its domain, if $y$ is between $f(a)$ and $f(b)$ then there is a $c \in (a,b)$ with $f(c) = y$. The IVT establishes that all continuous functions are Darboux. But are these the only Darboux functions? Or equivalently, if $f$ is Darboux is it necessarily continuous?
The answer to that is no. I’ll now prove a result which will allow me to find some discontinuous Darboux functions.
Result 2 (Darboux’s theorem): if $f : I \to \mathbb R$ for $I = [a,b] \subset \mathbb R$ is differentiable then $f’$ is Darboux.
Pf: I’ll follow the first proof given in the wikipedia article on Darboux’s theorem.
Let $y$ be between $f'(a)$ and $f'(b)$. If $y = f'(a)$ then I can take $c=a$ to get $f'(c) = y$, and similarly if $y = f'(b)$, so WLOG I can assume $y$ is strictly between $f'(a)$ and $f'(b)$.
First suppose $f'(a) < f'(b)$. Define $g : I\to\mathbb R$ by $g(x) = f(x) – yx$. $f$ is continuous so $g$ is too, so by the extreme value theorem I know there is some $c \in I$ such that $g(c)$ is the minimum value of $g$ over $I$.
Can $c \in \{a,b\}$? $g'(x) = f'(x) – y$ so $g'(a) = f'(a) – y < 0$ and $g'(b) = f'(b) – y > 0$. This means $g$ is increasing at $b$ so $c \neq b$. If $c = a$ then $g(a)$ is the mininum value of $g$ so this would imply $g(a) – g(x) < 0$ for $x > a$ which means
$$
\frac{g(a) – g(x)}{a – x} \geq 0
$$
for all $x > a$. But somehow $g'(a) < 0$ which wouldn’t be possible now, so it also must be that $c \neq a$. Thus the minimum of $g$ is at an interior point so by Fermat’s theorem $g'(c) = 0$. Plugging this in, I have $$ g'(c) = f'(c) – y = 0 \implies f'(c) = y. $$ The case for $f'(a) > f'(b)$ is analogous except I use a maximum of $g$. Thus either way $f’$ is Darboux.
$\square$
So now I can prove the following result:
Result 3: there exists a discontinuous Darboux function.
Pf: Consider
$$
f(x) = \begin{cases}x^2 \sin(1/x) & x \neq 0 \\ 0 & x = 0 \end{cases}.
$$
I want to show that $f$ is differentiable so by Darboux’s theorem I’ll then have that $f’$ is Darboux.
On $\mathbb R \backslash \{0\}$ $f$ is equal to the product of a differentiable function ($x^2$) and the composition of two differentiable functions ($\sin x$ and $1/x$) so $f$ is differentiable there too. The only potential point of concern then is $x=0$ so I’ll just prove differentiability there. Note that $-x^2 \leq f(x) \leq x^2$ for all $x \in \mathbb R$ so by the squeeze theorem $\lim_{x\to 0} f(x)$ both exists and equals $0$. As for differentiability, I need to show that
$$
\lim_{h\to 0} \frac{f(0 + h) – f(0)}{h}
$$
exists. Plugging in $f$, I find that this equals
$$
\lim_{h\to 0} \frac{h^2 \sin(1/h) – 0}{h} = \lim_{h\to 0} h\sin(1/h) = 0
$$
by the squeeze theorem with $|h|$ and $-|h|$, so $f$ is indeed everywhere differentiable.
I can now compute the derivative with the product and chain rules on $\mathbb R\backslash\{0\}$, and I just found $f'(0)=0$, so all together
$$
f'(x) = \begin{cases}2x\sin(1/x) – \cos(1/x) & x\neq 0 \\ 0 & x = 0\end{cases}
$$
and by Darboux’s theorem $f’$ is Darboux. But is $f’$ continuous at $0$?
Fix $\e \in (0, 1)$. I need to find a $\delta > 0$ such that $|x| < \delta$ implies
$$
|2x\sin(1/x) – \cos(1/x)| < \e.
$$
Suppose there is such a $\delta$. By the Archimedean property of $\mathbb N$ I can find an $N\in\mathbb N$ such that
$$
x_N := \frac{1}{2\pi N} < \delta $$ and for $x_N$ I have $$ |f'(x_N)| = \left\vert2 \frac{\sin(2\pi N)}{2\pi N} – \cos(2\pi N)\right\vert \\ = \left\vert 0 – 1\right\vert = 1 > \e.
$$
This is a contradiction, so there in fact is no such $\delta$ and $f’$ is not continuous at $0$. Thus I have a discontinuous Darboux function. Furthermore, this is an essential discontinuity because the left and right side limits don’t even exist. I can’t make $f’$ continuous just by changing $f'(0)$.
$\square$
That was pretty neat but it’s only discontinuous at one point. I can do much better with the Conway base 13 function which is Darboux yet is discontinuous everywhere, and additionally for any non-degenerate interval $I\subset \mathbb R$ this function is still surjective even when restricted to $I$.
Definition: The Conway base 13 function is a function $f : \mathbb R\to\mathbb R$ defined as follows. For any $x \in \mathbb R$, $x$ can be expressed as a tridecimal (i.e. its base 13 expansion) so it is of the form
$$
x = \pm x_1x_2\dots x_n.y_1y_2y_3\dots_{13}
$$
with each digit $x_i, y_j \in \{0,1, \dots, 9, A, B, C\}$. $f$ is then defined as follows:
1. if $x$ eventually is of the form $Ax_1x_2x_3\dots x_n C y_1 y_2y_3\dots_{13}$ where $x_i, y_j \in \{0,\dots,9\}$, so there is a digit $A$, then a finite sequence of digits $0$ – $9$, and then a $C$, and then digits $0$ to $9$ forever after, take
$$
f(x) = x_1x_2\cdots x_n.y_1y_2y_3\dots_{10}
$$
2. If instead $x$ is eventually of the form $Bx_1x_2x_3\dots x_n C y_1 y_2y_3\dots_{13}$, take
$$
f(x) = -x_1x_2\cdots x_n.y_1y_2y_3\dots_{10}.
$$
3. If neither condition is met, set $f(x)=0$.
Thus this function is using the fact that with the three extra symbols provided by a tridecimal expansion, I can store an arbitrary decimal expansion in a tridecimal expansion while also keeping track of the sign and the location of the decimal point via $A$, $B$, and $C$. If I only cared about mapping to positive numbers I could have done this in base 12 so $A$ would have indicated where the integer part starts and $B$ would have given the location of the decimal point. But for signed numbers base 13 does the trick.
Result 4: let $a < b$ so $I := (a,b)$ is an open interval in $\mathbb R$. Claim: $f$ is surjective on $(a,b)$. Pf: Let $r \in \mathbb R$ so $r = x_1\dots x_n.y_1y_2\dots_{10}$. For now assume $r > 0$. I will find a $s \in (a,b)$ such that $f(s)=r$, which means that $s$ in base 13 needs to eventually be of the form
$$
s = \cdots A x_1\dots x_n C y_1y_2\dots_{13}.
$$
I can achieve this by finding a number in $(a,b)$ with a finite tridecimal expansion, and then adding on $A x_1\dots x_n C y_1y_2\dots_{13}$ to the end after allowing enough leading zeros to ensure I’m still in $(a,b)$.
Let $m = \frac{a+b}{2}$ so $a < m < b$. For $k \in \mathbb N$ let $t_k = \text{trunc}(m, k)$ be the truncation of $m$ to $k$ tridecimal places.
I’m now going to show that for any $a<b$ eventually $(t_k)$ is in $(a,b)$. I want to consider $|m – t_k|$, so I’ll let $m = 0.a_1a_2\dots_{13}$ and then $t_k = 0.a_1a_2\dots {a_k}_{\,13}$ (WLOG I can ignore the integer part as that will get subtracted off). This means $$ |m – t_k| = 0.00\dots0a_{k+1}a_{k+2}\dots_{13} \leq 0.\underbrace{0\dots01}_{k}{}_{13} = 13^{-k}. $$ Thus for each $k\in\mathbb N$ I’ll have $|m – t_k| \leq 13^{-k}$, so for any $\e > 0$ there is a $K\in\mathbb N$ such that $k \geq K \implies |m – t_k| < \e$, or in other words
$$
\lim t_k = m.
$$
In particular this means eventually I’ll have
$$
|m – t_{k_0}| < \min\{m-a, b-m\} $$ for some $k_0\in \mathbb N$ so I have now produced a number $t := t_{k_0} \in (a,b)$ with a finite tridecimal expansion. I now need to paste $A x_1\dots x_n C y_1y_2\dots$ on the end of $t$, which is just addition. Let $z = (x_1, x_2, \dots, x_n, y_1, y_2, \dots)$ so this new number is of the form $$ s := t + \sum_{j = 1}^\infty z_j13^{-(j + q)} $$ for $q > k_0$ determining how many leading zeros there are to the term I’m adding on. $s \geq t$ so I’ll need to choose $q$ so that $s \in (a,b)$ still, which in this case is equivalent to $s < b$.
I can require that a base $b$ expansion never ends in infinitely many $b-1$ digits (so e.g. $1_{10}$ would be used instead of $0.999\dots_{10}$), which means that it can’t be that every $z_j =12$. Thus
$$
s < t + 12 \sum_{j=1}^\infty 13^{-(j+q)} = t + 12 \sum_{j=q+1}^\infty 13^{-j}.
$$
Using the result for geometric series I have
$$
\sum_{j=q+1}^\infty 13^{-j} = \sum_{j=0}^\infty 13^{-j} – \sum_{j=0}^{q}13^{-j} \\
= \frac{1}{1 -13^{-1}} – \frac{1 – 13^{-q-1}}{1 – 13^{-1}} \\
\frac {13^{-q}}{12}
$$
so all together I have
$$
s < t + 12 \sum_{j=q+1}^\infty 13^{-j} \\
= t + 13^{-q}
$$
I know $t < b$ and since $13^{-q} \to 0$ eventually I will have $s < b$ as well, which means $s\in(a,b)$. And by construction $f(s) = r$.
If instead $r < 0$ then the exact same thing works but with $B$ instead of $A$ in the tridecimal appended to $t$ to make $s$. Finally if $r = 0$ then I can just pick some number like $$ t + A \cdot \sum_{j = p}^\infty 13^{-j} $$ which for a sufficiently large $p$ is both in $(a,b)$ and guaranteed to map to $0$. So all together $f$ is a surjection on $(a,b)$, and $(a,b)$ was arbitrary so in fact $f$ is a surjection on any interval $(a,b)$.
$\square$
Corollary: $f$ is discontinuous everywhere. Pf: let $a\in\mathbb R$. For any $\delta > 0$ I just showed that $f$ is surjective on $(a-\delta, a+\delta)$ so it definitely isn’t the case that $f$ can be forced to be within $\e$ of $f(a)$ by making $\delta$ sufficiently small. This means that $f$ is everywhere discontinuous.
$\square$
So that’s Conway’s base 13 function. At first I think it seems rather magical but really it’s just a very clever way to make use of the fact that for any real number $r$ and interval in $\mathbb R$, there is a number in that interval that eventually has $r$’s entire decimal expansion after some finite number of digits, and the base 13 is a nice way to encode the sign and separate the integer and fractional parts.