Skip to main content
replaced http://mathoverflow.net/ with https://mathoverflow.net/
Source Link

One of the usual ways of proving Tennenbaum's theorem also applies to many of the theories on your list, and so they can have no computable nonstandard models.

The proof I have in mind is the following, which I also explained in this MO answerthis MO answer. Let $A$ be the set of Turing machine programs that halt on input $0$ with output $0$, and let $B$ be the set of programs that halt on input $0$ with output $1$. These sets are disjoint and computably inseparable, meaning that there is no computable $C$ containing $A$ and disjoint from $B$. Now, suppose that $M$ is a nonstandard model of arithmetic. Let $d$ be a nonstandard natural number, and inside $M$, consider the set of programs below $d$ that halt on input $0$ in at most $d$ steps with output $0$. In $M$, this is a (nonstandard) finite list, and so there is a nonstandard number $c$ coding this list of programs. Now, let $C$ be the set of standard programs $p$ that $M$ thinks appear on the list coded by $c$. This includes every program in $A$, since all such programs halt in a standard finite time with output $0$, and hence $M$ will agree that they halt before time $d$. Second, for a similar reason, this set includes no programs in $B$, since those programs halt in finite time with output $1$, and $M$ will see that. Finally, the set $C$ is computable from the operations of $M$, since we need only perform the decoding procedure to see if a given number $p$ is on the list coded by $c$. For example, we might use the coding that would require us merely to check whether $M$ thinks that the $p^{th}$ binary digit of $c$ is $1$ or not. If the operations of $M$ were computable, then this would be a computable procedure, in contradiction to the fact that $A$ and $B$ are computably inseparable. QED

Now, we haven't really used much of PA in this argument. Any theory $T$ that is able to perform basic Goedel coding and simulate Turing machine computations will be sufficient for the argument. This includes any $I\Sigma_n$, even $I\Sigma_0$, since the operation of a Turing machine is inductively iterating a very trivial process. So none of the stronger theories on your list have computable nonstandard models.

Meanwhile, however, I am unsure about the very weakest theories on your list, but this argument reduces the question to: can the given theory prove that for any number $d$, there is a number $c$ coding the list of Turing machine programs less than $d$ that halt on input $0$ with output $0$ in at most $d$ steps?

This is a comparatively simple statement in arithmetic, and any theory proving it will not have computable nonstandard models.

One of the usual ways of proving Tennenbaum's theorem also applies to many of the theories on your list, and so they can have no computable nonstandard models.

The proof I have in mind is the following, which I also explained in this MO answer. Let $A$ be the set of Turing machine programs that halt on input $0$ with output $0$, and let $B$ be the set of programs that halt on input $0$ with output $1$. These sets are disjoint and computably inseparable, meaning that there is no computable $C$ containing $A$ and disjoint from $B$. Now, suppose that $M$ is a nonstandard model of arithmetic. Let $d$ be a nonstandard natural number, and inside $M$, consider the set of programs below $d$ that halt on input $0$ in at most $d$ steps with output $0$. In $M$, this is a (nonstandard) finite list, and so there is a nonstandard number $c$ coding this list of programs. Now, let $C$ be the set of standard programs $p$ that $M$ thinks appear on the list coded by $c$. This includes every program in $A$, since all such programs halt in a standard finite time with output $0$, and hence $M$ will agree that they halt before time $d$. Second, for a similar reason, this set includes no programs in $B$, since those programs halt in finite time with output $1$, and $M$ will see that. Finally, the set $C$ is computable from the operations of $M$, since we need only perform the decoding procedure to see if a given number $p$ is on the list coded by $c$. For example, we might use the coding that would require us merely to check whether $M$ thinks that the $p^{th}$ binary digit of $c$ is $1$ or not. If the operations of $M$ were computable, then this would be a computable procedure, in contradiction to the fact that $A$ and $B$ are computably inseparable. QED

Now, we haven't really used much of PA in this argument. Any theory $T$ that is able to perform basic Goedel coding and simulate Turing machine computations will be sufficient for the argument. This includes any $I\Sigma_n$, even $I\Sigma_0$, since the operation of a Turing machine is inductively iterating a very trivial process. So none of the stronger theories on your list have computable nonstandard models.

Meanwhile, however, I am unsure about the very weakest theories on your list, but this argument reduces the question to: can the given theory prove that for any number $d$, there is a number $c$ coding the list of Turing machine programs less than $d$ that halt on input $0$ with output $0$ in at most $d$ steps?

This is a comparatively simple statement in arithmetic, and any theory proving it will not have computable nonstandard models.

