a funny function
05 September 2018

We will show that in Russian Recursive Mathematics (RUSS) [1,2,4] there exists an increasing, uniformly continuous function $f:[0,1] \to \mathbb{R}$, that has roots, is non-constant, but also is such that \[ f(x) = 0 \implies \exists \delta>0 : {f_{\restriction{B_{x}(\delta)}} = 0 } \ .\]

That is, there exists a non-trivial example of a function that, if it attains $0$ at a point $x$ then it is constant $0$ on an entire open neighbourhood of $x$. This seems bizarre, since it feels like the function should never be able to “leave $0$,” yet it does. Another way to look at this is that $f$ is a strong recursive counterexample to a strong form of the Intermediate Value Theorem (IVT), which, under the normal assumptions, assures the existence of the minimal root. This is interesting because there cannot be a strong counterexample to the normal IVT.

The construction of our function relies, not unsurprisingly, on a singular cover of the unit interval in RUSS. A singular cover is a sequence of intervals with rationals endpoints $[a_n,b_n]$ such that

  1. $a_n \lt b_n$
  2. $i\neq j \implies (a_i,b_i) \cap (a_j,b_j) = \emptyset$
  3. $\forall{x \in [0,1]}{\exists{i,j}:{b_i = a_j \land x \in [a_i,b_j]} }$
  4. $ \sum_{i=1}^n \vert b_i - a_i\vert \lt \alpha$

for a given fixed $0< \alpha < 1$.1 We will not require the full strength of 4, but only use the fact that $\left( [a_n,b_n]\right)_{n \geqslant 1}$ cannot be reduced to a finite cover.2 Notice that we can, for every $i$, and unless $a_i = 0$, find the unique interval $[a_j,b_j]$ to the left of $[a_i,b_i]$, that is we can find the unique index $\ell(i)$ such that $b_{\ell(i)} = a_i$. Similarly we can find the index $r(i)$ of the interval just to the right of the interval with index $i$. Let $g(0)$ be the index of the leftmost interval, that is the one containing $0$. For $n>0$ define $g(n) = r^n(g(0))$.

Let $m_i$ be the midpoint of $[a_i,b_i]$.

The idea for the function $f$ is that its value at $m_i$ is $2^{-k}$, where $k$ is the number of intervals to the left of $[a_i,b_i]$, including the limit case $2^{-\infty}$.

More formally: let $f_n$ be the function whose graph connects the points \[ (0,-1), \left(m_{g(0)}, -\frac{1}{2}\right), \left(m_{g(1)}, -\frac{1}{4}\right), \dots \left(m_{g(n)}, -\frac{1}{2^n}\right) , \left(m_{g(n+1)}, 0\right), (1,0) \ . \] It is easy to see that $f_n$ is a Cauchy sequence of increasing functions converging to $f:[0,1] \to \mathbb{R}$. Furthermore $f(m_{g(n)}) = -\frac{1}{2^n} $, and $f(1) = 0$. Since it is increasing and point-wise continuous it is automatically uniformly continuous [5].

Now assume that $x$ is such that $f(x) = 0$. Choose $i,j$ such that $x \in [a_i,b_j] $ and $b_i = a_j$. We must have $f(m_i) = f(m_j) = 0 $. But then also $f(m_{\ell(i)}) = 0$, and therefore $f(y) = 0$ for all $y\in [a_{\ell(i)}, 1]$. Hence $\delta = m_i - m_{\ell(i)}$ is the required modulus.

Bibliography
  • [1] Aberth, Oliver (1980). Computable analysis. .
  • [2] Douglas S. Bridges and Fred Richman (1987). Varieties of Constructive Mathematics. .
  • [3] HD (2018). Constructive Reverse Mathematics. .Habilitationsschrift, University of Siegen, Germany
  • [4] Kushner, B.A. and Leffman, L.I.A. (1984). Lectures on Constructive Mathematical Analysis. .
  • [5] Mandelkern, Mark (1983). Constructive Continuity. .
Footnotes
  • 1 Once we have a singular cover for a specific given $\alpha \lt 1$ on can construct one for any $\alpha \gt 0$ [3].
  • 2 The existence of such a cover is equivalent to the existence of a Kleene tree. The existence of a singular cover as outlined above seems to be a stronger statement [3]