Some observations about third-order functionals: any relationships between them?

109 Views Asked by At

Let $X'$ denote $X \to X$.

Here are some observations about third-order functionals over $\mathbb{N}$:

  • They are the natural home of ordinal notations. In general, $f \in \mathbb{N}'$ can only be iterated finitely many times if the result is to be well-defined. By contrast, $F \in \mathbb{N}''$ can be iterated along ordinal notations $\mathrm{Ord} \subset \mathbb{N}'''$ via diagonalization: we can write $$0Ff = f$$ $$(\alpha+1)Ff = F(\alpha Ff)$$ $$\mathrm{sup} \lambda Ffn = (\lambda n) Ffn$$ where $\lambda : \mathbb{N} \to \mathrm{Ord}$, $\mathrm{sup} : (\mathbb{N} \to \mathrm{Ord}) \to \mathrm{Ord}$. I first saw this in "A short introduction to Ordinal Notations" by Harold Simmons (pp.6-8).

  • They are the first level at which it's meaningful to distinguish between functionals taking arbitrary arguments and those taking only continuous arguments.

  • They seem to be the last level featuring "interesting" functionals not expressible using $\lambda$ calculus and lower-level functionals - at least in practice. See this blog post by Andrej Bauer (15 years old, but I'm not aware of it being outdated).

  • If we also include functionals of type $(\mathbb{N}' \to 2) \to 2$, then these are home to the collections of sets which lack various regularity properties (perfect set property, property of Baire, Lebesgue measurability...) or are counterexamples to various hypotheses (continuum hypothesis, axiom of determinacy...) with the existence of counterexamples to the continuum hypothesis in particular being independent of all known large cardinal axioms.

These observations feel to me like they could be related, but I don't know enough to say how. Could anyone offer some insight?