Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In the context of first-order arithmetic, if $\phi$ is a formula with only bounded quantifiers, then if you put existential quantifiers in front it becomes a $\Sigma_1^0$ formula according to the arithmetical hierarchy, and if you instead put universal quantifiers in front, it it becomes a $\Pi_1^0$ formula. A $\Delta_1^0$ set is a set defined by both a $\Sigma_1^0$ formula and a $\Pi_1^0$ formula.

Similarly, in the context of second-order arithmetic, if $\phi$ is a formula with only first-order quantifiers, then if you put second-order existential quantifiers in front it becomes a $\Sigma_1^1$ formula according to the analytical hierarchy, and if you instead put second-order universal quantifiers in front, it it becomes a $\Pi_1^1$ formula. A $\Delta_1^1$ set, also known as a hyperarithmetical set, is a set defined by both a $\Sigma_1^1$ formula and a $\Pi_1^1$ formula.

My question is, what is the intuition behind the definitions of $\Delta_1^0$ sets and $\Delta_1^1$ sets? Who cares if a set is defined by two formulas with different types of quantifiers? I'm specifically interested in the philosophical significance of these notions. For instance, why is it that an Edward Nelson-like strict finitist who only accepts induction on formulas with bounded quantifiers might be somewhat more open to accept induction for $\Delta_1^0$ sets? Similarly, how is it that Feferman and Schutte showed that a Weyl-style predicativist who is reluctant to accept comprehension for formulas with second-order quantifiers would accept comprehension for $\Delta_1^1$ sets?

Any help would be greatly appreciated.

Thank You in Advance.

share|improve this question
add comment

1 Answer 1

The $\Sigma_1^0$ sets of numbers are exactly the recursively enumerable sets. The $\Pi_1^0$ sets are those with recursively enumerable complements. So the sets which are $\Delta_1^0$, ie. are both $\Sigma_1^0$ and $\Pi_1^0$, are those which are r.e. and have r.e. complements -- i.e. are recursive. That is why we care that a set can be defined by these two formulas with different types of quantifiers!

Going from the arithmetical to the analytical hierarchy, you might find the following Wikipedia article at least helps with the question about the interest of $\Delta_1^1$ sets: http://en.wikipedia.org/wiki/Hyperarithmetical_theory

share|improve this answer
    
Thanks, I wasn't aware that the $\Sigma_0^1$ sets are the recursively enumerable sets, but now that you've told me, it seems fairly obvious (it's easy to make Turing machine that enumerates all the $\Sigma_0^1$ truths). So now the question becomes, why would a Parson/Nelson-style predicativist who's reluctant to accept induction for recursively enumerable sets be more willing to accept induction for recursive sets? –  Keshav Srinivasan Jan 19 at 16:13
    
Also, do you have any idea why someone who's reluctant to accept comprehension for formulas with second-order quantifiers would accept comprehension for $\Delta_1^1$ sets? –  Keshav Srinivasan Jan 19 at 16:29
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.