For each n, there is a (lightface) Σ0n set Sn ⊆ ω2 that's universal for the Σ0n subsets of ω. Since {n} × Sn is Σ0n, there is a union R of arithmetical sets such that (n, j, k) ∈ R iff (j, k) ∈ Sn. Clearly R is not itself arithmetical, and offhand I don't see why it should be Δ11.


If we define the sets Sn with care, is there a Δ11 set Q ⊆ ω3 such that (n, j, k) ∈ Q iff (j, k) ∈ Sn? 



Code universal arithmetical sets by a hyperarithmetical set?

> 
> 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.


