What is the Turing degree associated with an ultrafilter $U$?

Question

I asked Turing degree of a turing machine with access to an (arbitrary) nonstandard integer, not thinking about the possiblity that this could depend on the model used. The question was not formulated very well, but I did not want to delete it since I got some good answers. Now I will ask the question I originally had in mind.

Let $U$ be a ultrafilter on $\mathbb N$ and $f$ a partial computable function of two arguments, which can either accept or reject its input (or not halt) (I'm using a finite range so that the output is guaranteed to be standard, which should make things slightly simpler). We say that $f$ accepts $n$ with help from $U$ if $\{i \in \mathbb N : f(n,i)\text{ accepts}\} \in U$, and rejects or does not halt likewise (due to the definition of the ultrafilter, exactly one of these possibilities will be true). This can be seen as defining running $f$ in a model defined by a ultrapower of $\mathbb N$ with input $n$ (which is standard) and $H$=$(0,1,2,\dots)$. My question is, what is the turing degree associated with such functions, for a given ultrafilter $U$.

If the ultrafitler $U$ is principal, then its turing degree will just be $0$, so we will mostly consider nonprincipal ultrafilters.

For a nonprincipal ultrafilter $U$ (we will assume all ultrafilters are nonprincipal from this point on), we can construct a function $f(n,i)$ which interprets $n$ as a standard turing machine, and runs this machine for $i$ steps. If the machine halts, it will after a standard number of steps, and so $f$ will accept. If the machine has not halted after $i$ steps, it never will, and so $f$ will reject. $f$ has solved the halting problem for standard turing machines, and so the Turing degree of $U$ is at least $0'$. (Note that if the machine associated with $n$ is one that looks for a contradiction in, say, $ZFC$, $f$ is still guaranteed to give the right answer (according to whether or not $ZFC$ is consistient), even if the length of shortest contradiction is nonstandard in whatever metatheory we are using. That's because the ultraproduct model layers another layer of "nonstandardness" over what the metatheory already has.) We can also note that $U$'s turing degree must be at least $0'$, since it can be used to model an eventually correct machine.

On the other hand, for any set $S \subseteq \mathbb N$, we can construct an ultrafilter $U$ such that, with its help, we can compute $S$. Choose a computable encoding of finite sets of natural numbers.. Now, let $a$ be the set of encodings of subsets of $S$ of the form $S_{<n}$ for some $n$.

If $S$ is finite, then we can compute $S$ easily. Otherwise, $a$ will be infinite. Therefore, there will be some ultrafilter $U$ (assuming that at least one nonstandard ultrafilter exists) such that $a \in U$. Therefore, the function $f(n,i)$ defined as $n \in i$ (according to the encoding), will compute $S$. (To see this, note that for all $n \in S$, $f$ will accept for cofinitely of $i \in a$, and so $f$ will accept. Otherwise, $f$ will reject for all $i \in a$, and so will reject.)

This shows that ultrafilters can have arbitrarily high turing degrees, and in particular not all ultrafilters have the same turing degree.

So, my question is, for a given ultrafilter $U$, how can we determine the turing degree associated with it?

Answer 1

Great question! This is something that Uri Andrews, Mingzhong Cai, David Diamondstone, and I looked at in a recent paper.

First of all, let's note that there's an important undefined notion: the Turing degree of an ultrafilter. Only sets of natural numbers have Turing degrees, and an ultrafilter is a set of sets of natural numbers. So we can't really talk about its Turing degree.

