Proof Let $\{p_{i}\}_{i\in \mathbb {N}}$ be an enumeration of $[0,1]_{\mathbb {Q}}$ . We recursively define a sequence of rationals $\{a_{i}\}_{i\in \mathbb {N}}$ as follows. Let $a_{0}=0$ .

For given $a_{i}\in \mathbb {Q}$ we let $a_{i+1}\in \mathbb {Q}$ such that $|a_{i}-a_{i+1}|<4^{-i}$ and $|f(p_{i})-a_{i+1}|>4^{-i}/2 $ . One can always pick such $a_{i+1}$ effectively since the required condition on $a_{i+1}$ given $a_i$ is $\Sigma ^{0}_{1}$ . (Here we use the well-known fact that a dependent choice function for a $\Sigma ^{0}_{1}$ binary predicate of numbers is available within $\mathsf {RCA}_{0}$ . See, e.g., the argument in the proof of [Reference Simpson11, Theorem II.5.8], or [Reference Yokoyama14, Theorem 2.1].) Put $a=\lim _{n\to \infty }a_{i}$ and note that $|a - a_{i+1}| \le 4^{-i}/3$ . Therefore $|f(p_{i})-a|> 4^{-i}/2 - 4^{-i}/3>0$ . ⊣

Proof (i) Consider the $\Sigma ^{0}_{1}$ -definable sets $\mathcal {A}=\{(p,q)\in [0,1]_{\mathbb {Q}}\times \mathbb {Q}: f(p)< q\}$ and $\mathcal {B}=\{(p,q)\in [0,1]_{\mathbb {Q}}\times \mathbb {Q}: f(p)> q\}$ . To obtain a rational presentation for f, it suffices to find a set $Z\subseteq [0,1]_{\mathbb {Q}}\times \mathbb {Q}$ such that $\mathcal {A}\subseteq Z\subseteq [0,1]_{\mathbb {Q}}\times \mathbb {Q}\setminus \mathcal {B}$ . Such a set Z is obtained by an instance of $\Sigma ^{0}_{1}$ -separation, an axiom scheme which follows from $\mathsf {WKL}_0$ over $\mathsf {RCA}_{0}$ [Reference Simpson11, Lemma IV.4.4].

(ii) We may assume that f avoids rational numbers after passing to a vertical shift of f via Lemma 4.2. Then both $\mathcal {A}$ and $\mathcal {B}$ are $\Delta ^{0}_{1}$ . ⊣

Proof Within $\mathsf {RCA}_{0}$ , one can effectively find the value of a continuous function. Thus, the restriction to $[0,1]_{\mathbb {Q}}$ of a continuous function $f:[0,1]\to \mathbb {R}$ has a canonical encoding. ⊣

Sketch of proof

We define a uniformly computable sequence of reals $(r_e) $ such that $r_e$ is very close to $2^{-e}$ ; say $|r_e - 2^{-e}| \le 2^{-2e}$ . The function f is then obtained by linear interpolation between the values $f(2^{-e})= r_e$ ; in particular $f(0)=0$ and f is computable in the usual sense of computable analysis.

We define $r_e$ using a Cauchy name, as follows. Initially we let $r_e = 2^{-e}$ . If stage s is least such that $s\ge 2e$ and $e \in A_s$ we subtract $2^{-s}$ to $r_e$ and leave $r_e$ at this value. If stage s is least such that $s\ge 2e$ and $e \in B_s$ we add $2^{-s}$ from $r_e$ and leave $r_e$ at this value.

If Z is a rational presentation of f, let $X = \{e \colon \, (2^{-e},2^{-e}) \in Z\}$ . If $e \in A$ then $f(2^{-e})< 2^{-e}$ and hence $e \in X$ . If $e \in B$ then $f(2^{-e})> 2^{-e}$ and hence $e \not \in X$ . ⊣

Proof It is routine to transfer the computability theoretic proof above into an argument that the given assertion implies $\Sigma ^0_1$ separation over $\mathsf {RCA}_{0}$ . By [Reference Simpson11, Lemma IV.4.4] the scheme of $\Sigma ^0_1$ separation is equivalent to ${\textsf {WKL}}_{0}$ over $\mathsf {RCA}_{0}$ . ⊣

Proof Suppose that $\tau \in T\leftrightarrow \forall n \, \theta (n,\tau )$ . By $\Delta ^{0}_{1}$ comprehension, there exists a tree

$$ \begin{align*} \bar{T}=\{\tau: \forall n\le |\tau|\forall \sigma\preceq\tau \, \theta(n,\sigma)\}. \end{align*} $$

Then, $T\subseteq \bar {T}$ , and any path of $\bar {T}$ is a path of T by the definition of T. By $\mathsf {WKL}_0$ , $\bar {T}$ has a path, thus T has a path. ⊣

