Code universal arithmetical sets by a hyperarithmetical set? - MathOverflow

Code universal arithmetical sets by a hyperarithmetical set?

2011-07-23T20:17:47Z

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

If we define the sets S_n with care, is there a Δ¹₁ set Q ⊆ ω³ such that (n, j, k) ∈ Q iff (j, k) ∈ S_n?

Answer by Ali Enayat for Code universal arithmetical sets by a hyperarithmetical set?

2011-07-23T22:04:13Z

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.

Answer by Cole Leahy for Code universal arithmetical sets by a hyperarithmetical set?

2011-07-25T00:44:55Z

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

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

is equivalent to

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

so that 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 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

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.

Answer by Andreas Blass for Code universal arithmetical sets by a hyperarithmetical set?

2011-07-25T12:06:18Z

Perhaps the quickest answer to the original question is that the clause "If we define the sets $S_n$ with care" makes things look worse than they are. If you use any of the standard constructions of the universal $\Sigma^0_n$ sets $S_n$ , then the $Q$ obtained by stacking them next to each other will be hyperarithmetical. Care (of a somewhat perverse sort) would be needed to get $Q$ not to be hyperarithmetical. (Perverse care might consist of coding some non-hyperarithmetical set by putting its $n$-th bit into the $(0,0)$ position of $S_n$ .)