# Recursive sets as delta^0_1 in arithmetic hierarchy.

1. Apr 30, 2015

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 Σ01 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 (x0, x1,...xn)
S would be modeling a sentence of the form
(*) ∃(x)F(x) where none of the xi's appear free in F.
However, S is Δ01, 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.

2. Apr 30, 2015

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?

3. Apr 30, 2015

### 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 ∑01 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 ∏01 sentence. Thus, if the set S and its complement are both recursively enumerable, then S is both ∑01 and ∏01; in other words, S is Δ01.

4. Apr 30, 2015