This is an elementary question that I may blush about later, but for now:(adsbygoogle = window.adsbygoogle || []).push({});

given that a recursively enumerable set is a set modeling a Σ^{0}_{1}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_{0}, x_{1},...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 Δ^{0}_{1}, 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.

**Physics Forums - The Fusion of Science and Community**

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.

Loading...

Similar Threads for Recursive sets delta^0_1 |
---|

A About the “Axiom of Dependent Choice” |

I The difference between a family of sets and an indexed family of sets |

I Definition of surjection |

I Countability of ℚ |

I Recursive Ordinals and Creativity |

**Physics Forums - The Fusion of Science and Community**