Proof Let $M\in \mathbb {N}$ such that $\mathbf {v}_{f}\le M$ . We fix an effective listing $( p_n, q_n )_{n \in \mathbb {N}}$ of all elements of $[0,1]_{\mathbb {Q}}\times \mathbb {Q}$ , and identify $Z:\mathbb {N}\to \{0,1\}$ as $\{(p_{n},q_{n}):Z(n)=1\}\subseteq [0,1]_{\mathbb {Q}}\times \mathbb {Q}$ . We construct a binary tree T such that any path Z through T encodes a non-decreasing function $g :[0,1]_{\mathbb {Q}} \to \mathbb {R}$ with $f \le ^*_{\textsf {slope}} g$ . To do so, we ensure that the following conditions hold:

$\mathcal {R}_0:$  for any $r\in \mathbb {N}$ , $0\le g(p_r) \le M$ ;

$\mathcal {R}_1:$  for any $r,s\in \mathbb {N}$ , if $p_s \le p_r$ , $q_s \ge q_r$ , and $g(p_s)> q_s$ then $g(p_r)> q_r$ ; and

$\mathcal {R}_2:$  for any $r,s\in \mathbb {N}$ , if $p_s \le p_r$ then $f(p_r) - f(p_s) \le g(p_r) - g(p_s)$ .

Here, $\mathcal {R}_1$ guarantees that any g encoded by a path $Z_g$ through T is non-decreasing, and $\mathcal {R}_2$ guarantees the slope condition. Formally, we will consider a $\Pi ^{0}_{1}$ definable tree T to be the set of all $\tau \in 2^{<\mathbb {N}}$ such that

$$ \begin{align*} \text{(r0)}& \ \forall r < |\tau| \Big[(q_{r}\le 0\to \tau(r) = 0) \wedge (q_{r}\ge M\to \tau(r) = 1)\Big], \\ \text{(r1)}& \ \forall r, s < |\tau| \Big[(p_r \le p_s \land q_r \ge q_s \land \tau(r) = 0) \to \tau(s) = 0\Big], \\ \text{(r2)}& \ \forall r, s < |\tau| \Big[ (p_r \le p_s \land \tau(r) = 0 \land \tau (s) = 1) \to | f(p_s) - f(p_r) | \le q_{s}-q_{r}\Big]. \end{align*} $$

To see that T is infinite, notice that since f is of bounded variation, the string $Z_{v_{f}}|_k$ defined as $s\in Z_{v_{f}}|_k$ iff $\mathbf {v}_{f}(p_{s})<q_{s}$ and $s<k$ , which is available from bounded $\Sigma ^{0}_{1}$ comprehension (see [Reference Simpson11, Theorem II.3.10]), is an element of T for every $k \in \mathbb {N}$ . Thus by Lemma 4.7, T has a path Z. By (r0) and (r1) (for the case $p_{r}=p_{s}$ ), Z encodes a rational presentation. Let g be the unique function $ [0,1]_{\mathbb {Q}} \to \mathbb {R}$ defined as $g=g_{Z}$ .

Thus, this $g=g_{Z}$ is the desired function.⊣

Proof Take $K\in \mathbb {N}$ so that $|P|<K$ for any prefix-free set $P\subseteq T$ . By $\Sigma ^0_1$ induction, take

(1) $$ \begin{align} k = \max\{i\le K : \text{there is a prefix-free set } P \subseteq T \text{ with } |P| = i\}. \end{align} $$

Let $P_k \subseteq T$ witness (1). Let $\sigma = \max P_k$ , where the max is taken with respect to the usual integer encoding of binary strings. Let $\ell = \max \{|\tau | : \tau \in P_k\}$ . Any $\tau \in T$ with $|\tau |> \ell $ must extend an element of $P_k$ , and can have at most one successor. By the pigeonhole principle (which is available from $\Sigma ^{0}_{1}$ induction), there exists $\tau \in P_{k}$ with infinitely many extensions in T. Since each extension of $\tau $ of length exceeding $\ell $ has exactly one successor, we can effectively find a path through $ T$ extending $\tau $ .⊣

Proof 1 $\Rightarrow $ 2 is Theorem 4.8, 2 $\Rightarrow $ 3 is a direct consequence of Corollary 4.4(ii), and 3 $\Rightarrow $ 4 is trivial. We show 4 $\Rightarrow $ 1. We reason within $\mathsf {RCA}_0$ . Let $T \subseteq 2^{<\mathbb {N}}$ be an infinite binary tree. Assume for a contradiction that T has no path. Let $\widetilde {T} = \{\tau \in 2^{<\mathbb {N}} : \tau \not \in T \land \tau |_{(|\tau | - 1)} \in T\}$ . Without loss of generality we may assume that $\widetilde {T}$ is infinite. Consider the $\Sigma ^{0}_{1}$ definable set

