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$

2 Answers 2

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$
10
  • $\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$ Commented Oct 5, 2015 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$ Commented Oct 5, 2015 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$ Commented Oct 5, 2015 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$ Commented Oct 5, 2015 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$ Commented Oct 5, 2015 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
  • 1
    $\begingroup$ This is a great point, and highlights the need to be precise when one talks about "adding sets." $\endgroup$ Commented Oct 8, 2015 at 17:30

You must log in to answer this question.

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