There is a (lightface) Σ^{0}_{1} set A ⊆ ω such that for each p > 0 the Σ^{0}_{1} set T^{p} ⊆ ω^{p} given by

T^{p}( j,x_{1},…,x_{p} ) iff ∃t[ ⟨ j,⟨ x_{1},…,x_{p},t ⟩,1 ⟩ ∈ A ]

*parametrizes* the Σ^{0}_{1} subsets of ω^{p}, in the sense that X ⊆ ω^{p} is Σ^{0}_{1} iff for some j, X is the j-section

{ (x_{1},…,x_{p}) : T^{p}( j,x_{1},…,x_{p} ) }

of T^{p}. The set A is obtained by formalizing Kleene's notion of recursive derivation. (For details, see p. 127 of Moschovakis's *Descriptive Set Theory*, Second Edition. Any odd notation I use below is from that book; for instance, the asterisk will denote concatenation.)

We use A to define, for each pair p,n > 0, a set S^{p}_{n} ⊆ ω^{p+1} that parametrizes the Σ^{0}_{n} subsets of ω^{p}. It will be useful to write φ(α) as shorthand for the conjunction of this

∀j ∀y [ ∃i (α(i) = ⟨1,j,y⟩) ↔ (Seq(y) ∧ ∃t (⟨j,y*⟨t⟩,1 ∈ A)) ]

with this

∀j ∀y ∀m>0 [ ∃i (α(i) = ⟨m+1,j,y⟩) ↔ (Seq(y) ∧ ∃t ¬∃h (α(h) = ⟨m,j,y*⟨t⟩⟩)) ].

Here α ranges over ^{ω}ω and the Roman letters range over ω. Maintaining this convention, write ψ(α,n,j,y) for

∃m [ n = m+1 ∧ ∃i (α(i) = ⟨m+1,j,y⟩) ].

Notice that φ(α) ∧ ψ(α,n,j,y) defines an arithmetical subset of ^{ω}ω × ω^{3}. Hence the set H ⊆ ω^{3} given by

H(n,j,k) iff ∃α (φ(α) ∧ ψ(α,n,j,y))

is Σ^{1}_{1} since that pointclass is closed under projection along ^{ω}ω. Moreover, induction on n reveals that

∃α (φ(α) ∧ ψ(α,n,j,y))

is equivalent to

∀α (φ(α) → ψ(α,n,j,y))

so that H is in fact Δ^{1}_{1}. Now for p,n > 0 define

S^{p}_{n} = { (j,x_{1},…,x_{p}) : H(n,j,⟨x_{1},…,x_{p}⟩) }.

By induction on n, for each p the set S^{p}_{n} parametrizes the Σ^{0}_{n} subsets of ω^{p}. For the base, use the first conjunct of φ(α) to show that S^{p}_{1} = T^{p} for each p. For the inductive step, use the inductive hypothesis and the second conjunct of φ(α).

Finally, let Q ⊆ ω^{3} be the Δ^{1}_{1} set given by

Q(n,j,k) iff H(n,j,⟨k⟩)

so that (n,j,k) ∈ Q iff (j,k) ∈ S^{1}_{n}. If the foregoing is free of errors, this answers my original question.

The motivation for that question might have been obvious, but I'll put it down for the record.

*The set Q witnesses that the arithmetical sets are not the "effective analog" of the Borel sets.*

A classical result of Suslin is that the (boldface) **Δ**^{1}_{1} sets coincide with the Borel sets. Since the arithmetical hierarchy resembles the Borel hierarchy, one might expect that the relationship between Δ^{1}_{1} and arithmetical resembles that between **Δ**^{1}_{1} and Borel, enough perhaps that Δ^{1}_{1} and arithmetical would coincide. It is well known that this expectation is false, and indeed the Δ^{1}_{1} set Q witnesses this. For if Q were arithmetical, it would be Σ^{0}_{n} for some n. Taking any Σ^{0}_{n+1} set P ⊆ ω, there is some j such that for all k

P(k) iff (j,k) ∈ S^{1}_{n+1} iff (n+1,j,k) ∈ Q.

Since Q is Σ^{0}_{n} by hypothesis, so is P. But then, since P was arbitrary, every Σ^{0}_{n+1} subset of ω is in fact Σ^{0}_{n}, contradicting the theorem that the arithmetical hierarchy is proper.