Return to Revisions

There is a (lightface) Σ⁰₁ set A ⊆ ω such that for each p > 0 the Σ⁰₁ set T^p ⊆ ω^p given by

T^p( j,x₁,…,x_p ) iff ∃t[ ⟨ j,⟨ x₁,…,x_p,t ⟩,1 ⟩ ∈ A ]

parametrizes the Σ⁰₁ subsets of ω^p, in the sense that X ⊆ ω^p is Σ⁰₁ iff for some j, X is the j-section

{ (x₁,…,x_p) : T^p( j,x₁,…,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 Σ⁰_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 ^ωω × ω³. Hence the set H ⊆ ω³ given by

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

is Σ¹₁ since that pointclass is closed under projection along ^ωω. Moreover, induction on n reveals that the last displayed line is equivalent to

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

Hence H is in fact Δ¹₁. Now for p,n > 0 define

S^p_n = { (j,x₁,…,x_p) : H(n,j,⟨x₁,…,x_p⟩) }.

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

Finally, let Q ⊆ ω³ be the Δ¹₁ set given by

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

so that (n,j,k) ∈ Q iff (j,k) ∈ S¹_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 the failure of the naive "effectivization" of Suslin's classical result that the (boldface) Δ¹₁ sets coincide with the Borel sets.

The naive (and apparently fecund) analogy is that Δ¹₁ is to arithmetical as Δ¹₁ is to Borel. Since the latter two coincide, the analogy suggests the same for the former. It is well known that this suggestion is false, and indeed the Δ¹₁ set Q witnesses this. For if Q were arithmetical, it would be Σ⁰_n for some n. Taking any Σ⁰_n+1 set P ⊆ ω, there is some j such that for all k

P(k) iff (j,k) ∈ S¹_n+1 iff (n+1,j,k) ∈ Q.

Since Q is Σ⁰_n by hypothesis, so is P. But then, since P was arbitrary, every Σ⁰_n+1 subset of ω is in fact Σ⁰_n, contradicting the theorem that the arithmetical hierarchy is proper.