$$ \begin{align*} \textrm{Nonext}(T):=\{\tau \in T : \tau \text{ has only finitely many extensions in } T\}. \end{align*} $$

Then, by [Reference Simpson11, Lemma II.3.7], there exists a one-to-one function $h:\mathbb {N}\to \mathbb {N}$ such that $\text {rng}(h)=\textrm{Nonext}(T)$ . (Here, we identify a binary string with its usual integer encoding.)

Let $(\widetilde {\sigma }_k)_{k\in \mathbb {N}}$ be an enumeration of $\widetilde {T}$ such that $|\widetilde {\sigma }_i| \le |\widetilde {\sigma }_{i+1}|$ . Note that for any $k, \ell \in \mathbb {N}$ ,

(2) $$ \begin{align} |\widetilde \sigma_k | \le \ell \rightarrow k \le 2^\ell. \end{align} $$

For all $\sigma \in 2^{<\mathbb {N}}$ put $I_\sigma = [0.\sigma , 0.\sigma + 2^{-|\sigma |}]$ . For each $s \in \mathbb {N}$ define a polygonal function $f_s :[0,1] \to \mathbb {R}$ as follows. On the interval $I_{\widetilde {\sigma }_k}$ set

(3) $$ \begin{align} f_s = \begin{cases} \textrm{M}_{I_{\widetilde{\sigma}_k}}(2^{-k}, 2^{k - h(k)}) & \text{if } s\ge k> h(k), \\ 0 & \text{otherwise.} \end{cases} \end{align} $$

Let $f_s = 0$ elsewhere. Then $(f_s)_{s\in \mathbb {N}}$ defines an effectively uniformly continuous function $f = \lim _{s}f_s$ . By Corollary 4.4(ii), one may replace f with a vertical shift and then assume that f has a rational presentation.

We show that f is of bounded variation. As in the proof of Theorem 3.1, we only need to consider the variation of f on the disjoint intervals $I_{\widetilde {\sigma }_k}$ . Let $m \in \mathbb {N}$ , and for each $k \le m$ let $\Pi _k$ be a partition of $I_{\widetilde {\sigma }_k}$ containing the midpoints and endpoints of each sawtooth defined on that interval. For all $s \ge m$ one has

$$ \begin{align*} \sum \limits_{k = 0}^m V(f, \Pi_k) = \sum \limits_{k = 0}^m V(f_s, \Pi_k) \le \sum \limits_{k = 0}^m 2^{-h(k) + 1} < 1, \end{align*} $$

as required.

By our hypothesis in (5), there exists a rationally presented non-decreasing function $g :[0,1]_{\mathbb {Q}} \to \mathbb {R}$ such that $f \le ^*_{\textsf {slope}} g$ . Let $\Delta : \mathbb {N} \to \mathbb {R}$ be the function given by $\Delta (k) = \max \{g(0.\sigma + 2^{-|\sigma |}) - g(0.\sigma ) : \sigma \in T \land |\sigma | = k\}.$ Note that $\Delta $ is non-increasing.

There are two cases to consider. If $\lim _{n \to \infty } \Delta (n) = 0$ , then g behaves like a continuous function. This provides a decomposition of f that allows us to use an argument similar to the one in Theorem 3.1 to prove the existence of $\text {rng}(h)$ . One can then find a path through T by avoiding this set.

Otherwise, there is a jump-type discontinuity of g. The intervals around this point correspond to strings which form an infinite subtree $\widehat T$ of T. One can bound the size of any prefix-free subset of $\widehat T$ using the size of this jump, and thus effectively find a path through $\widehat T$ .

We now analyse the two cases in detail.

Case 1. $\lim _{n\to \infty }\Delta (n) = 0$ . Take $\gamma : \mathbb {N} \to \mathbb {N}$ such that $\Delta (\gamma (n)) < 2^{-n}$ . Such $\gamma $ exists by $\Delta ^{0}_{1}$ comprehension since “ $\Delta (k)<2^{-n}$ ” can be described by a $\Sigma ^{0}_{1}$ formula. If $h(k) = n<k$ then by (3),

$$ \begin{align*} g(0.\widetilde{\sigma}_k + 2^{-|\widetilde{\sigma}_k|}) - g(0.\widetilde{\sigma}_k) \ge V(\textrm{M}_{I_{\widetilde{\sigma}_k}}(2^{-k}, 2^{k - h(k)}), \Pi_k)= 2^{-h(k)+1}\ge 2^{-n}. \end{align*} $$

Hence $|\widetilde {\sigma }_k| \le \gamma (n)$ , and then by (2) $k \le 2^{\gamma (n)}$ . This gives

