MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 5 down vote accepted

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.

share|cite|improve this answer
Thanks for your reply, Ali. Lamentably, I didn't mention that I seek a more direct proof that there is a set Q meeting my description. Before posting, I had already skimmed the part of Rogers you mention; I wasn't satisfied with the observation that the codeset of true arithmetic is hyperarithmetical but not arithmetical. This is partly because that observation doesn't immediately yield a Q as I described, and partly because it requires a detour through logic and model theory which, for the sake of purity, I want to avoid. I think (?) I've found a more recursion theoretic proof, posted below. – Cole Leahy Jul 24 '11 at 23:27
@Cole: everything else being equal, my approach to MO answers gravitates towards not* re-inventing the wheel. For many of us, Logic, Model Theory, and Recursion Theory are all parts of the same subject; with all due respect to purity of methods; whose charms I will never deny. – Ali Enayat Jul 25 '11 at 2:33
@Ali: Your approach is sensible. When I spoke of purity, perhaps I was just trying to rationalize having spent time reinventing a wheel. In any case, it was a good exercise for a student like me. – Cole Leahy Jul 25 '11 at 5:09
@Ali: When you said we could "identify" the sets S-n from my original posting with the codeset for Sigma-0-n truths of arithmetic, did you have something special in mind, or were you just observing that both are Sigma-0-n complete with respect to Turing reducibility? – Cole Leahy Jul 25 '11 at 5:20
@Cole: my choice was informed by the fact that the truth set of $\Sigma_n$-sentences of arithmetic is Turing equivalent to $0^{(n)}$. – Ali Enayat Jul 25 '11 at 14:57

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

share|cite|improve this answer
Does this mean that the set R from the original question is indeed hyperarithmetical, and not just Borel? It was obtained by stacking, after all. – Cole Leahy Jul 25 '11 at 14:54
@Cole: I am not sure what you mean by Borel here; all subsets of $\omega$ are Borel if Borel is interpreted in its usual way. – Ali Enayat Jul 25 '11 at 14:59
That was silly of me! I corrected the original posting. Thanks for the tip. – Cole Leahy Jul 25 '11 at 15:10
Indeed, I am doubly silly. Of course the R from the original question is hyperarithmetical; we've shown that there is a hyperarithmetical Q meeting my description, and Q and R are coextensive! Please cut me some slack here, as I'm just learning. And I haven't had coffee today. – Cole Leahy Jul 25 '11 at 15:29

There is a (lightface) Σ01 set A ⊆ ω such that for each p > 0 the Σ01 set Tp ⊆ ωp given by

Tp( j,x1,…,xp ) iff ∃t[ ⟨ j,⟨ x1,…,xp,t ⟩,1 ⟩ ∈ A ]

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

{ (x1,…,xp) : Tp( j,x1,…,xp ) }

of Tp. 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 Spn ⊆ ωp+1 that parametrizes the Σ0n 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 Σ11 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 Δ11. Now for p,n > 0 define

Spn = { (j,x1,…,xp) : H(n,j,⟨x1,…,xp⟩) }.

By induction on n, for each p the set Spn parametrizes the Σ0n subsets of ωp. For the base, use the first conjunct of φ(α) to show that Sp1 = Tp for each p. For the inductive step, use the inductive hypothesis and the second conjunct of φ(α).

Finally, let Q ⊆ ω3 be the Δ11 set given by

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

so that (n,j,k) ∈ Q iff (j,k) ∈ S1n. 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) Δ11 sets coincide with the Borel sets. Since the arithmetical hierarchy resembles the Borel hierarchy, one might expect that the relationship between Δ11 and arithmetical resembles that between Δ11 and Borel, enough perhaps that Δ11 and arithmetical would coincide. It is well known that this expectation is false, and indeed the Δ11 set Q witnesses this. For if Q were arithmetical, it would be Σ0n for some n. Taking any Σ0n+1 set P ⊆ ω, there is some j such that for all k

P(k) iff (j,k) ∈ S1n+1 iff (n+1,j,k) ∈ Q.

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.