- #1
nomadreid
Gold Member
- 1,665
- 203
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.
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.