$$ \begin{align*} n \in \text{rng}(h) \leftrightarrow \exists k \le \max\{2^{\gamma(n)},n\}[h(k) = n], \end{align*} $$

so $\text {rng}(h)=\textrm{Nonext}(T)$ exists by $\Delta ^0_1$ comprehension. Thus $\textrm{Ext}(T)=T \setminus \textrm{Nonext}(T)$ exists. Now, one can construct a path of T by an easy primitive recursion: starting from the empty string, one can choose the left most immediate extension of a given string in $\textrm{Ext}(T)$ .

Case 2. There exists $M \in \mathbb {N}$ such that $\forall m \exists n [n> m \land \Delta (n) > 2^{-M}]$ Then there are infinitely many strings $\sigma \in T$ such that

$$ \begin{align*} g(0.\sigma + 2^{-|\sigma|}) - g(0.\sigma)>2^{-M}. \end{align*} $$

Without loss of generality, we may take $K\in \mathbb {N}$ such that $0\le g(0)<g(1)\le K$ . Let $L=\{i/2^{M+2}: 0\le i\le K2^{M+2}\}$ . Given a rational presentation Z of g, for $x,y,z\in \mathbb {Q}$ , we write $g(y)-g(x)\ge _{L}z$ if there exist $r,s\in \mathbb {N}$ such that $x=p_{r}$ , $y=p_{s}$ , $q_{r},q_{s}\in L$ , $Z(r)= {1}$ (which implies that $g(p_{r})<q_{r}$ ), $Z(s)={0}$ (which implies that $g(p_{s})>q_{s}$ ) and $q_{s}-q_{r}\ge z$ . Since L is finite, $g(y)-g(x)\ge _{L}z$ is actually $\Delta ^{0}_{1}$ statement as we only need to check finitely many r and s. Note that if $g(y)-g(x)>2^{-M}$ , then $g(y)-g(x)\ge _{L}2^{-M-2}$ since there are at least two points in $L\cap (g(x),g(y))$ .

The tree $\widehat T\subseteq T$ defined by $\widehat T=\{\sigma \in T: g(0.\sigma + 2^{-|\sigma |}) - g(0.\sigma ) \ge _{L}2^{-M-2}\}$ . is an infinite subtree of T. (The case assumption guarantees that $\widehat T$ is infinite, and $\widehat T$ is closed under prefixes because g is non-decreasing.) We verify the cardinality of any prefix-free subset of $\widehat T$ is bounded. For any prefix-free $P \subseteq \widehat T$ , we have

$$ \begin{align*} |P|2^{-M-2} \le \sum \limits_{\sigma \in P} g(0.\sigma + 2^{-|\sigma|}) - g(0.\sigma) \le g(1) - g(0) \le K. \end{align*} $$

Thus, $|P|\le K2^{M+2}$ . Hence by Lemma 4.9, $\widehat T$ has a path, and thus T has a path. ⊣

Proof Without loss of generality, we may suppose that $0\le f(0)\le f(1)\le 1$ . Assume that f is not pseudo-differentiable at z. If z is rational, then z is not Martin–Löf random, so assume that z is irrational. We will consider the following two cases.

Case 1. . Thus, for any $m\in \mathbb {N}$ , there exists $a_{0}<z<b_{0}$ such that for any $a,b\in \mathbb {Q}$ , $a_{0}<a<z<b<b_{0}\to S_{f}(a,b)>2^{m}$ . For a given $\sigma \in 2^{<\mathbb {N}}$ , we let $l_{\sigma }=0.\sigma $ and $r_{\sigma }=0.\sigma +2^{-|\sigma |}$ . Let $\varphi (m,\sigma )$ be a $\Pi ^{0}_{1}$ -formula saying that $S_{f}(l_{\sigma },r_{\sigma })\le 2^{m}$ . Write $\varphi (m,\sigma )\equiv \forall s \theta (s,m,\sigma )$ for a $\Sigma ^{0}_{0}$ -formula $\theta $ , and put

$$ \begin{align*} T_{m}:=\{\sigma\in 2^{<\mathbb{N}}: \forall \tau\preceq \sigma \forall s<|\sigma|\theta(s,m,\tau)\}. \end{align*} $$

Since $f(1)-f(0)\le 1$ , for each $m\in \mathbb {N}$ and $k\in \mathbb {N}$ , there are at most $2^{k}$ strings of length $m+k$ which are not in $T_{m}$ . Thus, $\mu (T_{m})\ge 1-2^{m}$ , and hence $\langle 2^{\mathbb {N}}\setminus [T_{m}]: m\in \mathbb {N} \rangle $ forms a Martin–Löf test. By the assumption, $z\notin [T_{m}]$ for any $m\in \mathbb {N}$ . Thus z is not Martin–Löf random relative to f.

