Is the Turing equivalence relation the orbit equiv. relation of the action of a countable group?

Question

The Turing equivalence relation on $\cal P(\mathbb{N})$ is defined by $A\equiv_T B$ iff $A\leq_T B$ and $B\leq_T A$. This is a countable Borel equivalence relation on the polish space $\cal P(\mathbb{N})$. And as stated, the answer to my question is yes since a theorem by Feldman and Moore says: for any countable Borel equivalence relation $E$ on a standard Borel space $X$, there is a countable group $G$ and a Borel action of $G$ on $X$ such that $E$ is the orbit equivalence relation of the action.

But from where I have looked, the Turing equivalence isn't the orbit e.r. of any countable group that is "found in nature". I was wondering if anything else was known about this, as well as any other instances of equiv. relations that are provably orbit equivalences, but with no known "natural" group doing the acting. It seems like for many important equivalences (like $E_0, E_{\infty}$, hyperfinite e.r's) we do in fact have a natural group that is acting, but perhaps that is the reason why we know so much about them.

Any references or other information would be great, thanks.

Answer 1

These slides of Simon Thomas for the Appalachian Set Theory Seminar 2007 are directly engaged with aspects of this question, particularly the question of which countable Borel equivalence relations arise as free Borel actions of countable groups or are Borel bireducidible with such an equivalence relation. These latter equivalence relations are called essentially free. (See also part I of his talk series "Countable Borel Equivalence Relations", which contains a proof of Feldman-Moore; part II was the link above.)

In particular, Simon Thomas proved that Turing equivalence is not essentially free.

Answer 2

Any countable Borel equivalence relation can arise from a Borel action of the free group on $\omega$ generators, which is a natural enough group. You should probably ask instead whether the action can be natural. Can the action be free, for example, as Joel discusses.

The field of countable Borel equivalence relations has gained a tremendous amount from studying equivalence relations arising from natural group actions. However, for the case of Turing equivalence, viewing this relation as arising from the Borel action of a countable group does not appear to be a helpful way of thinking.

You might be interesting in the following open question (from my thesis). The question essentially asks whether the Turing reductions are the unique way to generate Turing equivalence:

Suppose that $\{\psi_i\}_{i \in \omega}$ is any countable collection of partial Borel functions closed under composition such that $x$ and $y$ are Turing equivalent if and only if there exists an $i$ and a $j$ such that $\psi_i(x) = y$ and $\psi_j(y) = x$. Suppose also that $\{\varphi_i\}_{i \in \omega}$ is an enumeration of the Turing reductions. Then must there be a pointed perfect set $P$ and a function $u: \omega^2 \rightarrow \omega^2$ such that for every pair of Turing reductions $\varphi_i$ and $\varphi_j$, if $x,y \in P$ and $\varphi_i(x) = y$ and $\varphi_j(y) = x$, then $\psi_k(x) = y$ and $\psi_l(y) = x$, where $u(i,j) = (k,l)$?

It is probably optimistic to hope that the answer to the above question is "yes", when we have no idea how to approach this problem. However, beyond the question being nice in and of itself, a positive answer would have a large number of consequences. It would imply Martin's conjecture on Turing invariant functions is true, for example, which in turn would have a lot of consequences for the theory of countable Borel equivalence relations.

A positive answer would also imply any universal countable Borel equivalence relation must be able to witness its universality uniformly, regardless of the way it is generated. A nice implication of this would be that any increasing union of non-universal countable Borel equivalence relations must be non-universal.