Limit computability and ultrafilters
Uri Andrews, Mingzhong Cai, Mingzhong Cai, David Diamondstone, David Diamondstone, Noah Schweber, Noah Schweber · Computability · 2023
We study a class of operators on Turing degrees arising naturally from ultrafilters. Suppose [Formula: see text] is a nonprincipal ultrafilter on ω. We can then view a sequence of sets [Formula: see text] as an “approximation” of a set B produced by amalgamating the [Formula: see text] via [Formula: see text]: we set [Formula: see text]. This can be extended to the Turing degrees, by defining [Formula: see text]. The [Formula: see text] – which we call “ultrafilter jumps” – resemble classical limit computability in certain ways. In particular, [Formula: see text] is always a Turing ideal containing [Formula: see text]. However, they are also closely tied to Scott sets: [Formula: see text] is always a Scott set containing [Formula: see text]. (This yields an alternate proof of the standard result in reverse mathematics that Weak Konig’s Lemma is strictly weaker than arithmetic comprehension.) Our main result is that the converse also holds: if [Formula: see text] is a countable Scott set containing [Formula: see text], then there is some ultrafilter [Formula: see text] with [Formula: see text]. We then turn to the problem of controlling the action of an ultrafilter jump [Formula: see text] on two degrees simultaneously, and for example show that there are nontrivial degrees which are “low” for some ultrafilter jump. Finally, we study the structure on the set of ultrafilters arising from the construction [Formula: see text]; in particular, we introduce a natural preordering on this set and show that it is connected with the classical Rudin–Keisler ordering of ultrafilters. We end by presenting two directions for further research.