Set of Tennenbaum

The set of Tennenbaum (according to Stanley Tennenbaum ) is a result of mathematical logic . It says that no countable non-standard model of Peano arithmetic can be computable . A structure in the language of Peano arithmetic is called calculable if there are calculable functions and from to , a calculable binary relation to and constants , so that isomorphic to these objects : ${\displaystyle M}$ ${\displaystyle \oplus }$ ${\displaystyle \otimes }$ ${\displaystyle N\times N}$ ${\displaystyle N}$ ${\displaystyle \prec }$ ${\displaystyle N}$ ${\displaystyle n_{0},n_{1}}$ ${\displaystyle N}$ ${\displaystyle M}$

${\displaystyle (N,\oplus ,\otimes ,\prec ,n_{0},n_{1})\equiv M}$

While addition and multiplication cannot be calculated in any non-standard model, there are non-standard models in which the order and the successor function can be calculated. For non-standard models of “true” arithmetic, that is, the theory of first-order logic, it is analogous that these are not arithmetic . ${\displaystyle \mathbb {N} }$

Evidence sketch

The proof uses the fact that non-standard models contain "infinite" non-standard numbers in addition to the natural numbers and that for every non-standard model there is a non-standard number that encodes an undecidable set in the following sense : is exactly the set of natural numbers , so that the -th prime number divides into the number : ${\displaystyle M}$ ${\displaystyle a}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle M}$ ${\displaystyle a}$

${\displaystyle A=\{n\in \mathbb {N} :M\models pr(n)|a\}}$,

where the -th is prime. ${\displaystyle pr(n)}$ ${\displaystyle n}$

If there were a calculable non-standard model, then the addition in particular would be calculable. Thus, by dividing by the remainder , one could determine whether a given number divides the nonstandard number . This would also make it possible to decide the undecidable set . ${\displaystyle M}$ ${\displaystyle n}$ ${\displaystyle a}$ ${\displaystyle A}$

literature

• George Boolos , John P. Burgess, and Richard Jeffrey: Computability and Logic . 4th edition. Cambridge University Press, 2002, ISBN 0-521-70146-5 .
• Richard Kaye: Models of Peano arithmetic . Oxford University Press, 1991. ISBN 0-19-853213-X .

Web links

• Richard Kaye, Tennenbaum's Theorem for Models of Arithmetic (PDF file; 163 kB)

Individual evidence

1. ^ Joseph R. Shoenfield: Mathematical Logic . Addison-Wesley, 1967. 234