893: Remarks on Reverse Mathematics/3

[Sam Sanders]

Dear Harvey,

With all due respect for you and your no doubt busy schedule, but 
have you even read what I wrote in my responses to your first two “Remarks on RM” emails?

The thing is, for everything you wrote below, I had already provided a counterexample
in my responses to your first two “remarks on RM”.  

And because you no doubt want to learn what those counterexamples were/are, I will provide them again.  

But let me start with a caveat:  no matter your foundational convictions, we have to have some common ground, 
and ZFC suffices for all the below.  ZFC has third-order objects and ordinary mathematics does not make use
of representations like the ones used in SOA.  Hence, it behooves us to study how our shared reality ZFC and
its representation via SOA relate.  This is important: that you accept (at least) the language of third-order arithmetic 
and view the second-order language as a way of representing objects in the latter (for better or worse).  

> MORE ON DEALING WITH THIRD ORDER OBJECTS IN ORDINARY RM
> 
> FIRST OBSERVATION: The way third order objects are presented in a
> statement about third order objects will generally affect the logical
> status of the statement.
> 
> SECOND OBSERVATION. It is an easy matter for ordinary RM to fully
> accommodate the first observation.
> 
> For example. Let us consider a statement about all continuous
> functions from R into R. In RM one usually just assumes a particular
> way of presenting such functions which I call sequential
> presentations. There are many ways to formalize  sequential
> presentations of continuous functions. There should be a big
> robustness theorem that gives us confidence that any way of talking
> about sequential presentations of these functions are equivalent. So
> the entiere RM treatment of such functions is entirely preserved even
> under the First Observation. How? We simply use the phrase
> "sequentially presented continuous function" in the RM results.

There is nothing wrong with representations: we use them all the time and
all over the place.  However, RM seeks to study theorems of ordinary mathematics
“as they stand” without “constructive or other technical enrichments”.  A big deal is made
of this in SOSOA, and has been discussed on FOM at length.

So the key question is whether representations change logical strength (which would
be bad from the pov of RM).  And they do, even for continuous functions:  

The following second-order statement (formulated using codes for continuous functions) is equivalent to ACA_0:

“The Tietze extension theorem for separably closed sets ”

The following third-order statement (formulated using functions from R to R that happen to satisfy the epsilon-delta
definition of continuity) is provable in Kohlenbach’s base theory (and hence does not imply ACA_0):

“The Tietze extension theorem for separably closed sets”

There are many more examples (see [1]), including well-known thms by Heine and Weierstrass, even “one-point extensions”
due to Yokoyama-Tanaka.  The latter do not mention “separably closed”.

Where did the logical strength go?  It went here: assuming Kohlenbach’s base theory, ACA_0 is 
equivalent to

“for every code f for a continuous function defined an a separably closed set C \subset [0,1], there is 
g:[0,1] -> [0,1] that equals the code f on C.”

So there are models of Kohlenbach’s base theory with many codes that do not denote a third-order object!


I repeat my literary criticism: what should we call these codes that do not denote anything?  Perhaps the ghosts of departed quantities?


The point is that there is a tight connection between second- and third-order objects; an example is:

"if all reals are recursive, then all R-> R functions are continuous.”

The same connection does not exist for codes: even if all reals are recursive, there can be plenty codes for discontinuous functions.
And this is where everything goes South already: because of the disconnect between reals and codes.  

> The only alternative presentations of continuous functions from R into
> R of a similar fundamental character that I am aware of are through
> the Baire classes. I.e., Baire class alpha, where 1 <= alpha <=
> omega_1.
> 
> So for example, there is the reverse mathematics of Baire class
> omega_1 presented continuous functions. There should be a big
> robustness theorem that any way of presenting Baire class alpha
> functions, 1 <= alpha <= omega_1, are equivaelnt in an appropriate
> sense. Then there is a perfectly robust important subject called
> 
> the theory of Baire class alpha presented continuous functions
> 
> where one can use various definitions of continuous here, perhaps most
> naturally just the usual epsilon delta definition. The most
> interesting cases are probably alpha = 1, 2, omega_1.

In my previous email, I mentioned that 

“There is a function that is not Baire class 2” 

is hard to prove in terms of comprehension: Kleene’s quantifier (\exists^3) is needed, which brings
one to the level of full SOA.  So to make sure your codes denote anything,
one needs full SOA…

This is not quite the robustness theorem you were hoping for, I gather.  
The same applies to the below A-I you mention, as follows. 


> 
> Now of course one should in general use Polish spaces rather than R.
> So we have this kind of terminology:
> 
> sequentially continuous Polish functions
> Baire class alpha presented continuous Polish functions
> 
> So this fully accommodates the vast bulk of mathematics commonly
> presented using third order notions like functions from one Polish
> space into another, within the usual RM framework.
> 
> So let's review the A-I from
> https://cs.nyu.edu/pipermail/fom/2021-September/022876.html
> 
> A. Every sequence from X misses an element of X. Here X is a Polish
> space (with an appropriate nontriviality condition).
> B. No function from X into Y is injective. Here X is a nontrivial
> Polish space and Y is an appropriately countable space.
> C. No function from X into Y is bijective. Here X is a nontrivial
> Polish space and Y is an appropriately countable space, but even wider
> contexts may be very interesting.
> D. Every monotone function has at most countably many discontinuities.
> Here use R but maybe some other ordered spaces.
> E. Every function of bounded variation is the difference between two
> monotone functions.
> F. A function is Riemann integrable if and only if it is continuous
> almost everywhere.
> G. A monotone function is differentiable almost everywhere.
> H. The union of a sequence of sets of measure zero is of measure 0.
> I. Countable additivity of Lebesgue measure.
> 
> We can do the reverse mathematics of A-I for the Baire class alpha
> presented functions.
> 
> I DO NOT BELIEVE THAT ANY UNUSUALLY HIGH LOGICAL STRENGTHS ARISE FROM
> SUCH A STUDY.

That may well be true.  But the representations *massively* change the logical strength of some of the items A-I.  

For instance, the following needs Kleene’s (\exists^3) -and hence full SOA- for a proof in terms of comprehension:

  “A function of bounded variation on [0,1] has a point of continuity”  

(This is a fragment of F)

“ A function of bounded variation from R to Q cannot be a bijection”

(This is a fragment of C)

These results are either in [1-4] or the papers are available in request.  

Best,

Sam

References

[1] Sam Sanders, Representations and the Foundations of Mathematics, to appear in NDJFL, arxiv: https://arxiv.org/abs/1910.07913

[2] Dag Normann and Sam Sanders, On robust theorems due to Bolzano, Weierstrass, and Cantor in Reverse Mathematics, Submitted, https://arxiv.org/abs/2102.04787

[3] ___, Betwixt Turing and Kleene, Submitted, arxiv: https://arxiv.org/abs/2109.01352

[4] ___, On the uncountability of R, Submitted, arxiv:  https://arxiv.org/abs/2007.07560