The English language uses the modifier “-ish” for “sort of”. A “sort of yellow” object is called “yellow-ish”. This post describes a class of third-order objects that are “sort of second-order”, i.e. second-order-ish.
First of all, fix a function on the reals that is continuous everywhere and a real
. A moment of thought reveals that
can be approximated ‘by definition’ using only
for rational
. Thus, while
is a third-order object, it has a second-order/countable description;
is not second-order but second-order-ish.
The previous is nothing new and actually the foundation of how continuous functions are studied in second-order arithmetic, (Turing) computability theory, and Reverse Mathematics (see e.g. II.6.1. in Simpson’s excellent SOSOSA). An enterprising mind will of course inquire about discontinuous function classes that are second-order-ish, i.e. for which the definition contains an approximation device that allows us to (uniformly) approximate using nothing more than
for rational
.
As it turns out, there are many (even large) function classes that are second-order-ish, as follows:
cadlag, normalised bounded variation, quasi-continuous, Baire 1, and effectively Baire 2.
We note that there are non-measurable quasi-continuous functions and
non-Borel and measurable quasi-continuous functions. A function is effectively Baire 2 in case it is the pointwise limit of a double sequence of continuous functions, i.e. essentially the second-order coding of Baire 2 functions.
There are of course many function classes that are not second-order-ish, sometimes even small classes that are classically included in second-order-ish function classes, as follows:
bounded variation (BV), regulated, semi-continuous, cliquish, and Baire 2.
These are well-known function classes often going back 100 years or more, not some logical construct we ourselves came up with. You may even remember them from undergrad calculus.
My experience is that second-order-ish function classes can be studied using nothing more than second-order comprehension (in a third-order language); perhaps one can even code these classes in a reasonably faithful way. Non-second-order-ish functions cannot be studied in this way (or coded), i.e. one needs ‘truly’ third-order axioms to study them. Unfortunately, the class BV is included in Baire 1, i.e. this inclusion cannot be proved using second-order comprehension.
What is also interesting is that e.g. quasi-continuity and cliquishness are very close, mathematically speaking, but rather different logically. That is, the mathematical hierarchy and logical hierarchy seem orthogonal. I will make this more concrete in a follow-up posting.
Finally, here is a strong statement: the above shows that the distinction between 2nd and 3rd order objects is not as ‘written in stone’ or important as people may believe; the distinction between 1st and 2nd order is written in stone and important, but inferring anything from that one data point about higher types is… (fill in your own expletive).
Hi Sam, at the danger of taking you too literally: why do you restrict “second-order-ish” to only functions that can be determined only by their values at rational inputs, but not, say, algebraic or computable inputs? (FWIW, I have no good examples of interesting such function classes). You said “non-second-order-ish functions…need ‘truly’ third order axioms [to be studied]”, but this seems an overcommitment for the given notion of “second-order-ish”.
Dear Anupam,
that is a good point: one should be allowed to replace the rationals in ‘second-order-ish’ by any “nice” countable dense subset, akin to what “separable” means in reverse math.
Your examples are all good ones. There may well be function classes that need those instead of the rationals.
Best,
Sam