Something we can look at, though, is how it operates on Turing degrees. Given a Turing degree ${\bf d}$, let $\mathcal{U}({\bf d})$ be the set of sets of natural numbers of the form $\{n: \{m: \langle m, n\rangle\in X\}\in\mathcal{U}\}$ for $X\le_T{\bf d}$ (and denote this set $\mathcal{U}(X)$. For instance, your computation of the halting problem from a nonprincipal ultrafilter amounts to showing that $0'=\mathcal{U}(A)$ for a particular computable set $A$ (namely, $A=\{\langle x, e\rangle: \Phi_e(e)[x]\downarrow\})$.

A reasonable measure of the complexity of $\mathcal{U}$, then, is what it does to the computable sets: that is, $\mathcal{U}({\bf d})$. Now, on the face of it $\mathcal{U}({\bf d})$ is just some random collection of sets, and there's no reason for it to have any nice structure. However, it turns out:

Let $\mathcal{U}$ be a nonprincipal ultrafilter. Then for every Turing degree ${\bf d}$, $\mathcal{U}({\bf d})$ is a Scott set containing ${\bf d}$.

Moreover - and I think more germanely to your question - this reverses:

Let $\mathfrak{S}$ be a countable Scott set containing ${\bf d}'$. Then there is an ultrafilter $\mathcal{U}$ such that $\mathcal{U}({\bf d})=\mathfrak{S}$.

So this exactly characterizes the "one-use" computing power of ultrafilters. And this coincides with your definition of "Turing degree" of an ultrafilter (although in fact $\mathcal{U}({\bf 0})$ is never a Turing degree, as long as $\mathcal{U}$ is nonprincipal!).

---

What about multiple uses?

We might want to treat $\mathcal{U}$ as an operator which we can apply repeatedly - i.e. take the $\mathcal{U}$-"limit" of the $\mathcal{U}$-"limit" of a computable set. Then we want to look at $$\mathcal{U}^{\omega}({\bf d})=\mathcal{U}({\bf d})\cup\mathcal{U}(\mathcal{U}({\bf d}))\cup\mathcal{U}(\mathcal{U}(\mathcal{U}({\bf d})))\cup...$$ The characterization above generalizes to show:

Suppose $\mathfrak{S}$ is a countable Scott set, and $\mathfrak{I}$ is a Turing ideal such that the jump of every element of $\mathfrak{I}$ is in $\mathfrak{S}$. Then there is a nonprincipal ultrafilter $\mathcal{U}$ with $\mathcal{U}(\mathfrak{I})=\mathfrak{S}$. Moreover, $\mathcal{U}(\mathfrak{I})$ is always a Scott set containing the jump of each element of $\mathfrak{I}$.

Applying the second half of this, we have:

$\mathcal{U}^\omega({\bf d})$ is an arithmetic ideal (= closed under Turing jump).

And the first half gives us:

Suppose $\mathfrak{A}$ is a countable arithmetic ideal containing ${\bf d}$. Then there is a nonprincipal ultrafilter $\mathcal{U}$ with $\mathcal{U}^\omega({\bf d})=\mathfrak{A}$.

---

The above, I think, address your questions pretty well. But let me give a couple more potentially interesting facts from our paper:

• There is a nonzero degree ${\bf d}$ and a nonprincipal ultrafilter $\mathcal{U}$ with $\mathcal{U}({\bf d})=\mathcal{U}({\bf 0})$. Indeed, for every computably traceable ${\bf d}$, and for every 2-generic ${\bf d}$, there is such a $\mathcal{U}$. So there is a nontrivial "lowness" property.

• When we look at uncountable Turing ideals, the characterizations above break down. Specifically, the direction "if sufficiently closed, then there is an ultrafilter" can be broken: every model $M$ of PD (= projective determinacy) has a forcing extension $M[G]$ and a set of sets of natural numbers $\mathfrak{I}\in M[G]$ such that

  • $(\mathbb{N}, \mathfrak{I}; +,\times, \in)\prec(\mathbb{N}, 2^\mathbb{N}; +, \times, \in)$ (that is, $\mathfrak{I}$ satisfies every reasonable closure property), but

  • no ultrafilter $\mathcal{U}\in M[G]$ has $\mathcal{U}(\mathfrak{I})=\mathfrak{I})$.

• And here's a neat question. There is a natural partial pre-ordering $\trianglelefteq$ on the set of ultrafilters on $\mathbb{N}$, given by $\mathcal{U}\trianglelefteq\mathcal{V}$ iff $\mathcal{U}({\bf d})\subseteq\mathcal{V}({\bf d})$ for all sufficiently large degrees ${\bf d}$. Some basic facts about this are easy to prove (e.g. unsurprisingly it is $\omega_1$-directed), but one rather interesting open question is whether $\trianglelefteq$ coincides with (it is known that it at least is coarser than) the Rudin-Keisler order (and the same relationship/question exists between the version of $\trianglelefteq$ with "sufficiently large" removed, and the effective Rudin-Keisler order).

---

Finally, while Turing degrees don't make sense for ultrafilters, there are other measures of complexity which can apply to ultrafilters on the naturals. A few of these include:

• Constructibility degree.

• $\omega_1$-recursive degree.

• $E$-degree.

• Kleene degree, after interpreting the ultrafilter as a type-2 functional in an appropriate way (e.g. its characteristic function).

I don't know any non-obvious results along these lines (e.g. Grilliot's trick shows that every nonprincipal ultrafilter Kleene-computes the Turing jump functional, and it's easy to show that the converse fails), but they do give you more contexts in which to ask your questions.