Tennenbaum's theorem

The set of Tennenbaum ( by Stanley Tennenbaum ) is a result of mathematical logic. He states that no countable nonstandard model of Peano arithmetic can be predictable. This is called a structure in the language of Peano arithmetic computable if there are computable functions and constants and from to, a computable binary relation, so with these objects is isomorphic to:

While addition and multiplication in any non-standard model are predictable, there are nonstandard models in which the order and the successor function can be calculated. For non-standard models of the "real" arithmetic, that is, in the theory of first-order logic apply, by analogy, that these are not arithmetically.

Sketch of proof

The proof uses the fact that non-standard models in addition to the natural numbers also "infinite " non-standard figures included and that there is a non-standard number a is for any non-standard model, an undecidable set A coded in the following sense: A is the amount of natural numbers n such that the n- th prime in the number a divides:

Now if a predictable non-standard model, then the addition would be particularly predictable. This could be achieved by division with remainder to determine whether a given number n is the non-standard number a divides. This means that the undecidable set A would be decidable.