Case 2. and . We will follow the proof of (iii) $\to $ (ii) of [Reference Brattka, Miller and Nies1, Theorem 4.3] halfway within $\mathsf {RCA}_{0}$ .

Since f is non-decreasing and , the limit $\lim _{y \to z} f(y)$ exists by nested interval completeness [Reference Simpson11, Theorem II.4.8] which holds in $\mathsf {RCA}_{0}$ . So we may assume that $f(z)$ exists and f is continuous at z; this will be needed in the following argument when we apply a version of [Reference Brattka, Miller and Nies1, Lemma 2.5] formalized within $\mathsf {RCA}_{0}$ .

For given $p,q\in \mathbb {Q}$ , an interval A is said to be a $(p,q)$ -interval if it is of the form $A=(pi2^{-n}+q,p(i+1)2^{-n}+q)$ for some $n\in \mathbb {N}$ and $i\in \mathbb {Z}$ . For a finite set $L\subseteq \mathbb {Q}^{2}$ , an interval is said to be L-interval if it is a $(p,q)$ -interval for some $(p,q)\in L$ . One can formalise within $\mathsf {RCA}_{0}$ the proofs of Lemmas 2.5 and 4.1, and most of the proof of Lemma 4.4 of [Reference Brattka, Miller and Nies1]. To see this, note that these arguments only rely on elementary arithmetic, which can be formalised within $\mathsf {RCA}_{0}$ . Hence we have the following.

Claim 6.2.1. There exist rationals $\beta>\gamma >0$ and a finite set $L\subseteq \mathbb {Q}^{2}$ such that

$$ \begin{align*} \gamma &> \lim_{h\to 0} \inf \{S_{f}(A): A\text{ is an } L\text{-interval}\wedge |A|\le h\wedge z\in A\},\\ \beta & < \lim_{h\to 0} \sup \{S_{f}(A): A\text{ is an } L\text{-interval}\wedge |A|\le h\wedge z\in A\}. \end{align*} $$

In the final step of the proof of [Reference Brattka, Miller and Nies1, Lemma 4.4] for both inequalities there, one picks $(p,q)$ and $(r,s)$ from L which by themselves witness the two inequalities above, respectively; that is, we only need to look at $(p,q)$ intervals for the first, and at $(r,s)$ -intervals for the second. However, this is impossible within $\mathsf {RCA}_{0}$ since it requires an essential use of the infinite pigeonhole principle (also known as $\textrm{RT}^{1}$ ) which is equivalent to $\textrm{B}\Sigma ^0_2$ . Thus, we need to take a detour around this part of the proof.

We fix $\beta ,\gamma $ and $L\subseteq \mathbb {Q}^{2}$ as in Claim 6.2.1. An n-depth alternation L-sequence is a length $2n+1$ decreasing sequence of L-intervals $[0,1]\supseteq A_{0}\supseteq A_{1}\supseteq \dots \supseteq A_{2n}$ such that $S_{f}(A_{2i})<\gamma $ for any $i\le n$ , $S_{f}(A_{2i+1})>\beta $ for any $i<n$ . For $(p,q),(r,s)\in L$ , an n-depth alternation $(p,q)$ ; $(r,s)$ -sequence is an n-depth alternation L-sequence such that $A_{2i}$ is a $(p,q)$ -interval for any $i\le n$ and $A_{2i+1}$ is an $(r,s)$ -interval for any $i<n$ . The last interval of an n-depth alternation $(p,q)$ ; $(r,s)$ -sequence is called an n-depth $(p,q)$ ; $(r,s)$ -interval. By Claim 6.2.1, for any $n\in \mathbb {N}$ , there exists an n-depth alternation L-sequence such that $z\in A_{2n}$ . Furthermore, by the finite pigeon hole principle, every $n|L|^{2}$ -depth alternation L-sequence contains an n-depth alternation $(p,q)$ ; $(r,s)$ -subsequence for some $(p,q),(r,s)\in L$ . Thus, we have the following claim.

Note that we cannot fix $(p,q),(r,s)\in L$ for all $n\in \mathbb {N}$ in this claim since it would require $\textrm{B}\Sigma ^0_2$ again.

Next, we will calculate the size of n-depth $(p,q)$ ; $(r,s)$ -intervals. Fix $(p,q),(r,s)\in L$ and let $\{A^{s}\}_{s<u}$ be a finite collection of n-depth $(p,q)$ ; $(r,s)$ -intervals. Take an n-depth alternation $(p,q)$ ; $(r,s)$ -sequence $A^{s}_{0}\supseteq \dots \supseteq A^{s}_{2n}=A^{s}$ for each $s<u$ , and let

