The Wikipedia article on Turing degrees states "One general conclusion that can be drawn from the research is that the structure of the Turing degrees is extremely complicated."

They claim this is supported by the fact that "Simpson (1977) showed that the first-order theory of $\mathcal{D}$ [The collection of Turing degrees] in the language $〈 ≤, = 〉$ or $〈 ≤, ′, =〉$ is many-one equivalent to the theory of true second-order arithmetic."

I'm not sure I fully understand what this means or why it indicates that the structure of the Turing degrees is "extremely complicated."

  • $\begingroup$ What about the claim $0' \le a \implies \exists b, a \equiv b'$, do you see a proof ? $\endgroup$ – reuns Apr 16 at 7:16
  • $\begingroup$ @Arthur By itself, that doesn't say much - think about the analogous fact that every countable linear order embeds into $\mathbb{Q}$. But the fact that they all embed as initial segments, though ... $\endgroup$ – Noah Schweber Apr 16 at 16:17
  • $\begingroup$ As a very simplistic answer: the Turing degree of the set of true sentences of second-order arithmetic is very large. So if that degree reduces to the Turing degree of the set of true sentences of $\mathcal{D},\leq $, then the Turing degree of the theory of $\mathcal{D}, \leq$ is also very large. By comparison, the Turing degree of most "simple" structures is computable, or of degree $0^n$ for somewhat small $n$; this is a common consequence of quantifier elimination. . The Turing degree of true first order arithmetic is just $0^{\omega}$. The degree of $\mathcal{D}, \leq$ is far larger. $\endgroup$ – Carl Mummert Apr 17 at 19:05

The first-order theory of a structure $\mathcal{S}$ is just the set of first-order sentences true in $\mathcal{S}$. For example, whether or not a group is abelian can be "read off" the theory of that group by asking whether the theory contains the sentence "$\forall x, y(x*y=y*x)$." Not every property is first-order expressible, but many are.

Now suppose I have a structure where it's very difficult to tell whether it has a given property or not. This is one way in which a structure can be complicated. And this is exactly what Simpson's result says: that the theory of the Turing degrees subsumes all of the theory of natural numbers and sets of natural numbers. That is, there is a computable process for turning a first-order sentence $\varphi$ about the structure $\mathcal{N}_2=(\mathbb{N},\mathcal{P}(\mathbb{N}),+,\times,\in)$ (note: "true second-order sentence about $(\mathbb{N},+,\times)$" is the same as "true first-order sentence about $(\mathbb{N},\mathcal{P}(\mathbb{N}),+,\times,\in)$") into a sentence $\hat{\varphi}$ such that $\varphi$ is true in $\mathcal{N}_2$ iff $\hat{\varphi}$ is true in the Turing degrees. For example, if I had the theory of the Turing degrees "in hand" I would be able to tell immediately whether (say) the Goldbach conjecture is true, since Goldbach is first-order expressible in $\mathcal{N}_2$.

Put a bit more concretely: if I had a group where I needed to solve the Goldbach conjecture to tell if it was abelian, and do similar things to tell if it had other basic group-theoretic properties, I'd say it was pretty complicated. Simpson's result is basically saying that the same thing happens in the Turing degrees: understanding them completely requires that you understand everything there is to know about sets of natural numbers, at least from the first-order perspective.

Another way in which the Turing degrees are complicated, which may be easier to think about at first, is reflected in the lack of homogeneity. While above we thought of complexity in terms of how difficult it is to tell whether the structure in question has a given property or not, we could also look at how homogeneous it is, with the idea that more homogeneity generally means less complexity. For example, the linear order $\mathcal{Q}=(\mathbb{Q},<)$ is very homogeneous: different points in $\mathcal{Q}$ look the same given any $a,b\in\mathbb{Q}$ there is an automorphism of $\mathcal{Q}$ sending $a$ to $b$ (and indeed much more is true).

$\mathcal{D}$ doesn't share this property. Different Turing degrees can look quite different. For example, some Turing degrees are minimal while others aren't; some pairs of incomparable degrees have greatest lower bounds while others don't; some degrees have strong minimal covers while others don't; and so on. Indeed, every countable partial order is (isomorphic to) an initial segment of the Turing degrees, so we get radically different behavior just looking at "downward cones!" Some Turing degrees have infinite but well-ordered downward cones; there are also Turing degrees which set above just an infinite antichain (ok fine, and ${\bf 0}$).

At a "global" level we can say much more: $\vert\mathcal{D}\vert=2^{\aleph_0}$ but it is known by work of Slaman and Woodin that $\mathcal{D}$ has at most countably many automorphisms. So $\mathcal{D}$ is very far from "self-similar." And it is in fact conjectured that $\mathcal{D}$ is rigid (= no nontrivial automorphisms at all), although this seems well out of reach of current technology.

  • $\begingroup$ Your last $\varphi$ is missing a hat... $\endgroup$ – Andrés E. Caicedo Apr 16 at 16:41
  • 1
    $\begingroup$ @AndrésE.Caicedo Decorum restored! $\endgroup$ – Noah Schweber Apr 16 at 16:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.