2
$\begingroup$

We work in a countable language of finite-order arithmetic, which allows us to quantify over natural numbers, sets of natural numbers, sets of sets of natural numbers, and so on. We measure the complexity of sentences with a generalization of the arithmetical and analytical hierarchies to higher subscripts. We call $\Pi^m_n$ and $\Sigma^m_n$ for $m, n \in \mathbb{N}$ classes of the arithmetical hierarchy.

I'm interested in special classes of the arithmetical hierarchy that are built up as follows.

  1. $\Delta^0_0$ is special.
  2. If every true sentence in $\Pi^m_n$ (resp., $\Sigma^m_n$) follows from (i.e., can be proved from) true sentences belonging to special classes, then $\Pi^m_n$ (resp., $\Sigma^m_n$) is special.
  3. $\Pi^m_n$ is special if and only if $\Sigma^m_n$ is special.
  4. No other classes are special.

As an example, it's easy to see that $\Pi^0_n$ (equivalently, $\Sigma^0_n$) is special for all $n$. $\Delta^0_0$ is special, and all true $\Sigma^0_1$ sentences follow from true sentences belonging to $\Delta^0_0$ (because the latter contains witnesses for all true $\Sigma^0_1$ sentences). Thus, $\Pi^0_1$ is special. We can then similarly deduce that $\Sigma^0_2$ is special and so on.

If I'm understanding a 1961 result of Grzegorczyk, Mostowski, and Ryll-Nardzewski [1] correctly, then all true $\Pi^1_1$ sentences follow from true first-order arithmetic sentences, so $\Pi^1_1$ is special too.

My question is for which $m$ and $n$ is $\Pi^m_n$ special?

[1] "Definability of sets in models of axiomatic theories" (Thanks to Ali Enayat for bringing this paper to my attention in another question of mine.)

$\endgroup$
4
  • 2
    $\begingroup$ I don't have access to the linked article but I don't see a sense in which $\Pi^1_1$ sentences follow from true arithmetic sentences in general. There's a very coarse obstacle here: the true first-order theory of $\mathbb{N}$ has Turing degree ${\bf 0^{(\omega)}}$ but the true $\Pi^1_1$ theory of $\mathbb{N}$ isn't even hyperarithmetic. $\endgroup$ Commented Aug 3, 2021 at 21:08
  • $\begingroup$ I could be misinterpreting what they proved. My understanding is that they proved that every true $\Pi^1_1$ sentence is provable using the $\omega$-rule. I assumed this is equivalent to saying that every true $\Pi^1_1$ sentence follows from true arithmetic sentences, but now I see that I could be wrong in assuming that (although I'm not sure why that would be wrong). If I am wrong (in which case the answer to my question is $m=0$ and any $n$), I'd still be interested in the modified question where we allow the use of the $\omega$-rule in the definition of "follows from" in step 2. $\endgroup$
    – BPP
    Commented Aug 3, 2021 at 21:57
  • $\begingroup$ I mean, before you can be wrong or not you need to specify what notion of "follows from" you have in mind. The computability-theoretic point in my comment above means that any "simple" notion of deduction won't do the trick (e.g. it can't be a proof in the sense of Henkin semantics since the set of Henkin consequences of a ${\bf 0^{(\omega)}}$-computable theory will be ${\bf 0^{(\omega+1)}}$-computable). $\endgroup$ Commented Aug 3, 2021 at 22:03
  • $\begingroup$ I originally meant what you're calling a simple notion of deduction, so I think I was wrong. But deduction with the $\omega$-rule is not simple in your sense, so that question is still non-trivial, right? $\endgroup$
    – BPP
    Commented Aug 3, 2021 at 22:14

1 Answer 1

2
$\begingroup$

Per the comments, we're looking at deduction in some system based on the $\omega$-rule as opposed to standard first-order deduction (or Henkin semantics or etc.). There's a technical issue here - in my experiene the $\omega$-rule is usually formulated for first-order arithmetic sentences, so I'm not sure what it means to deduce a $\Pi^m_n$ or $\Sigma^m_n$ sentence using the $\omega$-rule for $m>0$ (this may be in the linked paper I don't have access to) - but in fact there's a coarse calculation which will apply to any reasonable interpretation I can think of:

Every version of the $\omega$-rule I can think of is $\Pi^1_1$ - roughly, "the $\omega$-consequences of $T$" will always be $\Pi^1_1$ relative to $T$. If (for example) we start with the true $\Pi^1_1$ theory of arithmetic, we won't even get all the true $\Sigma^1_1$ sentences since the true $\Sigma^1_1$ theory of arithmetic isn't itself $\Pi^1_1$ (more broadly, the projective hierarchy doesn't collapse).

Now your notion of specialness gives us only two tools for "climbing up" the syntactic hierarchy: deduction and complementation. In terms of Turing degree this means that we're not going to escape the $\omega$th hyperjump of $\emptyset$, which is a tiny subclass of $\Delta^1_2$.

(This is contra a silly claim I made originally - the point is that "$\Pi^1_1$ in $\Sigma^1_1$" is much weaker than "$\Pi^1_2$," or more concretely that $\mathcal{O}^\mathcal{O}$ is not $\Pi^1_2$ complete. The sense in which applying the $\omega$-rule "adds a $\Pi^1_1$" seems to follow the former pattern if set up in a natural way. That said, I see no sense at all in which we can get outside the analytical hierarchy.)

$\endgroup$
2
  • $\begingroup$ Do you mind explaining how we get that $\Pi^1_2$ is special (given that $\Pi^1_1$ is special)? $\endgroup$
    – BPP
    Commented Aug 3, 2021 at 23:13
  • $\begingroup$ @Ben See my edit (I did screw that up). $\endgroup$ Commented Aug 3, 2021 at 23:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .