Tennenbaum's theorem

Tennenbaum's theorem Not to be confused with Tennenbaum's construction of a computable copy of {displaystyle omega +omega ^{*}} having no computable infinite ascending or descending chains.

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 first-order Peano arithmetic (PA) can be recursive (Kaye 1991:153ff).

Contents 1 Recursive structures for PA 2 Statement of the theorem 3 Proof sketch 4 References Recursive structures for PA A structure {displaystyle M} in the language of PA is recursive if there are recursive functions {displaystyle oplus } and {displaystyle otimes } from {displaystyle mathbb {N} times mathbb {N} } to {displaystyle mathbb {N} } , a recursive two-place relation

Si quieres conocer otros artículos parecidos a Tennenbaum's theorem puedes visitar la categoría Model theory.