Skip to main content
Correct last paragraph
Source Link
Carl Mummert
  • 9.7k
  • 1
  • 46
  • 68

There is no computable, countable nonstandard model of Peano arithmetic. This result is known as Tennenbaum's theorem after Stanley Tennenbaum. There is an online paper at [1]. So if you take any sentence $R$ in the language of PA that is not true in the standard model but is consistent with PA, it will be true in some countable model of PA but not in the (unique, up to isomorphism) computable model of PA.

But I'm not sure if that addresses your question, because that answer is about models of a theory. In your question, it seems like you're talking about all countable models in the language of particular formula, rather than all models of a particular theory.

To make the answer fit that question, we want to replace PA with a finitely axiomatized subtheory of PA for which the only computable model is the standard model. There is a heuristic principle that we should be able to find a subtheory like this by examining the proof of Tennenbaum's theorem, and reference [1] confirms that this does work.

Let $T$ be the sentence that is the conjunction of the axioms of this subtheory. Let $R$ be the independent sentence from the first part, and look at the sentence $T \rightarrow R$$T \rightarrow \lnot R$. This will be true in every computable model (because the only computable model that satisfies $T$ is the standard model, which satisfies $R$$\lnot R$). It will be false in any countable nonstandard model of PA in which $R$ failsholds, because $T$ is a subtheory of PA.

1: Richard Kaye, "Tennenbaum's Theorem for Models of Arithmetic", http://web.mat.bham.ac.uk/R.W.Kaye/papers/tennenbaum/tennenbaum

(Note: I corrected the last paragraph based on a comment by Sergei Tropanets.)

There is no computable, countable nonstandard model of Peano arithmetic. This result is known as Tennenbaum's theorem after Stanley Tennenbaum. There is an online paper at [1]. So if you take any sentence $R$ in the language of PA that is not true in the standard model but is consistent with PA, it will be true in some countable model of PA but not in the (unique, up to isomorphism) computable model of PA.

But I'm not sure if that addresses your question, because that answer is about models of a theory. In your question, it seems like you're talking about all countable models in the language of particular formula, rather than all models of a particular theory.

To make the answer fit that question, we want to replace PA with a finitely axiomatized subtheory of PA for which the only computable model is the standard model. There is a heuristic principle that we should be able to find a subtheory like this by examining the proof of Tennenbaum's theorem, and reference [1] confirms that this does work.

Let $T$ be the sentence that is the conjunction of the axioms of this subtheory. Let $R$ be the independent sentence from the first part, and look at the sentence $T \rightarrow R$. This will be true in every computable model (because the only computable model that satisfies $T$ is the standard model, which satisfies $R$). It will be false in any countable nonstandard model of PA in which $R$ fails, because $T$ is a subtheory of PA.

1: Richard Kaye, "Tennenbaum's Theorem for Models of Arithmetic", http://web.mat.bham.ac.uk/R.W.Kaye/papers/tennenbaum/tennenbaum

There is no computable, countable nonstandard model of Peano arithmetic. This result is known as Tennenbaum's theorem after Stanley Tennenbaum. There is an online paper at [1]. So if you take any sentence $R$ in the language of PA that is not true in the standard model but is consistent with PA, it will be true in some countable model of PA but not in the (unique, up to isomorphism) computable model of PA.

But I'm not sure if that addresses your question, because that answer is about models of a theory. In your question, it seems like you're talking about all countable models in the language of particular formula, rather than all models of a particular theory.

To make the answer fit that question, we want to replace PA with a finitely axiomatized subtheory of PA for which the only computable model is the standard model. There is a heuristic principle that we should be able to find a subtheory like this by examining the proof of Tennenbaum's theorem, and reference [1] confirms that this does work.

Let $T$ be the sentence that is the conjunction of the axioms of this subtheory. Let $R$ be the independent sentence from the first part, and look at the sentence $T \rightarrow \lnot R$. This will be true in every computable model (because the only computable model that satisfies $T$ is the standard model, which satisfies $\lnot R$). It will be false in any countable nonstandard model of PA in which $R$ holds, because $T$ is a subtheory of PA.

1: Richard Kaye, "Tennenbaum's Theorem for Models of Arithmetic", http://web.mat.bham.ac.uk/R.W.Kaye/papers/tennenbaum/tennenbaum

(Note: I corrected the last paragraph based on a comment by Sergei Tropanets.)

Source Link
Carl Mummert
  • 9.7k
  • 1
  • 46
  • 68

There is no computable, countable nonstandard model of Peano arithmetic. This result is known as Tennenbaum's theorem after Stanley Tennenbaum. There is an online paper at [1]. So if you take any sentence $R$ in the language of PA that is not true in the standard model but is consistent with PA, it will be true in some countable model of PA but not in the (unique, up to isomorphism) computable model of PA.

But I'm not sure if that addresses your question, because that answer is about models of a theory. In your question, it seems like you're talking about all countable models in the language of particular formula, rather than all models of a particular theory.

To make the answer fit that question, we want to replace PA with a finitely axiomatized subtheory of PA for which the only computable model is the standard model. There is a heuristic principle that we should be able to find a subtheory like this by examining the proof of Tennenbaum's theorem, and reference [1] confirms that this does work.

Let $T$ be the sentence that is the conjunction of the axioms of this subtheory. Let $R$ be the independent sentence from the first part, and look at the sentence $T \rightarrow R$. This will be true in every computable model (because the only computable model that satisfies $T$ is the standard model, which satisfies $R$). It will be false in any countable nonstandard model of PA in which $R$ fails, because $T$ is a subtheory of PA.

1: Richard Kaye, "Tennenbaum's Theorem for Models of Arithmetic", http://web.mat.bham.ac.uk/R.W.Kaye/papers/tennenbaum/tennenbaum