6
$\begingroup$

What is the reverse mathematics strength of
"For all Lipschitz functions $\; f : \mathbb{R} \to \mathbb{R} \;$, $\;$ there exists a real number $x$ such that $f$ is differentiable at $x$." ?
(defined using epsilon-delta, so not requiring that there exist a function witnessing the convergence)

Since Lipschitz functions are differentiable almost everywhere,
I would guess the answer is "is equivalent to WWKL$_0$ (over RCA$_0$)".

Improve this question
$\endgroup$
3
  • $\begingroup$ Are you just looking for a lower bound, or an upper bound too? Did you check whether the "standard" proof works in $\mathsf{WWKL}_0$? $\endgroup$
    – François G. Dorais
    Commented Oct 6, 2011 at 22:19
  • $\begingroup$ I'm looking for both a lower bound and an upper bound. $\;$ I couldn't find the "standard" proof anywhere. $\endgroup$
    – user5810
    Commented Oct 6, 2011 at 22:30
  • $\begingroup$ You should probably add the "logic" tag, right? $\endgroup$
    – Jason Rute
    Commented Oct 7, 2011 at 15:32

2 Answers 2

Reset to default
7
$\begingroup$

(Update: I made my answer clearer and also fixed the references and added more.)

Your theorem should be true in every $\omega$-model of $\mathsf{RCA}_0$ as follows. The following paper

  • Brattka, Miller and Nies. Randomness and Differentiability. Submitted. (preprint)

proves that every computable function on $[0,1]$ that is Lipschitz is differentiable on all computable randoms. Further, from this proof, I believe you can extract a single computable martingale $M$ such that if $x$ is a point of differentiability of $f$, then $M$ does not succeed on $x$. Unlike ML randomness---which corresponds to $\mathsf{WWKL}_0$---with a test for computable randomness, i.e. the computable martingale $M$, you can compute a real $y$ such that $M$ doesn't succeed on $y$.

Hence there is (I believe) a real $y$ computable from the function $f$ for which $f$ is differentiable at $x$.

Hence your theorem holds in every $\omega$-model of $\mathsf{RCA}_0$.

This implies that your theorem is true in $\mathsf{RCA}_0$ or $\mathsf{RCA}_0$ plus some first order principle.

I should mention, I learned of this trick from Steve Simpson (in the case of Schnorr randomness).

Of course to see if it is provable in ${RCA}_0$, you should check that level of induction/collection used. A recent paper with Jeremy Avigad and Ed Dean,

  • Avigad, Dean and Rute. Algorithmic Randomness, reverse mathematics, and the dominated convergence theorem. Submitted (preprint)

gives an example where the dominated convergence thereom, in a sense, corresponds to $2$-randomness, but the reverse math strength of the dominated convergence thereom was a bit higher, since $\Sigma^0_2$ collection was needed.

(You do not not seem to need this, but...) even though you know a point $x$ such that $f$ is differentiable, that doesn't mean you know what the derviative is at that point. Actually, you can't even compute the derivative $f'$ in the $L^1$ norm.

There are more published and unpublished works related to the diffentiability of computable functions. One good summary of the recent work in this area is the Logic Blog on Andre Nies's website. Another is this talk by Nies.

There are also three results in preparation that may be of value. I proved, as did Pathak, Rojas and Simpson independently, that the Lebesgue differentiation theorem holds on Schnorr randoms. In particular this implies that a more restrictive notion of computable Lipschitz function is differentiable on Schnorr randoms (see Nies' talk mentioned above). Freer, Kjos-Hanssen and Nies, have a paper in preparation about Lipschitz functions and differentiability, which in a sense, "reverses" the above results. (Again, this is mentioned in the talk by Nies.)

Improve this answer
$\endgroup$
8
  • $\begingroup$ Is "that test" [$\hspace{.01 in} f$ being differentiable at $x$] or [the martingale]? $\endgroup$
    – user5810
    Commented Oct 6, 2011 at 23:29
  • $\begingroup$ By test I meant the martingale. It is computable from the function. If f is differentiable at x, then it cannot succeed on the martingale. There may be a null set of differentiable points that succeed on the martingale as well. $\endgroup$
    – Jason Rute
    Commented Oct 6, 2011 at 23:38
  • $\begingroup$ "If $f$ is differentiable at $x$, then it cannot succeed on the martingale." $\hspace{2 in}$ ... except for a null set of points $f$ is differentiable at? $\endgroup$
    – user5810
    Commented Oct 6, 2011 at 23:50
  • $\begingroup$ Sorry, I said the converse! Let me try to say it correct this time. As you know, the set of non-differentiable points of $f$ is null. From $f$ we can compute a martingale $M$ such that if $f$ is not differentiable at $x$, then $M$ succeeds on $x$. (I said "$x$ succeeds on the martingale" before but that was incorrect terminology---the martingale succeeds on $x$.) Now, since we can compute from $M$ some $y$ on which $M$ does not succeed, we can also computed a real for which $f$ is differentiable. $\endgroup$
    – Jason Rute
    Commented Oct 7, 2011 at 2:33
  • $\begingroup$ Do you know a link to "Brattka, Miller and Nies, Randomness and Differentiability"? $\;$ I can't find it online. $\endgroup$
    – user5810
    Commented Oct 7, 2011 at 7:37
4
$\begingroup$

Here it is, the newest version

http://dl.dropbox.com/u/370127/papers/randomnessanalysisjuly_2011.pdf

What jason says is right, even for nondecreasing functions. It is in our paper, Subection 5.1

Hence there is (I believe) a real $y$ computable from the function $f$ for which $f$ is differentiable at $x$.

Hence your theorem holds in every $\omega$-model of RCA0.

This implies that your theorem is true in RCA0 or RCA0 plus some first order principle.

Not sure what these fo principles do, I guess it's standard stuff?

Improve this answer
$\endgroup$
4
  • $\begingroup$ Dear Andre, Welcome to MO! You can use tex-style math as you normally would. The site also uses markdown, which is very useful has some weird side effects from time to time. $\endgroup$
    – François G. Dorais
    Commented Oct 23, 2011 at 1:15
  • $\begingroup$ Andre, I suspect that the theorem goes through in $\mathsf{RCA}_0$, but I would need to walk through the proof carefully to be sure. In case you or another reader is unfamiliar with Reverse Math, the axioms of $\mathsf{RCA}_0$ are basically the Peano axioms but with only induction on $\Sigma_1$ formulas (with second order parameters). Also there is a comprehension axiom for $\Delta_1$ formulas (with parameters). This comprehension axiom ensures the existence of computable sets. (.../...) $\endgroup$
    – Jason Rute
    Commented Oct 24, 2011 at 23:01
  • $\begingroup$ (.../...) It is a common mistake (that I have made in the past) to assume that if a set existence principle (like the one asked about) is computable, then it is provable in $\mathsf{RCA}_0$. A common example is the infinite pigeon-hole principle. Given a computable coloring, an infinite homogeneous set is computable: pick the correct color (by guessing correctly) and enumerate the set. But to prove it, one needs $\mathsf{B}\Sigma_2$, a collection principle between $\Sigma_1$ induction and $\Sigma_2$ induction. $\endgroup$
    – Jason Rute
    Commented Oct 24, 2011 at 23:09
  • $\begingroup$ And yes, this is standard reverse math stuff. The standard resource is Steve Simpson's book Subsystems of Second Order Arithmetic. The first chapter is online at Steve's website: math.psu.edu/simpson/sosoa/chapter1.pdf $\endgroup$
    – Jason Rute
    Commented Oct 24, 2011 at 23:15

You must log in to answer this question.