Any [algebraically closed field](http://en.wikipedia.org/wiki/Algebraically_closed_field) (ACF) is a model of Modular arithmetic (MA). (MA) has the same axioms as first order [Peano arithmetic](http://en.wikipedia.org/wiki/Peano_axioms#First-order_theory_of_arithmetic) (PA) except $\forall x(Sx \neq 0)$ is replaced with $\exists x(Sx=0)$. MA is [$\omega$-inconsistent](http://en.wikipedia.org/wiki/%CE%A9-consistent_theory) and all infinite models are [non-standard](http://en.wikipedia.org/wiki/Non-standard_model_of_arithmetic).


Is any ACF a recursive model of MA? If so, how would such a model avoid [Tennenbaum's theorem](http://arxiv.org/abs/1311.6375)? I know there are [weak theories of arithmetic](http://www.math.cas.cz/~jerabek/papers/realclosures.pdf) with recursive non-standard models, but MA has the same induction schema as PA.


I have [read](https://mathoverflow.net/questions/23796/a-question-about-open-induction) "An old theorem of A. J. Wilkie (Some results and problems on weak systems of arithmetic, Logic Colloquium '77) asserts that a discretely ordered ring $R$ can be extended to a model of open induction if and only if for all $n>1$, there is a homomorphism from $R$ onto $\mathbb{Z} /n \mathbb{Z}$". An ACF is not a discretely ordered ring, but any $\mathbb{Z} /n \mathbb{Z}$ is a model of MA. Is $\mathbb{A}$ homomorphic to some $\mathbb{Z} /n \mathbb{Z}$ or are ACF's different from other models of MA?


I asked this [question](https://math.stackexchange.com/questions/598875/recursive-non-standard-models) on SE and got no answer.




---


The standard models of MA are the rings $\mathbb{Z} /n \mathbb{Z}$ where $\mathbb{Z}$ are the standard integers and $n$ is a standard natural number. All standard models of MA are finite. Let $\mathbb{N}^\*$ be a countable non-standard model of PA and let $\mathbb{Z}^\*$ be the integers extended from $\mathbb{N}^\*$. A "non-standard" model of MA would be a ring $\mathbb{Z}^\* /n^\* \mathbb{Z}^\*$ where $n^\*$ is a non-standard natural number larger than any standard natural number.


We know the [structure](http://en.wikipedia.org/wiki/Non-standard_model_of_arithmetic#Structure_of_countable_non-standard_models) of $\mathbb{N}^\*$ is $\omega + (\omega ^\* + \omega) \cdot \eta$ where $\omega$ is the order type of the natural numbers, $(\omega ^\* + \omega)$ is the order type of the integers and $\eta$ is the order type of the rationals. The $(\omega ^\* + \omega)$ structures are sometimes call Z-blocks. The usual argument for the structure of countable non-standard models starts by assuming $a$ and $b$ are natural numbers and $|b-a|$ is larger than any standard natural number. Assume $a+b$ is even. Then $\frac{a+b}{2}$ must be an infinite distance from $a$ and an infinite distance from $b$. This shows the Z-blocks are dense. Between any two Z-blocks there is another Z-block.


I have always assumed similar arguments show a ring $\mathbb{Z}^\* /n^\* \mathbb{Z}^\*$ has the structure $(\omega ^\* + \omega) \cdot \eta$. I expand my question to ask if there are recursive models of $\mathbb{Z}^\* /n^\* \mathbb{Z}^\*$.



Recursive Non-standard Models of Modular Arithmetic?
The only part of the question that looks research-level is the last sentence, provided it is interpreted as “are there recursive models of *the theory* of $\mathbb{Z}^\* /n^\* \mathbb{Z}^\*$”, so let me address that. (Models do not have models, theories have models. The preceding discussion is quite nonsensical, as one can only ask about the order type of a structure that carries an order.)


The answer is that it depends on the properties of $n^\*$.


On the one hand, the usual proof of Tennenbaum’s theorem can be modified to produce an $n^\*$ such that $\mathrm{Th}(\mathbb{Z}^\* /n^\* \mathbb{Z}^\*)$ has no recursive models. Specifically, if $X$ and $Y$ are recursively inseparable r.e. sets of (standard) natural numbers, one can use overspill to find an $n^\*\in\mathbb N^\*$ such that


* if $k\in X$, then $p\_k$ (the $k$th prime) divides $n^\*$,
* if $k\in Y$, then $p\_k$ is coprime to $n^\*$.


Then if $M$ is a recursive model elementarily equivalent to $\mathbb{Z}^\* /n^\* \mathbb{Z}^\*$, the set $\{k:M\models\exists x\ne0\,(p\_kx=0)\}$ and its complement $\{k:M\models\exists x\,(p\_kx=1)\}$ are both r.e., hence they are recursive, and they separate $X$ and $Y$, contrary to the assumption.


On the other hand, if $n^\*$ is a nonstandard prime, then $F=\mathbb{Z}^\* /n^\* \mathbb{Z}^\*$ is a pseudofinite field of characteristic 0 (by a result of Macintyre). By a result of Ax, the theory of $F$ is decidable iff the set of univariate integer polynomials that have a root in $F$ is decidable. By a theorem of Frobenius, every monic integer polynomial splits modulo infinitely many primes, thus using overspill, there exists a nonstandard prime $n^\*$ such that *all* nonconstant integer polynomials have a root in $\mathbb{Z}^\* /n^\* \mathbb{Z}^\*$. It follows from the quoted result of Ax that $\mathrm{Th}(\mathbb{Z}^\* /n^\* \mathbb{Z}^\*)$ is decidable, hence it has a recursive model (with a recursive satisfaction predicate for all formulas).