One of the usual ways of proving Tennenbaum's theorem also applies to many of the theories on your list, and so they can have no computable nonstandard models.

The proof I have in mind is the following, which I also explained in this MO answer. Let $A$ be the set of Turing machine programs that halt on input $0$ with output $0$, and let $B$ be the set of programs that halt on input $0$ with output $1$. These sets are disjoint and computably inseparable, meaning that there is no computable $C$ containing $A$ and disjoint from $B$. Now, suppose that $M$ is a nonstandard model of arithmetic. Let $d$ be a nonstandard natural number, and inside $M$, consider the set of programs below $d$ that halt on input $0$ in at most $d$ steps with output $0$. In $M$, this is a (nonstandard) finite list, and so there is a nonstandard number $c$ coding this list of programs. Now, let $C$ be the set of standard programs $p$ that $M$ thinks appear on the list coded by $c$. This includes every program in $A$, since all such programs halt in a standard finite time with output $0$, and hence $M$ will agree that they halt before time $d$. Second, for a similar reason, this set includes no programs in $B$, since those programs halt in finite time with output $1$, and $M$ will see that. Finally, the set $C$ is computable from the operations of $M$, since we need only perform the decoding procedure to see if a given number $p$ is on the list coded by $c$. For example, we might use the coding that would require us merely to check whether $M$ thinks that the $p^{th}$ binary digit of $c$ is $1$ or not. If the operations of $M$ were computable, then this would be a computable procedure, in contradiction to the fact that $A$ and $B$ are computably inseparable. QED

Now, we haven't really used much of PA in this argument. Any theory $T$ that is able to perform basic Goedel coding and simulate Turing machine computations will be sufficient for the argument. This includes any $I\Sigma_n$, even $I\Sigma_0$, since the operation of a Turing machine is inductively iterating a very trivial process. So none of the stronger theories on your list have computable nonstandard models.

Meanwhile, however, I am unsure about the very weakest theories on your list, but this argument reduces the question to: can the given theory prove that for any number $d$, there is a number $c$ coding the list of Turing machine programs less than $d$ that halt on input $0$ with output $0$ in at most $d$ steps?

This is a comparatively simple statement in arithmetic, and any theory proving it will not have computable nonstandard models.

Source Link
Joel David Hamkins
  • 236.5k
  • 44
  • 777
  • 1.4k

One of the usual ways of proving Tennenbaum's theorem also applies to many of the theories on your list, and so they can have no computable nonstandard models.

The proof I have in mind is the following, which I also explained in this MO answer. Let $A$ be the set of Turing machine programs that halt on input $0$ with output $0$, and let $B$ be the set of programs that halt on input $0$ with output $1$. These sets are disjoint and computably inseparable, meaning that there is no computable $C$ containing $A$ and disjoint from $B$. Now, suppose that $M$ is a nonstandard model of arithmetic. Let $d$ be a nonstandard natural number, and inside $M$, consider the set of programs below $d$ that halt on input $0$ in at most $d$ steps with output $0$. In $M$, this is a (nonstandard) finite list, and so there is a nonstandard number $c$ coding this list of programs. Now, let $C$ be the set of standard programs $p$ that $M$ thinks appear on the list coded by $c$. This includes every program in $A$, since all such programs halt in a standard finite time with output $0$, and hence $M$ will agree that they halt before time $d$. Second, for a similar reason, this set includes no programs in $B$, since those programs halt in finite time with output $1$, and $M$ will see that. Finally, the set $C$ is computable from the operations of $M$, since we need only perform the decoding procedure to see if a given number $p$ is on the list coded by $c$. For example, we might use the coding that would require us merely to check whether $M$ thinks that the $p^{th}$ binary digit of $c$ is $1$ or not. If the operations of $M$ were computable, then this would be a computable procedure, in contradiction to the fact that $A$ and $B$ are computably inseparable. QED

Now, we haven't really used much of PA in this argument. Any theory $T$ that is able to perform basic Goedel coding and simulate Turing machine computations will be sufficient for the argument. This includes any $I\Sigma_n$, even $I\Sigma_0$, since the operation of a Turing machine is inductively iterating a very trivial process. So none of the stronger theories on your list have computable nonstandard models.

Meanwhile, however, I am unsure about the very weakest theories on your list, but this argument reduces the question to: can the given theory prove that for any number $d$, there is a number $c$ coding the list of Turing machine programs less than $d$ that halt on input $0$ with output $0$ in at most $d$ steps?

This is a comparatively simple statement in arithmetic, and any theory proving it will not have computable nonstandard models.