I'm in the midst of confusion about non-standard integers. It is my understanding that for example, in ZFC the Riemann hypothesis is equivalent to a $\Pi_1^0$ statement $(\forall y) \phi(y)$ where $\phi$ is a $\Delta_0$ formula in the language of arithmetic. Since every "true" (in the standard model) $\Sigma_1^0$ statement is provable in PA, my understanding is that if RH is independent of ZFC then it follows that $(\forall y) \phi(y)$ then must be true in the standard model of arithmetic. In this sense you get the notable "if the Riemann hypothesis is independent of ZFC, then it is true". The reason why $(\forall y)\phi(y)$ could be independent of ZFC is the possible existence of models of ZFC where there are non-standard "natural numbers" $y$ for which $\neg \phi(y)$ is true. If there are models of ZFC whose set of natural numbers is "standard", then $(\forall y)\phi(y)$ will be true within them.
Now consider a $\Sigma_0^1$ set $A$ with $x \in A$ iff $(\exists y)\phi(x, y)$ , where $\phi$ is a $\Delta_0$ formula in the language of arithmetic. It is possible that whether $n \in A$ for a particular $n$ is independent of PA, and then in models where $n \in A$, $(\exists y) \phi(x, y)$ has a non-standard witness. I'm now confused by the proof that a set is computably enumerable if it is $\Sigma_0^1$: my understanding was that we basically have a Turing machine that takes in $x$ and runs through each natural number $y$ until one is found with $\phi(x, y)$, and then the machine halts. Otherwise it will fail to halt. This machine halts precisely on elements of $A$ and hence witnesses the computable enumerability of $A$.
My question is twofold:
- How does this "run through each natural number $y$" translate into non-standard models of arithmetic? I think of this as working $0$, $1$, etc., but in non-standard models of arithmetic we have numbers that are not (externally? finite?) successors of $0$, so this tripped me up a bit since it doesn't seem like the ordinary enumeration procedure would hit non-standard numbers. I figure it must be above board since this proof seems standard – I feel I am wrong somewhere in the previous sentence.
- Am I correct in saying that the existence of $n \in \omega$ such that whether $n \in A$ is independent of PA is unimportant, since if we run the code for the Turing machine within a model of PA in which $n \in A$ is true, the machine will find a witness and halt on input $n$? But then there will be models where the machine will not halt on $n$, so PA does not prove the halting behaviour of the machine.
Best Answer
Yes in general computation in nonstandard models can behave differently. Consider a model $M$ of $PA+\neg Con(PA)$, which must be non standard. Then we can run a Turing machine that for any input $x$ it will search the least proof of a contradiction from $PA$. First we notice that this Turing machine has a standard index $e$, however, when we run the machine indexed by $e$ in the natural numbers it will never halt regardless of the input (so in particular $\omega\vDash W_e=\emptyset$) however in $M$ we have that $W_e$ is the set of all numbers. (By $W_e$ I mean the $e$-th $\Sigma^0_1$ set or rather the collection of all $n$ such that the Turing machine with index $e$ with input $n$ halts).
For less obvious examples you can look at the Goodstein sequences which are computable sequences of numbers that $PA$ cannot prove that they all terminate (see: https://en.wikipedia.org/wiki/Goodstein%27s_theorem). This is also related to the consistency of $PA$ since the ordinal $\epsilon_0$ being well ordered is in a way equivalent to the Goodstein sequences terminating. By a result of Gentzen you have that $\epsilon_0$ being well ordered implies the consistency of $PA$ (see: https://arxiv.org/pdf/1405.4484.pdf).
In general, how a nonstandard model of arithmetic interprets computation does not correspond to what is computable in the standard sense. This is because countable nonstandard models of $PA$ are not computable (in general this is true for nonstandard models of a weak fragment of $PA$ called $P^-+\textbf{I}\Delta^0_0$ see: https://en.wikipedia.org/wiki/Tennenbaum's_theorem). This means in particular that the "run through each number $y$" in nonstandard models does not correspond to an actual finitary process that can be performed by a Turing machine. Part of this is also related to the fact that in nonstandard models of $PA$ the notion of finiteness is also skewed, in the sense that there are many coded sets which the model thinks are finite but are externally infinite. If you go through the proof of Tennenbaum's theorem you can see how this skewed interpretation of finiteness is what is used to show that nonstandard countable models of $PA$ are not computable.
Finally, you are correct that $PA$ does not prove the correct halting behavior of all Turing machines, and neither will any recursively axiomatizable theory like $ZFC$, however it will accurately prove the halting behavior of some of the machines. That is to say that not everything goes, even when you consider nonstandard models. Furthermore if for standard $e,n\in \omega$ the Turing machine with index halts at input $n$ for the natural numbers it will halt in all models of $PA$. This is because, as you mentioned, $PA$ proves all true $\Sigma^0_1$ statements.
Edit: The way you interpret computation in first order arithmetic is through the Kleene normal form, that is there is some formula $U$ such that $U(e,s,x,o)$ is true if an only if the $e$-th Turing machine with input $x$ performs $s$ as a computation and halts with output $o$. In this case $s$ is the code for a sequence of computations. This means $s(n)$ is the state of the Turing machine $e$ and input $x$ at step $n$. We have that $s$ will have to satisfy certain arithmetically defined criteria to be considered a proper computation. In particular $U$ will require $s(0)$ to be some initial state given by $e$ and $x$ and $U$ will require that $s(n+1)$ to be some particular number relative to $s(n)$. This all depends heavily as to how you code sequences and Turing machines as natural numbers. In the case where $e$ is standard, and therefore corresponds to an actual program then this search will appear on some segment of $s$ in which the program "verifies" $0$,$1$,$2$,etc. Since internally $s$ is finite $M$ thinks this is just some finite search. Externally you have that $s$ could be listing out infinitely many "computations".