# Are the algebraic numbers recursive?

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.

• "Almost certain applies to MA" is not really the same thing as "applies to MA", and you should be wary of things which are "almost certainly". Commented Mar 20, 2016 at 19:33
• Tennenbaum's theorem says that no countable nonstandard model of PA has a computable addition or multiplication. It does not literally apply to other theories, although by examining the proof we can see that only some finite number of axioms of PA are actually used, and so the theorem will apply to fragments of PA that contain these axioms. There is no reason I can see to suspect that the particular axiom of PA that is changed in MA would not be used in the proof of the theorem, and so I can't see why the theorem should apply to MA. Commented Mar 20, 2016 at 20:04
• Re: your edit, the decimal expansion of any algebraic number is computable - this is a standard exercise. So that line of attack won't work. Also, you still haven't given any real evidence for Tennenbaum's theorem holding for $MA$. In response to your claim "$MA$ is a relatively strong theory," note that $MA$ doesn't prove anything resembling unique prime factorization - which is one of the key components of Tennenbaum's theorem! So I don't see how you possibly view $MA$ as a "relatively strong theory" in this context. Commented Mar 20, 2016 at 21:24
• You have given no justification for your claim that the algebraic numbers are a model of MA. Commented Mar 20, 2016 at 21:29
• @RussellEasterly That's not what Tennenbaum's theorem says at all. I think I've hit the point of diminishing returns - I'm going to bow out now. Hopefully my answer helps you understand why incomputable sets can't be coded into algebraic numbers; and maybe you can clarify what exactly you mean by "Tennenbaum for MA," and why you think it holds. If you do, and ask that as a separate question, I'll try to answer it; but I think I'm done here. Commented Mar 20, 2016 at 21:53

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)$,

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.

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$?

• $2 \leq 3$ because $(2+1=3) mod 4$. $3 \leq 2$ because $(3+3=2) mod 4$. Tennenbaum's theorem is a proof by contradiction. That is why I ask if the is any reason why I can't encode a non-recursive set as an algebraic number. Commented Mar 20, 2016 at 19:55
• @RussellEasterly I do not understand your comment. What does mod 4 have to do with the specific structure (the algebraics) you're asking about? Also, why do you think Tennenbaum applies to $MA$? Commented Mar 20, 2016 at 19:57
• @AsafKaragila Actually, we can also use a completely different argument: every computable field has a computable algebraic closure (Frohlich/Sheperdson). Commented Mar 20, 2016 at 20:05
• Oh. That's pretty cool. Commented Mar 20, 2016 at 20:08
• @RussellEasterly Yes, for example: (1) the proof of Tennenbaum's theorem frequently uses facts not provable in $MA$. (2) $MA$ has a wide variety of models, e.g. the $p$-adic integers for every $p$, which are easily describable. Also, what is a standard model in the context of $MA$? Without defining this, it's utterly unclear what "Tennenbaum for $MA$" even means - and if we just take "standard model" to mean "the usual model of arithmetic," then the fact that the algebraically closed numbers satisfy $MA$ immediately disproves Tennenbaum for $MA$. Commented Mar 20, 2016 at 21:49