Recursive sets as delta^0_1 in arithmetic hierarchy.

[nomadreid]

This is an elementary question that I may blush about later, but for now:
given that a recursively enumerable set is a set modeling a Σ⁰₁ sentence, and a recursive set is a recursively enumerable set S whose complement ℕ\S is also recursively enumerable. Fine.

But then, letting x^→ = the vector (x₀, x₁,...x_n)
S would be modeling a sentence of the form
(*) ∃(x^→)F(x^→) where none of the x_i's appear free in F.
However, S is Δ⁰₁, so that it also models some statement of the form
(**) ∀(x^→) G(x^→)

I am not sure how one comes to the conclusion about Δ; I see that
ℕ\S would model a sentence of the form
∃(x^→) ~F(x^→), (where ~ is negation), that is,
~∀(x^→) F(x^→)
(I am not working in an intuitionist setting.)
which doesn't quite make it.
What silly mistake am I making, or what obvious fact am I overlooking?
Thanks.

 

[nomadreid]

While I am on the topic, I find the term "computable" for recursive functions a bit strange, because we use functions in computers, and functions require more than a single quantifier to define. Where's my conceptual blooper?

 

[TeethWhitener]

It's been a long time since I've done this type of stuff, but I'm pretty sure that if a recursively enumerable set S models ∑⁰₁ sentences [of the form ∃xF(x)], then the complement ℕ/S models sentences of the form ~∃xF(x), not ∃x~F(x). In other words, the complement models ∀x~F(x), a ∏⁰₁ sentence. Thus, if the set S and its complement are both recursively enumerable, then S is both ∑⁰₁ and ∏⁰₁; in other words, S is Δ⁰₁.

 

[nomadreid]

Ah, yes, that makes sense. Thanks, TeethWhitener. May I blush now?