Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Recursive sets as delta^0_1 in arithmetic hierarchy.

  1. Apr 30, 2015 #1
    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?
  2. jcsd
  3. Apr 30, 2015 #2
    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?
  4. Apr 30, 2015 #3


    User Avatar
    Science Advisor
    Gold Member

    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.
  5. Apr 30, 2015 #4
    Ah, yes, that makes sense. Thanks, TeethWhitener. May I blush now?
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Recursive sets as delta^0_1 in arithmetic hierarchy.
  1. Transfinite recursion (Replies: 5)