We study the logical and computational properties of basic theorems of uncountable mathematics, including the Cousin and Lindelöf lemma published in 1895 and 1903. Historically, these lemmas were among the first formulations of open-cover compactness and the Lindelöf property, respectively. These notions are of great conceptual importance: the former is commonly viewed as a way of treating uncountable sets like e.g. [Formula: see text] as “almost finite”, while the latter allows one to treat uncountable sets like e.g. [Formula: see text] (...) as “almost countable”. This reduction of the uncountable to the finite/countable turns out to have a considerable logical and computational cost: we show that the aforementioned lemmas, and many related theorems, are extremely hard to prove, while the associated sub-covers are extremely hard to compute. Indeed, in terms of the standard scale (based on comprehension axioms), a proof of these lemmas requires at least the full extent of second-order arithmetic, a system originating from Hilbert–Bernays’ Grundlagen der Mathematik. This observation has far-reaching implications for the Grundlagen’s spiritual successor, the program of Reverse Mathematics, and the associated Gödel hierarchy. We also show that the Cousin lemma is essential for the development of the gauge integral, a generalization of the Lebesgue and improper Riemann integrals that also uniquely provides a direct formalization of Feynman’s path integral. (shrink)

We investigate the connections between computability theory and Nonstandard Analysis. In particular, we investigate the two following topics and show that they are intimately related. A basic property of Cantor space$2^ $ is Heine–Borel compactness: for any open covering of $2^ $, there is a finite subcovering. A natural question is: How hard is it to compute such a finite subcovering? We make this precise by analysing the complexity of so-called fan functionals that given any $G:2^ \to $, output a (...) finite sequence $\langle f_0, \ldots,f_n \rangle $ in $2^ $ such that the neighbourhoods defined from $\overline {f_i } G\left$ for $i \le n$ form a covering of $2^ $. A basic property of Cantor space in Nonstandard Analysis is Abraham Robinson’s nonstandard compactness, i.e., that every binary sequence is “infinitely close” to a standard binary sequence. We analyse the strength of this nonstandard compactness property of Cantor space, compared to the other axioms of Nonstandard Analysis and usual mathematics.Our study of yields exotic objects in computability theory, while leads to surprising results in Reverse Mathematics. We stress that and are highly intertwined, i.e., our study is holistic in nature in that results in computability theory yield results in Nonstandard Analysis and vice versa. (shrink)

We study the logical and computational properties of basic theorems of uncountable mathematics, in particular Pincherle's theorem, published in 1882. This theorem states that a locally bounded function is bounded on certain domains, i.e. one of the first ‘local-to-global’ principles. It is well-known that such principles in analysis are intimately connected to (open-cover) compactness, but we nonetheless exhibit fundamental differences between compactness and Pincherle's theorem. For instance, the main question of Reverse Mathematics, namely which set existence axioms are necessary to (...) prove Pincherle's theorem, does not have an unique or unambiguous answer, in contrast to compactness. We establish similar differences for the computational properties of compactness and Pincherle's theorem. We establish the same differences for other local-to-global principles, even going back to Weierstrass. We also greatly sharpen the known computational power of compactness, for the most shared with Pincherle's theorem however. Finally, countable choice plays an important role in the previous, we therefore study this axiom together with the intimately related Lindelöf lemma. (shrink)

Cantor’s first set theory paper (1874) establishes the uncountability of ${\mathbb R}$. We study this most basic mathematical fact formulated in the language of higher-order arithmetic. In particular, we investigate the logical and computational properties of ${\mathsf {NIN}}$ (resp. ${\mathsf {NBI}}$ ), i.e., the third-order statement there is no injection resp. bijection from $[0,1]$ to ${\mathbb N}$. Working in Kohlenbach’s higher-order Reverse Mathematics, we show that ${\mathsf {NIN}}$ and ${\mathsf {NBI}}$ are hard to prove in terms of (conventional) comprehension axioms, (...) while many basic theorems, like Arzelà’s convergence theorem for the Riemann integral (1885), are shown to imply ${\mathsf {NIN}}$ and/or ${\mathsf {NBI}}$. Working in Kleene’s higher-order computability theory based on S1–S9, we show that the following fourth-order process based on ${\mathsf {NIN}}$ is similarly hard to compute: for a given $[0,1]\rightarrow {\mathbb N}$ -function, find reals in the unit interval that map to the same natural number. (shrink)

