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$?

  • 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$ – François G. Dorais May 22 '15 at 2:13
  • $\begingroup$ No, they should be the same - that's a much clearer way to phrase it. $\endgroup$ – Noah Schweber May 22 '15 at 2:15

[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.

| cite | improve this answer | |
  • $\begingroup$ François, could you explain a bit more? Why doesn't $s=0$ fulfill that existential trivially? $\endgroup$ – Joel David Hamkins May 22 '15 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$ – François G. Dorais May 22 '15 at 17:00

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.