Is the graph of the Conway base 13 function connected?

Solution 1:

Merely knowing that the base-13 function takes every value in every interval does not tell us whether its graph is connected or not. Here is an answer by Eric Wofsey that constructs a function with this property and a connected graph -- on the other hand a comment by Niels J. Diepeveen explains how any such function can be modified to have a disconnected graph without losing the every value-in-every-interval property:

I think a counterexample can be obtained more easily by modifying the function slightly. Let $f$ be Conway's function. Define $g(x)=f(x)+1$ if $f(x)=x$ and $g(x)=f(x)$ otherwise. The fibres of $g$ are still dense in $\mathbb R$ since they differ by only one point each from those of $f$, but $g$ has no fixed points, which gives an easy separation of the graph.

So we need to look closer into Conway's particular definition to resolve the matter.

The graph of the base-13 function is not connected.

In fact it is totally separated (and therefore totally disconnected), since you can carry out variants of the following construction almost everywhere in the plane, enough to separate any two points.

Let $f$ be the Conway function as defined in Wikipedia. I will construct a continuous function $h:\mathbb [0,1]\to[1,2]$ such that $h(x)\ne f(x)$ everywhere. Then $$\{(x,f(x))\mid 0<x<1 \land f(x)>h(x)\}$$ is a nontrivial relatively clopen subset of the graph of $f$ (since $f(0)=f(1)=0$), so the graph is not connected.

The construction depends on the fact that the intersection of the graph of $f$ with the rectangle $[0,1]\times[1,2]$ is the union of countably many functions $f_i$ such that

• $f_i$'s domain is a subset of $[0,1]$
• $f_i$ is non-decreasing, and
• $f_i$ is surjective onto $[1,2]$.

Namely, each $f_i$ handles the inputs where the encoded decimal point is in a particular position, with a particular sequence of tridecimal digits in front of it. Each of them looks a bit like the Cantor function with the interior of each plateau removed, such that there is a horizontal gap instead.

The properties of$f_i$ noted above means that it can be uniquely extended to a non-decreasing $g_i:[0,1]\to[1,2]$. (At points where $f_i(x)$ is not defined, there can only be one possible value of $g_i(x)$ that won't break monotonicity). We have that $g_i(0)=1$, $g_i(1)=2$ and $g_i$ is continuous.

My $h$ will be strictly decreasing, with its values chosen such that it intersects each $g_i$ at an $x$-coordinate where $f_i$ is not defined. This prevents it from intersecting each of the $f_i$s and therefore from intersecting all of $f$.

We start by setting $h(0)=2$, $h(1)=1$ and now inductively define a sequence of additional points on $h$. In this phase we maintain the invariants that

• $h$ is defined at finitely many points in $[0,1]$.
• $h(x)$ is (so far) only defined for points where $f(x)=0$.
• Whenever $h(a)$ and $h(b)$ are defined for distinct $a$ and $b$, the slope $\frac{h(a)-h(b)}{a-b}$ will be strictly between $-2$ and $0$. (We easily see that it is enough to enforce this between neighboring points).

Now in step $i$ we will chose an $x_i$ and $h(x_i)$ which prevents $h$ from meeting $f_i$. Consider the piecewise linear function we get from interpolating linearly between the known points of $h$. It is strictly decreasing, so it intersects $g_i$ at exactly one point. If this happens to be at an already known point of $h$, we don't need to add any point in this step.

Otherwise the points where near the intersection point where the slope condition above will let us place a new $(x_i,h(x_i))$ form an open parallelogram of $[0,1]\times[1,2]$, which contains the intersection point. The set of $x$ such that $(x,g_i(x))$ is in the parallelogram is open and nonempty, and therefore we can chose an $x_i$ in this set with $f(x_i)=0$. Now set $h(x_i)=g_i(x_i)$.

At the end of $\omega$ many steps, we will have defined $h(x)$ for a dense set of $x$s, because each interval on the $x$ axis contains the entire preimage of the interior of $[1,2]$ under at least one of the $g_i$s.

This means that $x\mapsto h(x)+x$ is Lipschitz with Lipschitz constant $1$ defined on a dense subset of $[0,1]$, and it therefore extends uniquely to a function on all of $[0,1]$ with the same Lipschitz constant. Subtracting $x$ back out gives us a strictly decreasing continuous $h$ that avoids all $f_i$, as desired.