El teorema de Tennenbaum , llamado así por Stanley Tennenbaum , quien presentó el teorema en 1959, es un resultado de la lógica matemática que establece que ningún modelo no estándar contable de aritmética de Peano (PA) de primer orden puede ser recursivo (Kaye 1991:153ff).
Una estructura en el lenguaje de PA es recursiva si hay funciones recursivas y de a , una relación recursiva de dos lugares < M en , y constantes distinguidas tales que
donde indica isomorfismo y es el conjunto de números naturales (estándar) . Debido a que el isomorfismo debe ser una biyección , todo modelo recursivo es contable. Existen muchos modelos no estándar contables no isomorfos de PA.
El teorema de Tennenbaum establece que ningún modelo numerable no estándar de PA es recursivo. Además, ni la adición ni la multiplicación de un modelo de este tipo pueden ser recursivas.
Este esquema sigue el argumento presentado por Kaye (1991). El primer paso de la prueba es mostrar que, si M es cualquier modelo no estándar numerable de PA, entonces el sistema estándar de M (definido a continuación) contiene al menos un conjunto no recursivo S . El segundo paso es mostrar que, si la operación de adición o multiplicación sobre M fuera recursiva, entonces este conjunto S sería recursivo, lo cual es una contradicción.
A través de los métodos utilizados para codificar tuplas ordenadas, cada elemento puede ser visto como un código para un conjunto de elementos de M . En particular, si dejamos que sea el i ésimo primo en M , entonces . Cada conjunto estará acotado en M , pero si x no es estándar, entonces el conjunto puede contener infinitos números naturales estándar. El sistema estándar del modelo es la colección . Se puede demostrar que el sistema estándar de cualquier modelo no estándar de PA contiene un conjunto no recursivo, ya sea apelando al teorema de incompletitud o considerando directamente un par de conjuntos re recursivamente inseparables (Kaye 1991:154). Estos son conjuntos re disjuntos de modo que no hay un conjunto recursivo con y .
Para la última construcción, comience con un par de resets recursivamente inseparables A y B . Para el número natural x existe un y tal que, para todo i < x , si entonces y si entonces . Por la propiedad de desbordamiento , esto significa que hay algún x no estándar en M para el cual hay un y (necesariamente no estándar) en M de modo que, para cada con , tenemos
Sea el conjunto correspondiente en el sistema estándar de M . Como A y B son re, se puede demostrar que y . Por lo tanto, S es un conjunto separador para A y B , y por la elección de A y B esto significa que S no es recursivo.
Ahora, para demostrar el teorema de Tennenbaum, comencemos con un modelo contable no estándar M y un elemento a en M de modo que no sea recursivo. El método de demostración muestra que, debido a la forma en que se define el sistema estándar, es posible calcular la función característica del conjunto S utilizando la función de adición de M como un oráculo. En particular, si es el elemento de M correspondiente a 0, y es el elemento de M correspondiente a 1, entonces para cada uno podemos calcular ( i veces). Para decidir si un número n está en S , primero calcule p , el n º primo en . Luego, busque un elemento y de M de modo que
para algunos . Esta búsqueda se detendrá porque el algoritmo euclidiano se puede aplicar a cualquier modelo de PA. Finalmente, tenemos si y solo si el i encontrado en la búsqueda fue 0. Debido a que S no es recursivo, esto significa que la operación de suma en M no es recursiva.
Un argumento similar muestra que es posible calcular la función característica de S usando la multiplicación de M como oráculo, por lo que la operación de multiplicación de M también es no recursiva (Kaye 1991:154).
Jockush y Soare han demostrado que existe un modelo de AP con bajo grado . [1]