. For a finite union of intervals

which is described by a finite disjoint union as

, put

and

. Since any two $(p,q)$ -intervals (or $(r,s)$ -intervals) are disjoint, or one includes the other, we have that

for any $i\le n$ and

for any $i<n$ . Thus, for any $i<n$ ,

Hence,

(4)

Now, put

$$ \begin{align*} U_{n}^{(p,q);(r,s)} &:= \bigcup \{ A: A\text{ is an } n \text{-depth }(p,q);(r,s)\text{-interval}\},\\ U_{n}&:=\bigcup_{(p,q),(r,s)\in L}U_{n}^{(p,q);(r,s)}. \end{align*} $$

Note that one can enumerate all n-depth $(p,q)$ ; $(r,s)$ -intervals f-computably. By $(4)$ , $\bar \mu (U_{n}^{(p,q);(r,s)})\le (\gamma /\beta )^{n}$ . Thus, $\bar \mu (U_{n})\le (\gamma /\beta )^{n}|L|^{2}$ . By Claim 6.2.2, $z\in \bigcap _{n\in \mathbb {N}}U_{n}$ . Thus z is not Martin–Löf random relative to f.

Proof Choose $q\in \mathbb {Q}$ such that $ \mu (S)\le \bar \mu (U) \le q<1$ . Then, $\mu (T_{S})\ge 1-q$ . Let $\widetilde {T} = \{\tau \in 2^{<\mathbb {N}} : \tau \not \in T_{S} \land \tau |_{(|\tau | - 1)} \in T_{S}\}$ . Put

$$ \begin{align*} T^{n}:=\{\sigma_{0}^{\frown}\dots^{\frown}\sigma_{k}: k< n\wedge [ \forall i< k\, \sigma_{i}\in \widetilde{T}]\wedge \sigma_{k}\in T_{S}\}. \end{align*} $$

Then, we have $\mu (T^{n})\ge 1-q^{n}$ . Thus, for large enough $l\in \mathbb {N}$ , $\langle 2^{\mathbb {N}}\setminus [T^{ln}]: n\in \mathbb {N} \rangle $ forms a Martin–Löf test relative to S, and hence $Z\in [T^{ln}]$ for some $n\in \mathbb {N}$ . By $\Sigma ^{0}_{1}$ -induction, take

$$ \begin{align*} m=\max\{m': \exists c\le ln\, \exists \langle \sigma_{i}\in\widetilde{T}: i<c \rangle(Z|_{m'}=\sigma_{0}^{\frown}\dots^{\frown}\sigma_{c-1})\}. \end{align*} $$

Then, the tail W of Z defined by $W(i)=Z(i+m)$ is in $[T_{S}]$ , whence $0.W\in [0,1]\setminus U$ .⊣

Proof We show that the result holds in any countable model $(\mathcal {M}, \mathcal {S})$ of ${\textsf {WWKL}}_{0}$ . Let $f : [0,1]_{\mathbb {Q}} \to \mathbb {R}$ be a rationally presented function of bounded variation in $(\mathcal {M}, \mathcal {S})$ , and let $U\subseteq [0,1]$ be an open set such that $\bar \mu (U) < 1$ . We will show that there exists a real $z\in [0,1]\setminus U$ such that f is pseudo-differentiable at z. Let $(\mathcal {M}, \widehat {\mathcal {S}}) \models {\textsf {WKL}}_{0}$ be the model given by Lemma 6.5. By Theorem 4.10,

$$ \begin{align*} (\mathcal{M}, \widehat{\mathcal{S}}) \models \textsf{Jordan}_{\mathbb{Q}}. \end{align*} $$

Hence $\widehat {\mathcal {S}}$ contains a non-decreasing function $g : [0,1]_{\mathbb {Q}} \to \mathbb {R}$ such that $f \le ^*_{\textsf {slope}} g$ .

Within $(\mathcal {M}, \widehat {\mathcal {S}})$ , define $h : [0,1]_{\mathbb {Q}} \to \mathbb {R}$ by $h(x) = g(x) - f(x)$ . By Lemma 6.5 again, there is a real $z \in [0,1]$ such that $z \in \mathcal {S}$ and $z \in \mathsf {MLR}^{g \oplus h\oplus \mathcal {U}}$ . By Lemma 6.6, we may assume that $z\in [0,1]\setminus U$ . The functions g and h are pseudo-differentiable at z in $(\mathcal {M}, \widehat {\mathcal {S}})$ by Lemma 6.2. Therefore f is pseudo-differentiable at z in $(\mathcal {M}, \widehat {\mathcal {S}})$ , and hence in $(\mathcal {M}, \mathcal {S})$ .⊣

