Teorema de Tennenbaum

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).

Estructuras recursivas para PA

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 ${\displaystyle M}$ ${\displaystyle \oplus }$ ${\displaystyle \otimes }$ ${\displaystyle \mathbb {N} \times \mathbb {N} }$ ${\displaystyle \mathbb {N} }$ ${\displaystyle \mathbb {N} }$ ${\displaystyle n_{0},n_{1}}$

${\displaystyle (\mathbb {N} ,\oplus ,\otimes ,<_{M},n_{0},n_{1})\cong M,}$

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. ${\displaystyle \cong }$ ${\displaystyle \mathbb {N} }$

Enunciado del teorema

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.

Boceto de prueba

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 . ${\displaystyle x\in M}$ ${\displaystyle S_{x}}$ ${\displaystyle p_{i}}$ ${\displaystyle z\in S_{x}\leftrightarrow M\vDash p_{z}|x}$ ${\displaystyle S_{x}}$ ${\displaystyle S_{x}}$ ${\displaystyle \{S_{x}\cap \mathbb {N} :x\in M\}}$ ${\displaystyle A,B\subseteq \mathbb {N} }$ ${\displaystyle C\subseteq \mathbb {N} }$ ${\displaystyle A\subseteq C}$ ${\displaystyle B\cap C=\emptyset }$

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 ${\displaystyle i\in A}$ ${\displaystyle p_{i}|y}$ ${\displaystyle i\in B}$ ${\displaystyle p_{i}\nmid y}$ ${\displaystyle m\in M}$ ${\displaystyle m<_{M}x}$

${\displaystyle M\vDash (m\in A\to p_{m}|y)\land (m\in B\to p_{m}\nmid y)}$

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. ${\displaystyle S=\mathbb {N} \cap S_{y}}$ ${\displaystyle A\subseteq S}$ ${\displaystyle B\cap S=\emptyset }$

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 ${\displaystyle S=\mathbb {N} \cap S_{a}}$ ${\displaystyle \oplus }$ ${\displaystyle n_{0}}$ ${\displaystyle n_{1}}$ ${\displaystyle i\in \mathbb {N} }$ ${\displaystyle n_{i}=n_{1}\oplus \cdots \oplus n_{1}}$ ${\displaystyle \mathbb {N} }$

${\displaystyle a=\underbrace {y\oplus y\oplus \cdots \oplus y} _{p{\text{ times}}}\oplus n_{i}}$

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. ${\displaystyle i<p}$ ${\displaystyle n\in S}$

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).

Grados de Turing de los modelos de PA

Jockush y Soare han demostrado que existe un modelo de AP con bajo grado . ^[1]

Referencias

• Boolos, George ; Burgess, John P.; Jeffrey , Richard (2002). Computabilidad y lógica (4.ª ed.). Cambridge University Press . ISBN 0-521-00758-5.
• Kaye, Richard (1991). Modelos de aritmética de Peano . Oxford University Press . ISBN 0-19-853213-X.
• Kaye, Richard (septiembre de 2011). "Teorema de Tennenbaum para modelos de aritmética". En Juliette Kennedy y Roman Kossak (ed.). Teoría de conjuntos, aritmética y fundamentos de las matemáticas: teoremas, filosofías (PDF) . Apuntes de clase de lógica. Vol. 36. ISBN 9781107008045.
• Tennenbaum, Stanley (1959). "Modelos no arquimedianos para la aritmética". Avisos de la American Mathematical Society . 6 : 270.

1. V. Harizanov, "Capítulo 1: Teoría de modelos computables puros" , en Handbook of Recursive Mathematics , editado por Yu. L. Ershov, SS Goncharov, A. Nerode, JB Remmel (1998, Elsevier). Capítulo 1, p.13