I'm looking at the theorem concerning the Model of Arithmetic:
M arith = (Integers, +, *, <) is undecidable.
What does the "decidability" of a model mean exactly? Does that mean that "the problem of determining if the given model satisfies any FOL statement" is undecidable?
Thanks for the help!
On
If you mean the effectiveness of $PA$ (i,e., the first order theory of arithmetic with $+,*,<$ primitive recursive), then this link http://www.math.cornell.edu/~shore/papers/pdf/effmod32.pdf covers a great deal of direct properties of effectively decidable first order theories and their corresponding models.
But, regarding your question in particular, the decidability of a model $M$ of arithmetic (a model of $PA$) can mean the following: 1) The language $L_M$ is recursively enumerable, in the sense that every term, formula, and sentence can be effectively associate with a Goedel numbering. 2) By Goedel's incompleteness theorem, since $L_M$ cannot be both complete and consistent, then there are some arithmetical truths (in the sense of a partial truth predicate $Tr_1$) for which there is no proof sequence leading from the axioms of $PA$ to all valid sentences of the natural numbers. This is, in essence, the content of Goedel's first incompleteness theorem coupled with the compactness theorem, which asserts that $PA$ (a set of first-order sentences) has a model iff every finite subset of $PA$ has a model.
The problem you cite originates in the proof of (2) that assets that $PA$ is not both consistent and complete. This is a case of Goedel's first incompleteness theorem. Formulated in terms of computability, it simply is the proof of the fact that no finite program $e$ of a Turing machine $T^e$ can decide whether a $\Delta^0_1$ sentence $\forall x\phi(x)$ or $\exists x \phi(x)$ is true (halts if 0 if $Tr_1$ holds for $x$, and 1 if otherwise) in a denumerable domain (a model $M$) or whether it is refutable.
This is clear if one has an enumeration of the partial recursive functions $f_1(z),..,f_e(z)$ where $e$ is the code of $T_e$ on arbitrary input $z$. Since if all such sentences $\phi$ where decidable by $T^e$ then one could effectively deduce a proof of $0=1$, which proves everything from $PA$, including its own inconsistency (which is the content of Goedel's second incompleteness theorem).
Hope this helps. As a hint for a proof, think of the diagonal argument in terms of proving that that set of all valid sentences $\forall x \psi(x)$ is not in the range of a total recursive function, since if it were, then out could deduce a contradiction, consequently proving such a function indeed does not exist for the set in question.
In this case, the undecidability means there is no algorithm for deciding in general whether a sentence in our language is true in $\mathbb{Z}$.
To prove the undecidability, it is easiest to use the fact that there is no algorithm for deciding whether a sentence over the the usual language for arithmetic is true in the natural numbers $\mathbb{N}$. (Here it is convenient and customary, but not necessary, to have $\mathbb{N}$ include $0$.)
Then to prove the required undecidability result, we show that given any sentence $\varphi$ of "arithmetic," we can mechanically produce a sentence $\varphi'$ such that $\varphi$ is true in $\mathbb{N}$ if and only if $\varphi'$ is true in $\mathbb{Z}$.
This shows that if we had an algorithm for deciding truth in $\mathbb{Z}$, we could produce an algorithm for deciding truth in $\mathbb{N}$. But there is no such algorithm.