Coherence-spaces and domains with totality are used to give interpretations of inductively defined types. A category of coherence spaces with totality is defined and the closure of positive inductive type constructors is analysed within this category. Type streams are introduced as a generalisation of types defined by strictly positive inductive definition. A semantical analysis of type streams with continuous recursion theorems is established. A hierarchy of domains with totality defined by positive induction is defined, and density for a sub-hierarchy is (...) proved. (shrink)

The aim of Reverse Mathematics (RM for short) is to find the minimal axioms needed to prove a given theorem of ordinary mathematics. These minimal axioms are almost always equivalent to the theorem, working over the base theory of RM, a weak system of computable mathematics. The Big Five phenomenon of RM is the observation that a large number of theorems from ordinary mathematics are either provable in the base theory or equivalent to one of only four systems; these five (...) systems together are called the ‘Big Five’. The aim of this paper is to greatly extend the Big Five phenomenon as follows: there are two supposedly fundamentally different approaches to RM where the main difference is whether the language is restricted to second-order objects or if one allows third-order objects. In this paper, we unite these two strands of RM by establishing numerous equivalences involving the second-order Big Five systems on one hand, and well-known third-order theorems from analysis about (possibly) discontinuous functions on the other hand. We both study relatively tame notions, like cadlag or Baire 1, and potentially wild ones, like quasi-continuity. We also show that slight generalizations and variations of the aforementioned third-order theorems fall far outside of the Big Five. (shrink)

We review some of the history of the computability theory of functionals of higher types, and we will demonstrate how contributions from logic and theoretical computer science have shaped this still active subject.

We show that to every recursive total continuous functional $\Phi$ there is a PCF-definable representative $\Psi$ of $\Phi$ in the hierarchy of partial continuous functionals, where PCF is Plotkin's programming language for computable functionals. PCF-definable is equivalent to Kleene's S1-S9-computable over the partial continuous functionals.

We use the theory of domains with totality to construct some logics generalizing ω-logic and β-logic and we prove a completenes theorem for these logics. The key application is E-logic, the logic related to the functional 3E. We prove a compactness theorem for sets of sentences semicomputable in 3E.

We prove that the hierarchy of hereditarily effective typestreams, that are effective models of inductivly defined types, has the length of the first recursivly inaccessible ordinal.

We give a characterisation of an extension of the Kleene-Kreisel continuous functionals to objects of transfinite types using limit spaces of transfinite types.

Reverse Mathematics (RM hereafter) is a program in the foundations of mathematics where the aim is to identify theminimalaxioms needed to prove a given theorem from ordinary, i.e., non-set theoretic, mathematics. This program has unveiled surprising regularities: the minimal axioms are very oftenequivalentto the theorem over thebase theory, a weak system of ‘computable mathematics’, while most theorems are either provable in this base theory, or equivalent to one of onlyfourlogical systems. The latter plus the base theory are called the ‘Big (...) Five’ and the associated equivalences arerobustfollowing Montalbán, i.e., stable under small variations of the theorems at hand. Working in Kohlenbach’shigher-orderRM, we obtain two new and long series of equivalences based on theorems due to Bolzano, Weierstrass, Jordan, and Cantor; these equivalences are extremely robust and have no counterpart among the Big Five systems. Thus, higher-order RM is much richer than its second-order cousin, boasting at least two extra ‘Big’ systems. (shrink)

We show how Kreisel's representation theorem for sets in the analytical hierarchy can be generalized to sets defined by positive induction and use this to estimate the complexity of constructions in the theory of domains with totality.

We prove that the Kleene schemes for primitive recursion relative to the μ-operator, relativized to some nondeterministic objects, have the same power to express total functionals when interpreted over the partial continuous functionals and over the Kleene-Kreisel continuous functionals. Relating the former interpretation to Niggl's ℳω we prove Nigg's conjecture that ℳω is strictly weaker than Plotkin's PCF + PA.

We show that the length of a hierarchy of domains with totality, based on the standard domain for the natural numbers \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} ${\Bbb N}$\end{document} and closed under dependent products of continuously parameterised families of domains will be the first ordinal not recursive in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $^3E$\end{document} and any real. As a part of the proof we show that the domains of the hierarchy share (...) important properties with the types of continuous functionals. The main result can also be viewed as a representation theorem for recursion in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $^3E$\end{document}. (shrink)