4
$\begingroup$

For a nonstandard model of enough arithmetic - say, $\mathcal{N}\models I\Sigma_1$ - we can define the set of halting times of standard machines relative to $\mathcal{N}$: $$SH(\mathcal{N})=\{n\in\mathcal{N}:\exists e\in\omega(\mathcal{N}\models \text{$\Phi_e(0)$ halts in exactly $n$ steps})\}.$$ Here $\omega$ denotes standard $\omega$, so $SH(\mathcal{N})$ is not in general definable in $\mathcal{N}$. Note that $SH(\mathcal{N})$ is a subsemiring of $\mathcal{N}$, so we can consider it as a possible setting for arithmetic.

Sadly, $SH(\mathcal{N})$ is not guaranteed to be a model of $I\Sigma_1$, regardless of how much induction we have in $\mathcal{N}$. To see why: Suppose we have a $\Sigma_0$-formula $\varphi$ such that $SH(\mathcal{N})\models \exists x\varphi(x).$ Then certainly $\mathcal{N}\models\exists x\varphi(x)$, so there is a least $m\in\mathcal{N}$ such that $\mathcal{N}\models\varphi(m)$; however, this doesn't give us a least element of $SH(\mathcal{N})$ satisfying $\varphi$.

I'm in general interested in the arithmetic properties of $SH(\mathcal{N})$. In the interests of asking a concrete question, however:

Are there nonstandard models $\mathcal{N}$ of $I\Sigma_1$ with $SH(\mathcal{N})\models I\Sigma_1$? If so, what determines whether $SH(\mathcal{N})\models I\Sigma_1$?

$\endgroup$
2
  • 1
    $\begingroup$ Is there any reason to believe $SH(\mathcal N)$ is different from the parameter-free $\Sigma_1$-definable elements on $\mathcal N$? $\endgroup$ May 22, 2015 at 2:13
  • $\begingroup$ No, they should be the same - that's a much clearer way to phrase it. $\endgroup$ May 22, 2015 at 2:15

1 Answer 1

1
$\begingroup$

[Remark: This answer assumes Noah's answer to my comment that $SH(\mathcal N)$ consists precisely of the elements of $\mathcal N$ that are $\Sigma_1$-definable without parameters. This way, not only is $SH(\mathcal N)$ a semiring but it is closed under all standard primitive recursive functions (assuming $\mathcal N \models I\Sigma_1$). In particular, $SH(\mathcal N)$ understands the standard methods for encoding Turing machines and their computations, hence $SH(\mathcal N)$ correctly understands the formula $\tau(e,s)$ below.]

There is a bounded formula $\tau(e,s) \equiv$ "$\phi_e(0)$ halts in at most $s$ steps". Therefore $$\omega = \{x \in SH(\mathcal N) : SH(\mathcal N) \models \exists s \forall e \leq x \lnot\tau(e,s)\}$$ witnesses the failure of $\Sigma_1$-induction in $SH(\mathcal N)$ unless $SH(\mathcal N) = \omega$. The latter happens if and only if $\mathcal N$ satisfies every true $\Pi_1$ sentence.

$\endgroup$
2
  • $\begingroup$ François, could you explain a bit more? Why doesn't $s=0$ fulfill that existential trivially? $\endgroup$ May 22, 2015 at 12:13
  • $\begingroup$ @JoelDavidHamkins: You're right that $SH(\mathcal N)$ depends on how one clocks Turing machines. If $0 \notin SH(\mathcal N)$ then $SH(\mathcal N)$ isn't a semiring nor does it contain all parameter-free $\Sigma_1$-definable elements of $\mathcal N$ and the answer breaks down. $\endgroup$ May 22, 2015 at 17:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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