18
$\begingroup$

IVT Property: If $a<b$ and $y$ is between $f(a)$ and $f(b)$, then there exists $c\in(a,b)$ such that $f(c)=y$.

Theorem. Let $f:\mathbb R \to \mathbb R$ be a function with the IVT Property. If the set of discontinuities of $f$ is first category in $\mathbb R$, then the graph of $f$ is connected.

This is an old Theorem. I assume there must be a counterexample if we leave out the first category assumption, though I don't know of any (help!).

There are functions which are discontinuous everywhere and still have connected graphs. F.B. Jones showed that the graph of a function satisfying $f(x)+f(y)=f(x+y)$ for all $x$ and $y$ can be connected, even if the function is discontinuous everywhere.

So now I come to Conway's example. It has the IVT property in a rather extreme way: it takes every value on every interval. It is discontinuous everywhere. Is the graph connected?

$\endgroup$
5
  • 1
    $\begingroup$ This is a great try at a counterexample. The set of discontinuities of $f$ is all of $\Bbb R$, so it is as far from first category as you can get. A naive try is to separate the graph into $(x,f(x))$ and $(y,f(y))$ with $x \le k$ and $y \gt k$. This fails because any neighborhood of $(k, f(k))$ will include points of the upper half. Now we need to find a path that connects $(k,f(k)+\epsilon)$ to $(k, f(k)-\epsilon)$ without going through any of the points of the graph. $\endgroup$ – Ross Millikan Aug 11 '16 at 5:24
  • 4
    $\begingroup$ 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. $\endgroup$ – Niels J. Diepeveen Aug 11 '16 at 16:39
  • $\begingroup$ Sorry, I should have said that the fibres of $g$ differ from those of $f$ by finitely many points each. $\endgroup$ – Niels J. Diepeveen Aug 11 '16 at 16:50
  • $\begingroup$ @NielsDiepeveen that is a good counterexample! $\endgroup$ – Forever Mozart Aug 11 '16 at 17:27
  • $\begingroup$ and you basically proved that taking every value on every interval is not enough to guarantee the graph is connected. $\endgroup$ – Forever Mozart Aug 11 '16 at 17:30
12
+50
$\begingroup$

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.

$\endgroup$
11
  • $\begingroup$ Sorry, what do you mean by the height of the gap? $\endgroup$ – YuiTo Cheng Jun 27 '19 at 13:55
  • $\begingroup$ @Yui, the $y$-coordinate at which the gap happens. $\endgroup$ – hmakholm left over Monica Jun 27 '19 at 13:57
  • $\begingroup$ (This is well defined because $f_i$ is surjective and increasing, so the supremum of the values of $f_i$ to the left of the gap must be the same as the infimum of the values of $f_i$ to the right of the gap). $\endgroup$ – hmakholm left over Monica Jun 27 '19 at 14:03
  • $\begingroup$ I see. Thanks for your clarification. $\endgroup$ – YuiTo Cheng Jun 27 '19 at 14:06
  • 1
    $\begingroup$ @YuiToCheng: Because $A=\{(x,y)\mid 0<x<1, y > h(x)\}$ is open in $\mathbb R^2$ (so its intersection with $f$ is open in $f$) and its boundary does not contain any points of $f$ (so the rest of $f$ is contained in the complement of the closure of $A$, which is open in $\mathbb R^2$). $\endgroup$ – hmakholm left over Monica Jun 27 '19 at 15:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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