Return to Answer

so that (n,j,k) ∈ Q iff (j,k) ∈ S¹_n. If the foregoing is free of errors, this answers my original question.

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

so that (n,j,k) ∈ Q iff (j,k) ∈ S¹_n. If the foregoing is free of errors, this answers my original question.

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) Δ¹₁ sets coincide with the Borel sets. Since the arithmetical hierarchy resembles the Borel hierarchy, one might expect that the relationship between Δ¹₁ and arithmetical resembles that between Δ¹₁ and Borel, enough perhaps that Δ¹₁ and arithmetical would coincide. It is well known that this expectation 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

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

is Σ¹₁ 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 Δ¹₁. Now for p,n > 0 define

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. But this suggestion is false, since Q is Δ¹₁ but not arithmetical. If it were arithmetical, it would be Σ⁰_n for some n. Taking any Σ⁰_n+1 set P ⊆ ω, there is some j such that for all k

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