Tennenbaum's theorem

Tennenbaum's theorem, named for Stanley Tennenbaum who presented the theorem in 1959, is a result in mathematical logic that states that no countable nonstandard model of Peano arithmetic (PA) can be recursive.

Recursive structures for PA

A structure $\scriptstyle M$ in the language of PA is recursive if there are recursive functions + and × from $\scriptstyle N\times N$ to $\scriptstyle N$, a recursive two-place relation < on $\scriptstyle N$, and distinguished constants $\scriptstyle n_{0},n_{1}$ such that

$(N,+,\times ,<,n_{{0}},n_{{1}})\equiv M,\,$

where $\scriptstyle \equiv$ indicates isomorphism and $\scriptstyle N$ is the set of (standard) natural numbers. Because the isomorphism must be a bijection, every recursive model is countable. There are many nonisomorphic countable nonstandard models of PA.

Statement of the theorem

Tennenbaum's theorem states that no countable nonstandard model of PA is recursive. Moreover, neither the addition nor the multiplication of such a model can be recursive.

Proof Strategy

Briefly, the strategy for proving Tennenbaum's Theorem is based on the "overspill principle", which guarantees that certain nonstandard numbers must exist, and recursively inseparable sets, which guarantee that certain recursive separating sets cannot exist. These two forces are put into conflict by the fact that given a model with a recursive coding on the natural numbers, any formula with bounded quantifiers and finitely many parameters will produce a recursive set of natural numbers consisting of the codes of the elements for which the formula holds.

The overspill principle is used to show that the desired parameter exists, and if a nonstandard model were to have a recursive coding then a particular bounded-quantifier formula supplied with that parameter and composed with the injection mapping (from natural numbers to codes for elements of the model) would be a recursive separator of recursively inseparable sets.

Proof Outline

The theory of PA cannot define the standard part of a nonstandard model. This is because the standard part of a nonstandard model is closed under the successor operation, so a first-order formula that were true for exactly the standard numbers would satisfy the premises of the induction schema (true for 0 and true for every successor of an element it is true for) without satisfying the conclusion (true everywhere). This is the origin of the overspill principle: if some formula is true for all the standard elements of the model it must be true for a nonstandard element as well. Any infinite part of the model defined by a first-order formula must "spill over" from the standard part into the nonstandard part; otherwise the formula would define the standard part of the model.

The other force at play is the existence of disjoint recursively enumerable sets which are not separable by any recursive set. For example, consider the set of (natural number codes for) provable first-order formulas and the set of codes for disprovable first-order formulas. Each of these sets is recursively enumerable: just enumerate all the well-formed proofs of predicate calculus and look at their conclusions. However, the existence of a separating set would contradict Gödel's incompleteness theorem.

Given two such disjoint and inseparable recursively enumerable (r.e.) sets A and B, for every natural number k the formula "for all x<k, y<k, and z<k: z is not both the x^th smallest element of A and the y^th smallest element of B" is a theorem of PA (since A and B are disjoint sets). Since this formula holds for every natural number k the overspill principle forces it to hold for some nonstandard element n. Now consider the set C of all elements e of the model such that e is the i^th smallest element of A for some i<n. This subset of the model is definable (from one parameter, n) by a first order formula, and it includes all of (the standard part of) A but none of (the standard part of) B. Therefore (the standard part of) C cannot be a recursive set since A and B are recursively inseparable.

If the elements of M were to be coded onto the (standard) natural numbers in such a way that the addition and multiplication operations of the model were recursive functions on the codes, then every subset of the model defined by a first-order formula with finitely many parameters and bounded quantifiers is a recursive set of natural numbers. Moreover the injection mapping that takes a standard natural number to the code for that element in the model is also a recursive function -- to inject the number k simply take the code for the model's zero element and perform the model's successor operation on it k times. Therefore any recursive coding of a nonstandard model onto the natural numbers, along with a recursive definition (acting on codes) for the model's addition and multiplication operations will give a recursive separator, which cannot exist.

References

• George Boolos, John P. Burgess, and Richard Jeffrey (2002) Computability and Logic, 4th ed. Cambridge University Press. ISBN 0-521-00758-5
• Richard Kaye (1991) Models of Peano arithmetic. Oxford University Press. ISBN 0-19-853213-X.
• Richard Kaye (Sep 2011). "Tennenbaum's Theorem for Models of Arithmetic". In Juliette Kennedy and Roman Kossak. Set theory, arithmetic, and foundations of mathematics - theorems, philosophies (PDF). Lecture Notes in Logic. 36. ISBN 9781107008045.