Are the algebraic numbers recursive?

Question

I am interested in a theory I call 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 has finite models: the commutative rings $\mathbb{Z}/n\mathbb{Z}$.

MA is an ill-founded theory and all infinite models of MA are non-standard. The algebraic numbers is a countably infinite non-standard model of MA. Tennenbaum's theorem says neither addition nor multiplication can be recursive in a non-standard model of arithmetic. Tennenbaum's theorem almost certainly applies to MA. Despite this, we can do arithmetic with algebraic numbers using the rules for complex numbers.

Given the algebraic numbers as a model of MA, are addition and multiplication recursive in this model? If so, what prevents me from encoding a non-recursive set as an algebraic number? If addition and multiplication are not recursive in this model then what type of operations aren't computable?

---

By algebraic numbers I mean the field of algebraic numbers which is algebraically closed. This includes the complex algebraic numbers.

The standard definition $x \leq y \iff \exists z(x+z=y)$ does not work in MA because of the way modular arithmetic works. Consider that $(2+1=3) mod 4$ and $(3+3=2) mod 4$ proving $2 \leq 3$ and $3 \leq 2$ in the model $\mathbb{Z}/4\mathbb{Z}$. This is why MA is an ill-founded theory. MA is also $\omega$-inconsistent. The statement $\forall x(Sx \neq 0)$ is true for all standard natural numbers in any infinite model of MA. $\omega$-inconsistent theories can't have a standard infinite model.

Tennenbaum's theorem is a proof by contradiction that applies to very weak theories of arithmetic. MA is a relatively strong theory. The question is whether a non-recursive set of standard natural numbers can be encoded as a non-standard number. In the algebraic numbers, any number that is not a standard natural number is a non-standard natural number. For example, $-1, \frac{1}{2}$, and $i$ are all "infinite" natural numbers in this model. Tennenbaum's proof uses overspill.

Assume we have a non-recursive set of natural numbers. One way to encode this set is by using negative powers of 2. Basically, we define a binary number, $x$, such that the $n'th$ bit in $x's$ expansion is 1 if $n$ is in the set. Consider the following statement:

$\sum_{i=0}^{n} 2^{-i} = 2-2^{-n}$

If our algebraic model of MA is recursive then I can compute this sum for $\frac{1}{2}$ which is $2-2^{-\frac{1}{2}} = 1.29...$. Now, I can subtract $2^{-n}$ from this sum for every $n$ in our non-recursive set. This gives me a number where the $n'th$ bit of the number is $0$ if $n$ is in our set. Note that I don't actually have to compute such a number. I only have to show such an algebraic number exists and can be used as an oracle for a TM.

Answer 1

Let me preface this by saying that I'm very surprised by your claim that Tennenbaum "almost certainly" applies to $MA$. Do you have any evidence for this? Also, what precisely does "nonstandard model" mean in the context of $MA$?

Do you mean the algebraic real numbers, or the algebraic complex numbers?

The algebraic reals do not, in fact, form a model of $MA$. The nonnegative algebraic numbers are definable - they are the ones which have square roots (note that the square root of an algebraic number is algebraic).

Now this means that induction fails in the algebraic reals - $0$ is nonnegative, and the successor of a nonnegative number is nonnegative, but there are non-nonnegative (heh) algebraic numbers.

As a side note, of course, this means that the usual ordering is definable as

$x\le y\iff \exists z(z*z+x=y)$,

contra your comment above.

For the algebraic complex numbers, things are more complicated; they might form a model of $MA$, but I'm not sure.

---

As to the question of whether the structure $(A, +, \times)$ ($A$ the set of algebraic reals, $+$ and $\times$ usual addition and multiplication) has a recursive copy: it does, but the proof is nontrivial. The difficulty, roughly, is the following: I need some way of "naming" algebraic numbers so that each one has exactly one name, and I can effectively find names for the sum and product of two named algebraic numbers.

Here's how to do that: say that a pre-code is a pair $(p, I)$, where

• $p$ is a polynomial with rational coefficients, and

• $I$ is an open interval with rational endpoints.

A precode is a code if

• $p$ has exactly one zero in $I$.

Fix some appropriate mechanism $\eta$ for coding precodes by naturals. Now we have two important facts: the theory of the structure $\mathcal{R}=(\mathbb{R}, +, \times)$ is decidable (Tarski https://en.wikipedia.org/wiki/Decidability_of_first-order_theories_of_the_real_numbers), and each element of $\mathbb{Q}$ is definable in $\mathcal{R}$. This combines to show the following:

• The set of codes is computable.

• The relation $\sim$ on codes, given by $(p, I)\sim (q, J)$ iff the unique zero of $p$ in $I$ is the unique zero of $q$ in $J$, is computable.

Say that $(p, I)$ is a good code if there is no earlier (in the sense of the coding-by-naturals $\eta$) code $(q, J)$ which is $\sim (p, I)$. Then by the above, the set of good codes is computable. Again applying decidability of $\mathcal{R}$ and the definability of each rational in $\mathcal{R}$, the operations $\oplus$ and $\otimes$ on good codes defined below are computable:

• $(p, I)\oplus (q, J)=(r, K)$ iff $(r, K)$ is a good code and the unique zero of $r$ in $K$ is the sum of the unique zeroes of $p$ in $I$ and of $q$ in $J$.

• $(p, I)\otimes (q, J)=(r, K)$ iff $(r, K)$ is a good code and the unique zero of $r$ in $K$ is the product of the unique zeroes of $p$ in $I$ and of $q$ in $J$.

A similar argument also works for the algebraic complex numbers.

---

EDIT: As to your question

what prevents me from encoding a non-recursive set as an algebraic number?

Note that a key component of Tennenbaum's theorem is coding via prime factorization; that is, the (semi)ring structure of any model of arithmetic has a lot of definable complexity. (This is also a driving force in Godel's theorem.) By contrast, prime factorization isn't interesting in a field. So "what prevents" this coding is the complete absence of any of the analogous semiring-theoretic complexity!

And indeed, the theory of the field of algebraic numbers is decidable. So this really is a crucial bit of complexity that's dropped.

---

EDIT: Based on your recent edit to the question, I believe this will be relevant:

If $z=a+bi$ is algebraic, then the decimal expansions of $a$ and $b$ are each computable.

This is a standard exercise. The rough outline is: suppose $z=a+bi$ is algebraic, and fix a polynomial $p$, rational $c$ and $d$, and a rational $q$ such that the unique root of $p$ in $\{y: \vert y-(c+di)\vert<q\}$ is $z$. We now use the decidability of $\mathbb{C}$ to compute the decimal expansions of $a$ and $b$. For example, we can use $Th(\mathbb{C})$ to answer questions of the form

Is $z$ in the closed box $[1.356+2.837i, 1.357+2.838i]\times [12.458-0.001i, 12.459-0i]$?

By asking a series of such questions, we can compute the decimal expansion of $a$ and $b$. A slight difficulty is caused if either/both $a$ and $b$ are rational; but this is easily handled by a separate case (note that every rational is definable).

This is why we can't code a non-computable set into the decimal expansion of an algebraic number. And the lack of semiring-theoretic complexity prevents other kinds of Tennenbaum encoding. Based on all this, I again ask: do you have any real reason to believe Tennenbaum holds for $MA$?