What is the intuition behind $\Delta_1^0$ sets and $\Delta_1^1$ sets?

Question

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.

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

Answer 2

It's been a while, but let me say a bit about why someone skeptical of second-order quantifiers might still accept $\Delta^1_1$ sets.

The point is that each $\Delta^1_1$ set can be "built up predicatively:" $X$ is $\Delta^1_1$ iff there is some computable well-ordering $\alpha$ and some index for a Turing machine $e$ such that $X=\Phi_e^{\emptyset^{(\alpha)}}$, where $\emptyset^{(\alpha)}$ is the jump hierarchy starting with $\emptyset$ built along $\alpha$. (Note that while the Turing degree of $\emptyset^{(\alpha)}$ depends only on the ordertype of $\alpha$, the specific set $\emptyset^{(\alpha)}$ is highly representation-dependent, and in fact the proof that $\emptyset^{(\alpha)}\equiv_T\emptyset^{(\beta)}$ if $\alpha\cong\beta$ is nontrivial.)

To a predicativist, the jump operation $U\mapsto U'$ and the idea of iterating along an already-built well-ordering are each perfectly acceptable, so each hyperarithmetic set is acceptable. It just so happens that $\Delta^1_1$=hyperarithmetic (and this is nontrivial).

It's worth noting as a tangent that the notions of $\Delta^1_1$ and hyperarithmeticity separate when we look closely enough: e.g. $\Delta^1_1$-$\mathsf{CA_0}$ and $\mathsf{ATR_0}$ are very different systems. The fact that $\mathsf{ATR_0}$ is vastly more significant than $\Delta^1_1$-$\mathsf{CA_0}$ in reverse mathematics reflects the relative "floppiness" of the notion of being $\Delta^1_1$, and to a certain extent one could argue that this reinforces the idea that hyperarithmeticity is the really important notion here.

---

There's also a model-theoretic characterization of $\Delta^1_1$, incidentally, paralleling an earlier characterization of $\Delta^0_1$:

• $X\subseteq\mathbb{N}$ is $\Delta^0_1$ iff there is some formula $\varphi$ in the language of first-order arithmetic such that, for every model $\mathcal{M}\models\mathsf{PA}$, we have $\varphi^\mathcal{M}\cap\mathbb{N}=X$.

• $X\subseteq\mathbb{N}$ is $\Delta^1_1$ iff there is some formula $\varphi$ in the language of second-order arithmetic such that, for every $\omega$-model $\mathcal{M}\models\Delta^1_1$-$\mathsf{CA_0}$, we have $\varphi^\mathcal{M}=X$.

See the introduction to Moschovakis' paper Abstract computability and invariant definability.