4
$\begingroup$

$RCA_0$ has $\Delta_0$-comprehension and $\Sigma_1$ induction. Let $X\Sigma_{n}$ be $RCA_0$ plus $\Sigma_n$-induction and let $X\Sigma_{\omega}$-induction be $RCA_0$ plus the full induction schema.

Does any of the systems $X\Sigma_{\delta}$ for $\delta\in\omega + 1$ prove the existence of sets that are not proved by $\Delta_0$-comprehension, and if so to what level of comprehension do such sets belong?

$\endgroup$
9
$\begingroup$

One answer is trivially "Yes" - fix some first-order sentence $\varphi$ which is provable from $X\Sigma_n$ but not $RCA_0$ alone and consider the formula $$\psi(x)\equiv (\varphi \vee \neg(x\in 0'))$$ (where "$x\in 0'$" is shorthand for the standard $\Sigma^0_1$ formula defining the Halting Problem). Then $RCA_0$ does not prove comprehension for $\psi$, but $X\Sigma_n$ does. Moreover, by choosing $\varphi$ to be a true $\Pi^0_1$ sentence, we can have $\psi$ be $\Pi^0_1$, so this gives examples as low in the arithmetic hierarchy as possible.

I suspect this is not what you mean. The problem is, it's not clear how to interpret your question. The $\omega$-models of $RCA_0$ and of $X\Sigma_n$ are of course the same, so there are no "true" sets of natural numbers whose existence requires induction.

Maybe you can clarify what you are asking?


EDIT: Another response which you might find more satisfactory:

Actually, induction axioms should be thought of as anticomprehension axioms - they show that definable cuts can't exist!

One instance of this is:

Let $M=(\omega_M, \mathbb{R}_M)$ be a model of $RCA_0$ such that, for some $\mathbb{R}'\supseteq\mathbb{R}_M$, we have $(\omega_M, \mathbb{R}')\models X\Sigma_n$. Then $M\models X\Sigma_n$.

Basically, the only way a model $M$ of $RCA_0$ could fail to be a model of $X\Sigma_n$ is if the first-order part of $M$ has a $\Sigma_n$-definable-from-parameters-in-$\mathbb{R}_M$ cut; but if $(\omega_M, \mathbb{R}')\models X\Sigma_n$ for some larger $\mathbb{R}'$, then this can't happen.

In particular, for any model $\omega_M$ of the first-order part $I\Sigma_n$ of $X\Sigma_n$, the structure $(\omega_M, D)$ - where $D$ is the class of $\Delta^0_1$ subsets of $\omega_M$ - is a model of $X\Sigma_n$. But $(\omega_M, D)$ is also the smallest model of $RCA_0$ with first-order part $\omega_M$!

So adding induction doesn't add sets.

$\endgroup$
  • $\begingroup$ I do not understand your shorthand $x\in 0'$ for "the standard $\Sigma^0_1$ formula" which your allegedly trivial example - that I also do not understand - seems to build upon. $\endgroup$ – Frode Bjørdal Oct 5 '15 at 21:27
  • $\begingroup$ By 0' I mean the halting problem. Basically, I'm using $x\in 0'$ as shorthand for the statement "$\exists s(T(x, x, s))$," where $T$ is Kleene's $T$-predicate. (You can use your favorite sufficiently complicated $\Sigma^0_1$ formula instead, if you prefer.) $\endgroup$ – Noah Schweber Oct 5 '15 at 21:30
  • $\begingroup$ The point is that, depending on whether $\varphi$ holds or not, $\psi$ either defines the halting problem, or the set of all natural numbers. Now, $RCA_0$ certainly can't prove that $\exists Y\forall x (x\in Y\iff \psi(x))$, since then $RCA_0+\neg \varphi$ would have to prove that the halting problem exists. $\endgroup$ – Noah Schweber Oct 5 '15 at 21:32
  • $\begingroup$ So the extra instances of comprehension that you point out that would hold for $X\Sigma_{63}$ would be instances true because $\psi$ for $X\Sigma_{63}$ defines the set of all natural numbers? $\endgroup$ – Frode Bjørdal Oct 5 '15 at 21:50
  • 2
    $\begingroup$ @FrodeBjørdal Yes, your interpretation of my answer is correct. I've edited my answer to (hopefully) be more satisfactory. $\endgroup$ – Noah Schweber Oct 5 '15 at 22:02
6
$\begingroup$

There is at least one way in which adding induction for arithmetical formulas does "add sets" in the context of Reverse Mathematics: induction is sometimes required to show that certain "finite" sets and "finite" sequences actually exist. Of course, full induction holds in all $\omega$-models, so this is only relevant when we look at nonstandard models, where these "finite" sequences will be of nonstandard length.

For example, in $\mathsf{RCA}_0$, we can prove that for each $k \in \mathbb{N}$ the set $k \cap 0'$ exists. This follows from "bounded $\Sigma^0_1$ comprehension", which is provable in $\mathsf{RCA}_0$ even though $\Sigma^0_1$ comprehension is not. Of course, we cannot prove $0'$ itself exists, in $\mathsf{RCA}_0$.

Now, working in $\mathsf{RCA}_0$, I do not see any reason why $k \cap 0''$ must exist for each $k \in \mathbb{N}$. On the other hand, the statement "$(\forall k)[k \cap 0'' \text{ exists}]$" is equivalent over $\mathsf{RCA}_0$ to an arithmetical statement, because we can code $k \cap 0''$ as a finite sequence of length $k$. And that arithmetical statement is provable in $\mathsf{PA}$ by induction on $k$, using classical logic. So the arithmetical statment is provable in $\mathsf{RCA}$ as well.

$\endgroup$
  • 1
    $\begingroup$ This is a great point, and highlights the need to be precise when one talks about "adding sets." $\endgroup$ – Noah Schweber Oct 8 '15 at 17:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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