Skip to main content
3 of 3
Commonmark migration

The answer to your question is positive.

Note that the sets $S_n$ that you define can be identified with the set $TA_n$ of Gödel numbers of all first order $\Sigma_n$ sentences true in the structure $(\omega, +, \cdot)$. Let $TA$ (true arithmetic) be the set of Gödel numbers of all first order sentences true in the structure $(\omega, +, \cdot)$.

$TA$ is not only hyperarithmetic, but it is an arithmetic singleton (this is sometimes rephrased as "$TA$ is implicitly definable"). This means there is first order formula $\phi(X)$, formulated in the arithmetical vocabulary augmented with a new unary predciate $X$ such that:

For all subsets $X$ of $\omega$, $(\omega, +, \cdot, X)$ satisfies $\phi(X)$ iff $X=TA$.

The implicit definability of $TA$ is attributed to Hilbert, Bernays, Kuznecov, and Trahtenbrot in Roger's Theory of Effective Functions and Effective Computability (p.344. Thm XII; see also p.381, Thm XI, where $TA$ is referred to as $V$).

It is easy to see that every arithmetic singleton is hyperarithmetic, but the converse is false. For example, there is a hyperarithmetic set that is arithmetically generic; and of course no arithmetically generic set can be an arithmetic singleton.

For more more detail on the above paragraph, as well as an exposition of implicit definability of $TA$, see the text Computability and Logic, by Boolos, Jeffrey, and Burgess.

Ali Enayat
  • 17.7k
  • 2
  • 63
  • 105