Affiliations: [a] Department of Mathematics, University of Wisconsin, 480 Lincoln Drive, 213 Van Vleck Hall, Madison, WI 53706, USA | [b] Hyperimmune Books, 620 Morning Creek Ln, Suwanee, GA 30024, USA | [c] Google, 1600 Amphitheatre Pkwy, Mountain View, CA 94043, USA | [d] Proof School, 515 Highland Ave., San Mateo, CA 94401, USA
Abstract: We study a class of operators on Turing degrees arising naturally from ultrafilters. Suppose U is a nonprincipal ultrafilter on ω. We can then view a sequence of sets A=(Ai)i∈ω as an “approximation” of a set B produced by amalgamating the Ai via U: we set limU(A)={x:{i:x∈Ai}∈U}. This can be extended to the Turing degrees, by defining δU(a)={limU(A):A=(Ai)i∈ω∈a}. The δU – which we call “ultrafilter jumps” – resemble classical limit computability in certain ways. In particular, δU(a) is always a Turing ideal containing Δ20(a). However, they are also closely tied to Scott sets: δU(a) is always a Scott set containing a′. (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 S is a countable Scott set containing a′, then there is some ultrafilter U with δU(a)=S. We then turn to the problem of controlling the action of an ultrafilter jump δU 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 U↦δU; 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.
Keywords: Ultrafilters, limit computability, scott ideal
DOI: 10.3233/COM-170176
Journal: Computability, vol. 12, no. 2, pp. 101-115, 2023