Proof 1 $\Rightarrow $ 2 is Theorem 6.7, 2 $\Rightarrow $ 3 is trivial, 2 $\Rightarrow $ 4 is straightforward from Corollary 4.4. For 4 $\Rightarrow $ 5, within $\mathsf {RCA}_{0}$ , we have $\bar \mu (\emptyset )=0$ , since if $[[S]]=\emptyset $ , then S is empty, so $\mu (S)=0$ . Thus, if an open set $U\subseteq [0,1]$ has positive measure, then U is not empty. It remains to show $\neg $ 1 $\Rightarrow \neg $ 3 and $\neg $ 1 $\Rightarrow \neg $ 5.

We show $\neg $ 1 $\Rightarrow \neg $ 3. Assuming $\neg $ 1 we first construct an open set $U\subseteq [0,1]$ such that $\bar {\mu }(U)<1$ and $[0,1]\setminus U$ only contains rationals. The idea is similar to the one in the proof of Proposition 5.1: If $\textrm{WWKL}$ fails, there is a tree T with no paths such that $\mu (T)\ge \varepsilon $ where $\varepsilon>0$ . Put

$T'=\{\tau \in 2^{<\mathbb {N}}\mid \tau =\sigma ^{\frown }0^{k}$ for some $\sigma \in T$ and $k<|\tau |\}$ ,

$\widetilde T=\{\tau \in 2^{<\mathbb {N}}\mid \tau \notin T'$ and $\tau |_{|\tau |-1}\in T'\}$ , and

$U=\bigcup _{\tau \in \widetilde T}(0.\tau ,0.\tau +2^{-|\tau |})\subseteq [0,1]$ .

