I recently asked on math.stackexchange Are the algebraic numbers recursive? I had assumed the field of algebraic numbers is a model of a theory I call Modular Arithmetic. I also assumed Tennenbaum's theorem applies to MA. A number of people questioned these assumptions. I want to detail some of the questions asked and hopefully get answers to them. Issues mentioned included:
$\textbf{Models of MA}$ - Which models of MA are standard and what does it mean to say a model of MA is nonstandard? Is the field of algebraic numbers a model of MA?
$\textbf{Consistency}$ - Tennenbaum's theorem uses a proof by contradiction. Which theory, or theories, do we have to assume are consistent to use Tennenbaum's proof?
$\textbf{Meta-theory}$ - Which parts of Tennenbaum's proof rely on the meta-theory?
$\textbf{Overspill}$ - Tennenbaum's proof uses overspill. Is overspill applicable to MA?
$\textbf{Coding sets}$ - Tennenbaum's theorem requires encoding "finite" sets of natural numbers as a natural number. Can this be done in MA?
Models of MA
MA has the same axioms as first order Peano arithmetic (PA) except $\forall x Sx \neq 0$ is replaced with $\exists x Sx=0$. The standard models of MA are the finite commutative rings $\mathbb{Z}/n\mathbb{Z}$. Assume we have a model of MA where $S(n)=0$ and $n$ is a standard natural number. Then our model is a finite ring. $-1$ must be larger than all standard natural numbers in any infinite model of MA. The Lowenheim-Skolem theorem can be used to prove MA has infinite models. Any infinite model of MA has nonstandard elements that can't be represented as numerals in the language of MA. Mathematicians much better than I have told me any algebraically closed field is a model of MA. I have been unable to prove otherwise, but I would welcome any such disproof.
Consistency
Any proof by contradiction requires the assumption that one or more theories are consistent. MA is consistent because it has finite models, but proving MA has infinite models requires more than the axioms of MA. Tennenbaum's theorem is more about what can be proven in a standard meta-theory than what is provable in the non-standard model. We must assume both MA and the meta-theory are consistent to use Tennenbaum's proof.
Meta-theory
I am assuming the meta-theory is ZFC and based on a standard model of PA. I also assume the meta-theory can prove MA has infinite models. The only parts of Tennenbaum's proof that use the non-standard model are overspill and coding of sets.
Overspill
As near as I can tell, the standard argument for overspill works in MA. Assume there is a predicate that is only true for standard natural numbers and show the induction axiom is not satisfied.
Coding sets
Tennenbaum's proof uses prime factorization to encode finite (in the model) non-recursuve sets of natural numbers. This method fails in many models of MA. Sets of "small enough" numbers can be encoded as sums of powers of 2. Consider the set {1,2,3} encoded as $2^1+2^2+2^3$. Call this sum a "binary set". This sum works fine as an encoding of this set in a large enough model of MA like $\mathbb{Z}/100\mathbb{Z}$ but fails in a smaller model like $\mathbb{Z}/10\mathbb{Z}$. $x$ is "small enough" to be encoded into a set in model $\mathbb{M}$ if $x < floor(log2(|\mathbb{M}|))$. Given an infinite model of MA it is easy to see all standard natural numbers are small enough to be encoded into a binary set. All that remains is to show there are "infinite" natural numbers small enough to be encoded into binary sets. We can use overspill to do this. Assume we have a binary set that encodes all the standard natural numbers and only a finite number of nonstandard numbers. Then we could create a predicate with a finite number of exceptions that defines the standard natural numbers. This is a contradiction proving any encoding of all standard natural numbers must also encode an infinite number of nonstandard numbers. There is no smallest nonstandard binary set encoding of all the standard natural numbers. For any model, $\mathbb{M}$, of MA there exists a binary set including all standard natural numbers that is less than $log2(|\mathbb{M}|)$. A similar argument shows there is no smallest binary set encoding a non-recursive set.
Does Tennenbaum's theorem apply to Modular arithmetic? Please point out any obvious flaws in my reasoning. I know practically nothing about ring theory but I suspect there are lots of ways to encode finite sets of natural numbers in a commutative ring. I would welcome any suggestions. For example, could a finite set of natural numbers be encoded as the roots of a polynomial?
A major problem here, I think is that in a nonstandard model of PA, the standard elements form a submodel that is itself a model of PA, so properties we can prove about the standard model are automatically true in the larger non-standard model too.
In contrast, what you call standard elements of an infinite model of MA do not form a model of MA themselves -- instead they will be isomorphic to the standard naturals -- so the relationship between what is true about the standard elements and what is true in the model in general is much murkier.
This seems to be fatal for your plan -- Tennenbaum's reasoning depends on defining a nonrecursive subset of $\mathbb N$ by an arithmetic formula, and then arguing that this formula does not become true for too many additional standard elements when we interpret it in a non-standard model instead of in $\mathbb N$. And this argument depends on most of the quantifiers in the formula being bounded, which does not work well in the MA setting at all.
More precisely, in Tennenbaum's argument you start out with recursively inseparable disjoint subsets of $\mathbb N$, given as $A=\{n\mid \exists x.\varphi(n,x)\}$ and $B=\{n\mid \exists x.\psi(n,x)\}$, where $\varphi$ and $\psi$ have only bounded quantifiers in them. PA proves that $A$ and $B$ are disjoint -- formally $\forall n.\neg(\exists x.\varphi(n,x) \land \exists y.\psi(n,y))$ -- and therefore this holds even when the formulas are interpreted in the non-standard model.
When the non-standard model is not actually a model of PA, this argument falls apart -- there's no guarantee that $A$ and $B$ are still disjoint, as evaluated in the non-standard model. And there's a pretty good reason to expect that both $\varphi$ and $\psi$ will completely stop working like they do in $\mathbb N$, because they depend on bounded quantifiers, and in the MA world there's no ordering so the bounds don't work!
We never even get to the point where we ask if the non-standard model can encode its $A\cap\mathbb N$ as a single element or not.
But if we did come to that point, there would be problems there too. Your proposal about powers of $2$ tacitly assumes that the function $n\mapsto 2^n$ can be expressed in MA -- but it is not at all clear how one would do that without having a definable ordering.