0
$\begingroup$

Any algebraically closed field (ACF) is a model of Modular arithmetic (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)$. MA is $\omega$-inconsistent and all infinite models are non-standard.

Is any ACF a recursive model of MA? If so, how would such a model avoid Tennenbaum's theorem? I know there are weak theories of arithmetic with recursive non-standard models, but MA has the same induction schema as PA.

I have read "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 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 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}^*$.

Improve this question
$\endgroup$
15
  • $\begingroup$ Every countable ACF is isomorphic to a recursive one. Tennenbaum’s theorem is about models of PA (or its weak subsystems like $IE_1$), so it does not apply to MA. I don’t understand the last question. What is $\mathbb A$? If it is supposed to be an ACF, then no, because every homomorphism from a field into another ring is automatically an embedding. $\endgroup$
    – Emil Jeřábek
    Commented Dec 14, 2013 at 18:15
  • $\begingroup$ Anyway, just like Tennenbaum’s theorem, Wilkie’s theorem is about models of DOR and IOpen, it has nothing to do with MA. $\endgroup$
    – Emil Jeřábek
    Commented Dec 14, 2013 at 18:19
  • $\begingroup$ Why doesn't Tennenbaum's theorem apply to MA? What prevents me from encoding a recursively inseparable set as a non-standard number? $\endgroup$
    – Russell Easterly
    Commented Dec 14, 2013 at 18:23
  • 3
    $\begingroup$ That’s not a sensible question. There is no reason why you should expect recursive sets to be encodable in the same way as in PA in a theory which is quite different from PA. Pretty much nothing in usual proofs of Tennebaum theorem works for MA. What you call for whatever reason “nonstandard models of MA” do not behave in any useful way similarly to nonstandard models of PA. The main property of nonstandard models of PA is that they are end-extensions of the standard model under the ordering of the model, and then induction gives overspill. None of this makes any sense without an ordering. $\endgroup$
    – Emil Jeřábek
    Commented Dec 14, 2013 at 18:33
  • $\begingroup$ I would accept this as an answer. Let $PA^{-Inf}$ be PA with out the axiom $\forall x(Sx \neq 0)$. Would Tennenbaum's theorem apply to $PA^{-Inf}$? Does Tennenbaum's theorem require the axiom $\forall x(Sx \neq 0)$? $\endgroup$
    – Russell Easterly
    Commented Dec 14, 2013 at 18:48

1 Answer 1

Reset to default
6
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks for taking the time to answer my question. I assume MA would not be "the theory of $\mathbb{Z}^* /n^* \mathbb{Z}^*$". Would you say something about what axioms such a theory would have? I will repost the question as "Are there theories where $\mathbb{Z}^* /n^* \mathbb{Z}^*$? is a recursive model" if you want. $\endgroup$
    – Russell Easterly
    Commented Dec 18, 2013 at 3:09
  • $\begingroup$ Assuming you are talking about the second part of the answer, the complete theory of the $\mathbb Z^*/n^*\mathbb Z^*$ chosen there is described in the answer, it is axiomatized by the theory of pseudofinite fields of characteristic $0$ together with the schema $\exists x\,f(x)=0$ for every nonconstant polynomial $f\in\mathbb Z[x]$. Note that this theory has a recursive model, but $\mathbb Z^*/n^*\mathbb Z^*$ is not recursive itself. All models of this form are recursively saturated, thus one can encode a nonrecursive set e.g. as $\{k:\exists x\,x^{p_k}=a\}$ for some $a$ in the model. $\endgroup$
    – Emil Jeřábek
    Commented Dec 18, 2013 at 11:28
  • 2
    $\begingroup$ In fact, quotients of models of PA by a nonstandard element are never recursive. One can easily show that if there were such a recursive model, then there would be one with $n^*$ a nonstandard prime. In the same paper where he proved that the fields one gets this way are pseudofinite (Residue fields of models of $P$), Macintyre also claims that they are not recursive (or equivalently, that there are no recursive, recursively saturated pseudofinite fields of characteristic $0$). $\endgroup$
    – Emil Jeřábek
    Commented Dec 18, 2013 at 21:40

Not the answer you're looking for? Browse other questions tagged .