Recursive sets as delta^0_1 in arithmetic hierarchy.

In summary, the conversation discusses the properties of recursively enumerable and recursive sets in relation to modeling sentences of the forms ∃xF(x) and ∀x~F(x). It is determined that if a set is both recursively enumerable and its complement is also recursively enumerable, then the set must be Δ01. This is a result of the complement modeling a ∏01 sentence instead of the expected ∑01 sentence. The conversation also briefly touches on the term "computable" for recursive functions and its relation to single quantifiers.
  • #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.
 
Physics news on Phys.org
  • #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?
 
  • #3
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.
 
  • Like
Likes nomadreid
  • #4
Ah, yes, that makes sense. Thanks, TeethWhitener. May I blush now?
 

1. What is the definition of recursive sets in the arithmetic hierarchy?

Recursive sets are sets of natural numbers that can be defined by a computable function. In the arithmetic hierarchy, these sets are considered to be at the lowest level, or delta^0_1, which means they can be defined by a single quantifier-free formula.

2. How are recursive sets related to computability?

Recursive sets are closely related to the concept of computability, as they can be defined by computable functions. This means that there exists an algorithm that can determine whether a given number belongs to the set or not.

3. Are all recursive sets delta^0_1 in the arithmetic hierarchy?

No, not all recursive sets are delta^0_1 in the arithmetic hierarchy. Some recursive sets may be at higher levels in the hierarchy, such as delta^0_2 or delta^0_3, depending on the complexity of the formula used to define them.

4. What is the significance of recursive sets being at the lowest level of the arithmetic hierarchy?

Being at the lowest level of the arithmetic hierarchy, delta^0_1, means that recursive sets can be defined in a simple and straightforward manner. This makes them useful for studying the foundations of computability theory and understanding the complexity of other sets in the hierarchy.

5. How are recursive sets used in mathematics and computer science?

Recursive sets have various applications in mathematics and computer science, such as in the study of computability, complexity theory, and formal languages. They are also used in the development of algorithms and programming languages, as well as in the analysis of mathematical structures and theories.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
1K
  • Programming and Computer Science
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
6
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
3
Views
895
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
2K
  • Programming and Computer Science
Replies
14
Views
496
  • Set Theory, Logic, Probability, Statistics
Replies
15
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
917
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
4K
Replies
1
Views
828
Back
Top