As in the proof of Proposition 5.1, we have $\bar \mu (2^{\mathbb {N}}\setminus [T'])\le 1-\mu (T)<1$ , and any path of $T'$ is rational. Thus $\bar \mu (U)\le \bar \mu (2^{\mathbb {N}}\setminus [T'])<1$ and $[0,1]\setminus U$ only contains rationals.

Next we construct a rationally presented non-decreasing function which is not pseudo-differentiable at any rational. Let $\{q_{i}\}_{i\in \mathbb {N}}$ be an enumeration of $[0,1]_{\mathbb {Q}}$ . Define a function $f:[0,1]_{\mathbb {Q}}\to \mathbb {R}$ by $f(p)=\sum _{q_{i}<p}2^{-i}$ . Clearly, f is non-decreasing and not pseudo-differentiable at any rational. By Proposition 4.3, some vertical shift of f has a rational presentation. Thus we have $\neg $ 3.

Finally, we show $\neg $ 1 $\Rightarrow \neg $ 5. This implication is related to [Reference Brattka, Miller and Nies1, Theorem 6.7] (originally due to Demuth) in the setting of reverse mathematics. If $\textrm{WWKL}$ fails, there is a tree T with no path such that $\mu (T)\ge \varepsilon $ where $\varepsilon>0$ . We construct a sequence of trees $\langle T_{n}: n\in \mathbb {N} \rangle $ such that no $T_{n}$ has a path and $\mu (T_{n})\ge 1-2^{-4n}$ . Let the $T^{i}$ be defined as in the proof of Lemma 6.6 where $q = 1- \varepsilon $ . No $T^{i}$ has a path, and $\mu (T^{i})\ge 1-(1-\varepsilon )^{i}$ . Thus, one can effectively choose $i_{0}<i_{1}<\dots $ so that $\mu (T^{i_{n}})\ge 1-2^{-4n}$ . Now let $T_n = T^{i_n}$ .

Let $\widetilde {T}_{n} = \{\tau \in 2^{<\mathbb {N}} : \tau \not \in T_{n} \ \land \ \tau |_{|\tau | - 1} \in T_{n}\}$ . As before put $I_{\sigma }:=[0.\sigma ,0.\sigma +2^{-|\sigma |}]$ . Since $T_{n}$ has no path we have $[0,1]=\bigcup _{\sigma \in \widetilde {T}_{n}}I_{\sigma }$ for any n. Since $\mu (T_{n})\ge 1-2^{-4n}$ we have $\sum _{\sigma \in \widetilde {T}_{n}}|I_{\sigma }|\le 2^{-4n}$ . Note that if $\sigma \in \widetilde {T}_{n}$ and $m<n$ , there exists $\tau \in \widetilde {T}_{m}$ such that $\tau \preceq \sigma $ . Note also that $|\sigma |\ge n$ for any $\sigma \in \widetilde {T}_{n}$ .

For $v \in \mathbb R^+$ and $r \in \mathbb N$ , recall $\textrm {M}_A(v, r)$ denotes a sawtooth function on the interval A with r many teeth of height v. For each $n,s \in \mathbb {N}$ define a polygonal function $f_{n,s} :[0,1] \to \mathbb {R}$ as follows. For $\sigma \in \widetilde {T}_{n}$ , on the interval $I_{\sigma}$ , set

$$ \begin{align*} f_{n,s} = \begin{cases} \textrm{M}_{I_{\sigma}}(2^{-2n-|\sigma|}, 2^{5n}) & \text{if } |\sigma|\le s, \\ 0 & \text{otherwise.} \end{cases} \end{align*} $$

Then $(f_{n,s})_{s\in \mathbb {N}}$ defines an effectively uniformly continuous function $f_{n}$ . For these functions $f_{n}$ one can check the following properties.

1. (i) If $\sigma \in \widetilde {T}_{n}$ , $x\in I_{\sigma }$ and $m\ge n$ , then $0\le f_{m}(x)\le 2^{-2m-|\sigma |}$ . In particular, $|f_{n}|\le 2^{-2n}$ .

2. (ii) For any $0\le x<y\le 1$ and for any $n\in \mathbb {N}$ , $|f_{n}(x)-f_{n}(y)|/|x-y|\le 2^{3n+1}$ .

3. (iii) $\mathbf {v}_{f_{n}}\le 2^{-n+1}$ .

(i) and (ii) follow from the definition. To see (iii),

$$ \begin{align*} \mathbf{v}_{f_{n}}=\sum_{\sigma\in \widetilde{T}_{n}}\mathbf{v}_{\textrm{M}_{I_{\sigma}}(2^{-2n-|\sigma|}, 2^{5n})}=\sum_{\sigma\in \widetilde{T}_{n}}2^{3n-|\sigma|+1}\le 2^{3n+1}2^{-4n}=2^{-n+1}. \end{align*} $$

Define an effectively uniformly continuous function f by $f=\sum _{n\in \mathbb {N}}f_{n}$ . Then, f is of bounded variation since $\mathbf {v}_{f}=\sum _{n\in \mathbb {N}} \mathbf {v}_{f_{n}}\le 2$ . Actually, f is absolutely continuous. One can see this as follows. For any $x\in [0,1]$ and $\varepsilon>0$ , take large enough $n\in \mathbb {N}$ so that $\sum _{j>n}\mathbf {v}_{f_{j}}<\varepsilon /2$ . Since each $f_{i}$ , $i\le n$ , is absolutely continuous by (ii), one can find $\delta>0$ so that $\sum _{i\le n}(f_{i}(x)-f_{i}(y))<\varepsilon /2$ for any y such that $|x-y|<\delta $ .

By Corollary 4.4(ii), after replacing f with a vertical shift we may assume that f has a rational presentation.

We will see that this f is not pseudo-differentiable at any point. Let $x\in [0,1]$ , $\delta>0$ and $K\in \mathbb {N}$ . We will find $a\le x\le b$ so that $b-a<\delta $ and $|S_{f}(a,b)|>K$ . Take $n\in \mathbb {N}$ large enough so that $2^{3n-1}>K$ and $|I_{\sigma }|<\delta $ for any $\sigma \in \widetilde {T}_{n}$ . Since $T_{n}$ has no path, there exists $\sigma \in \widetilde {T}_{n}$ such that $x\in I_{\sigma }$ . Let $a\le x\le b$ so that $a,b$ are nearest to x yielding extreme values of the saw-tooth function $\textrm {M}_{I_{\sigma }}(2^{-2n-|\sigma |}, 2^{5n})$ . Then, $|f_{n}(b)-f_{n}(a)|=2^{-2n-|\sigma |}$ and $b-a=2^{-5n-1-|\sigma |}$ . By (i), $|f_{j}(b)-f_{j}(a)|\le 2^{-2j-|\sigma |}$ for any $j>n$ , and by (ii), $|f_{i}(b)-f_{i}(a)|/|b-a|\le 2^{3i+1}$ for any $i<n$ . Thus,

$$ \begin{align*} \frac{|f(b)-f(a)|}{|b-a|}&\ge \frac{|f_{n}(b)-f_{n}(a)|}{|b-a|}-\sum_{j>n}\frac{|f_{j}(b)-f_{j}(a)|}{|b-a|}-\sum_{i<n}\frac{|f_{i}(b)-f_{i}(a)|}{|b-a|}\\ &\ge\frac{2^{-2n}-|\sigma|}{2^{-5n-1-|\sigma|}}-\sum_{j>n}\frac{2^{-2j-|\sigma|}}{2^{-5n-1-|\sigma|}}-\sum_{i<n}2^{3i+1}\\ &\ge 2^{3n+1}-2^{3n}-2^{3n-1} = 2^{3n-1}. \end{align*} $$

Hence, $|S_{f}(a,b)|>K$ .⊣