What is the Turing degree of Truth?

308 Views Asked by At

First of all by Truth I mean the set $T$ of the Gôdel numbers of the true formulas of first order arithmetic.

First order arithmetic is not decidable and $T$ is not decidable, additionally the undefinability theorem says that $T$ can not be expressed in first order logic, so $T$ does not belong to the arithmetical hierarchy and his Turing degree is at least $\omega$.

What is then the Turing degree of $T$?

Is there a good textbook that somebody can suggest where this kind of subjects are explained thoroughly?

1

There are 1 best solutions below

0
On BEST ANSWER

$T$ does not belong to the arithmetical hierarchy and his Turing degree is at least $\omega$.

A couple quick comments:

  • I assume "$\omega$" should be "$0^{(\omega)}$" - in which case that's correct - since $\omega$ isn't a Turing degree.

  • More substantively, there's a serious issue in your reasoning. You're right that $T$ can't be arithmetic. However, that is not sufficient to conclude that $T\ge_T0^{(\omega)}$: there are Turing degrees incomparable with $0^{(\omega)}$ (and hence not arithmetic or $\ge_T0^{(\omega)}$), and even Turing degrees above every arithmetic set which are incomparable with $0^{(\omega)}$ (this second fact is an instance of the more general exact pair theorem).

To show that $T\ge_T0^{(\omega)}$, you need to argue that given $\langle a,b\rangle\in\mathbb{N}^2$ you can find - computably - a sentence $\varphi$ which is true iff $b\in 0^{(a)}$. You can do that via Kleene's $T$-predicate. Conversely, to show $0^{(\omega)}\ge_TT$ you just show that uniformly the $\Sigma_n$-theory of $\mathbb{N}$ has Turing degree $0^{(n)}$. Soare's book is a good source on this material.