Skip to content

The Proof Theory Blog

!(A & B) = !A ⊗ !B

Menu
  • Home
  • About
  • Contribute
  • Resources
Menu

Second-order-ish mathematics I

Posted on August 12, 2023August 12, 2023 by Sam Sanders

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 f on the reals that is continuous everywhere and a real x. A moment of thought reveals that f(x) can be approximated ‘by definition’ using only f(q) for rational q. Thus, while f is a third-order object, it has a second-order/countable description; f 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 f(x) using nothing more than f(q) for rational q.

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 2^{|\mathbb{R}|} non-measurable quasi-continuous functions and 2^{|\mathbb{R}|} 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).

2 thoughts on “Second-order-ish mathematics I”

  1. Anupam Das says:
    September 15, 2023 at 2:53 pm

    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”.

    Reply
  2. Sam Sanders says:
    September 15, 2023 at 5:39 pm

    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

    Reply

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

Meta

  • Register
  • Log in
  • Entries RSS
  • Privacy Policy

Search

© 2023 The Proof Theory Blog | Powered by Minimalist Blog WordPress Theme
The Proof Theory Blog uses cookies, but you can opt-out if you wish. For further information see our privacy policy. Cookie settingsAccept
Privacy & Cookies Policy

Privacy Overview

This website uses cookies to improve your experience while you navigate through the website. Out of these cookies, the cookies that are categorized as necessary are stored on your browser as they are essential for the working of basic functionalities of the website. We also use third-party cookies that help us analyze and understand how you use this website. These cookies will be stored in your browser only with your consent. You also have the option to opt-out of these cookies. But opting out of some of these cookies may have an effect on your browsing experience.
Necessary
Always Enabled
Necessary cookies are absolutely essential for the website to function properly. This category only includes cookies that ensures basic functionalities and security features of the website. These cookies do not store any personal information.
Non-necessary
Any cookies that may not be particularly necessary for the website to function and is used specifically to collect user personal data via analytics, ads, other embedded contents are termed as non-necessary cookies. It is mandatory to procure user consent prior to running these cookies on your website.
SAVE & ACCEPT