Tennenbaum's theorem proves neither addition nor multiplication can be recursive in any countable non-standard model of arithmetic. Tennenbaum's proof applies to theories much weaker than PA.

Tennenbaum's proof is a proof by contradiction. If addition or multiplication is recursive in a non-standard model then it is possible to use a form of induction called overspill to prove recursively inseparable sets can be encoded as non-standard natural numbers. Overspill says if $f(n)$ is true for all standard natural numbers then $f(\alpha)$ is true for some non-standard natural number, $\alpha$. An example of a recursively inseparable set would be the set of standard natural numbers encoding a Turing machine that halts on blank input.

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 finite field" would be a ring $\mathbb{Z}^* /p^* \mathbb{Z}^*$ where $p^*$ is a non-standard prime number larger than any standard natural number. Non-standard finite fields admit almost quantifier elimination. This means non-standard finite fields must be "almost recursive".

It can be shown Tennenbaum's theorem applies to non-standard finite fields. If there exists a recursive non-standard finite field then Tennenbaum's proof by contradiction becomes a proof of contradiction. It means we can recursively determine if a standard natural number, $n$, encodes a halting TM by checking if $n$ is a root of one of a finite set of polynomials.

Is "almost quantifier elimination" enough to prove a non-standard finite field is recursive? Even if it is not, this seems to be a big problem. James Ax proved the theory of finite fields is decidable. Can there be a recursive mapping from a recursive model of finite fields to a non-recursive model or could we once again derive a contradiction?

  • 7
    $\begingroup$ That's a good question, but I advise you to avoid pompous titles as this one. In mathematics, and generally in science, it is best to assume that you are wrong until proven otherwise. Unless you fully prove that arithmetic is inconsistent, the ongoing assumption is that you are the one missing a point, and this title gives out the opposite vibe. $\endgroup$
    – Asaf Karagila
    Jan 10 '14 at 7:54
  • 1
    $\begingroup$ What has the final sentence, the only question in the body of the post, to do with the consistency of arithmetic? And how does your title square with talk about non-standard models of arithmetic, given that even the existence of unexpected models of a theory is enough to confirm consistency? $\endgroup$ Jan 10 '14 at 8:38
  • $\begingroup$ I apologize if my title seems pompous. Some people think I am crazy to doubt the consistency of arithmetic, but it is the motivation for my question. Tennenbaum's theorem and the decidability of the theory of finite fields are established results. If there is a recursive non-standard finite field it seems we could derive a contradiction using Tennenbaum's theorem. There are already proofs non-standard finite fields admit "almost quantifier elimination". I want to know if this is enough to prove such a model is recursive. $\endgroup$ Jan 11 '14 at 0:29
  • $\begingroup$ Russell, there's nothing inherently wrong doubting the consistency of arithmetic. And I applaud you for trying to argue your case as rigorously as possible, and without resorting to idiotic arguments like "Oh, the real numbers are countable because blah. Therefore modern mathematics is crap. -Signed, a physicist". But using pompous titles like this one only takes away from the question, and from you. This thread could have a perfectly valid and mathematically interesting title, rather than a thin attempt at controversy. $\endgroup$
    – Asaf Karagila
    Jan 15 '14 at 23:19
  • $\begingroup$ Good, thank you. Now I can vote this up without feeling strange. $\endgroup$
    – Asaf Karagila
    Jan 18 '14 at 20:55

I think there is a confusion here between two notions of "recursive".

Tennenabum's theorem deals with recursive structures. Let us assume for simplicity that that the language contains a single unary relation symbol $R$. Then a recursive structure $\mathcal M$ for this language has underlying set $\mathbb N$ and with $R^{\mathcal M}$ a recursive subset of $\mathbb N$. The formal definition is more complicated than that, but intuitively, in a recursive structure there is a reasonable coding of the elements and we can reasonably do computations. For example, the usual natural numbers, the ring of polynomials over the rationals, or the set $\mathbb N$ with a predicate for the primes are all recursive structures. By contrast, if we equip $\mathbb N$ with a single unary relation symbol for some undecidable set, then this structure is not recursive.

Tennenbaum's theorem says that there is no nonstandard recursive model of the theory of the natural numbers. So while we have computer programs that add and multiply integers, there can be no computer program which can perform manipulations on nonstandard integers.

Almost quantifier elimination deals with theories, not structures. If a theory has quantifier elimination, or something close, then we might expect that it is "easy" or closer to being decidable. But very complicated structures can have very simple theories. Take the example from before. The theory of an infinite set partitioned into two infinite sets is very simple and easy to understand. It is certainly decidable! But the structure $\mathbb N$ with a predicate for the set of those numbers coding a Turing machine which halts is complicated from this point of view, even though its theory is decidable.

  • $\begingroup$ I do assume a decidable theory has recursive models. As you point out, this is not a trivial assumption. Computers can add and multiply complex numbers. If there is a recursive mapping from the complex numbers to an uncountable non-standard finite field then computers could manipulate non-standard integers. $\endgroup$ Jan 11 '14 at 0:21
  • 4
    $\begingroup$ @RussellEasterly: no, they can't. Computers can only (even theoretically) add and multiply computable numbers (for the simple reason that they can't even represent any others!), and of those there are only countably many. $\endgroup$
    – tomasz
    Jan 11 '14 at 2:00
  • 1
    $\begingroup$ @tomasz: this is a question of formalism, to some extent. In Weihrauch-style computable analysis (which he calls TTE), the addition of arbtitrary real number is computable. $\endgroup$ Feb 15 '14 at 2:26

Several answers to this question can be seen on MathOverflow at https://mathoverflow.net/questions/157624/can-a-decidable-theory-have-non-recursive-models/ . In particular, the answer to the title question is "yes".


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.