The strength of compactness in Computability Theory and Nonstandard Analysis

Dag Normann, Sam Sanders

Published 2018-01-24Version 1

The authors recently pioneered a connection between Nonstandard Analysis and Computability Theory, resulting in a number of surprising results and even more open questions. We answer some of the latter in this paper, all of which pertain to the two following intimately related topics. (T.1) A basic property of Cantor space $2^{\mathbb{N}}$ is Heine-Borel compactness: Any open cover of $2^{\mathbb{N}}$, has a finite sub-cover. A natural question is: How hard is it to compute such a finite sub-cover? We make this precise by analysing functionals that given $g:2^{\mathbb{N}}\rightarrow \mathbb{N}$, output $\langle f_0 , \dots, f_n\rangle $ in $2^{\mathbb{N}}$ such that the neighbourhoods defined from $\overline{f_i}g(f_i)$ for $i\leq n$ cover $2^{\mathbb{N}}$. The special and weak fan functionals are central objects in this study. (T.2) A basic property of $2^{\mathbb{N}}$ 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 in the spirit of Reverse Mathematics, which turns out to be intimately related to the computational properties of the special and weak fan functionals. We establish the connection between these new fan functionals on one hand, and arithmetical comprehension, transfinite recursion, and the Suslin functional on the other hand. We show that compactness (nonstandard or otherwise) readily brings us to the outer edges of Reverse Mathematics (namely $\Pi_2^1$-CA$_0$), and even into Schweber's higher-order framework (namely $\Sigma_{1}^{2}$-separation).