Are computable models sufficient? - MathOverflow

Are computable models sufficient?

2010-08-02T10:41:25Z

What I mean is this. By downward Lowenheim-Skolem theorem, first-order formula Q is a always true iff it is true in every countable structure. But is there some first-order formula Q which is true in every computable structure and false in some non-computable structure? My feeling is that of course the answer should be "yes", but I can't construct an example. I feel also that the questions of the sort has been widely studied. (For example, maybe some study of conditions under which first-order theory has computable model or hasn't). Do you know anything about that?

Thanks in advance.

Answer by Carl Mummert for Are computable models sufficient?

2010-08-02T11:51:23Z

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

Answer by Kaveh for Are computable models sufficient?

2010-08-02T20:54:06Z

Carl's answer is correct.

There is also a to more direct way to achieve the same thing. The Tennenbaum's theorem holds for much weaker theories, e.g. $I\Delta_0$ (even for far weaker theories like $IOpen$ plus some number theoretic principles, but not for $IOpen$, a result due to Shepherdson).
$I\Delta_0+exp$ is finitely axiomatizable, see Haim Gaifman and Constantine Dimitracopoulos, "Fragments of Peano's Arithmetic and the MRDP Theorem". It is also a sub-theory of $PA$.

For more on Tennenbaum's theorem and weak arithmetics, have a look at this paper:
Shahram Mohsenipour, "Hierarchies of Subsystems of Weak Arithmetic", to appear
in "Set theory, Arithmetic, Philosophy: Essays in Memory of Stanley Tennenbaum" (edited by J. Kennedy and R. Kossak), Cambridge University Press.