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 contable no estándar 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. Hay muchos modelos no estándar contables no isomórficos de PA. ${\displaystyle \cong }$ ${\displaystyle \mathbb {N} }$

Declaración del teorema

El teorema de Tennenbaum establece que ningún modelo no estándar contable de PA es recursivo. Además, ni la suma ni la multiplicación de dicho modelo pueden ser recursivas.

Bosquejo de prueba

Este esbozo sigue el argumento presentado por Kaye (1991). El primer paso en la demostración es mostrar que, si M es cualquier modelo no estándar contable 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 suma o multiplicación en 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 verse 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 AP contiene un conjunto no recursivo, ya sea apelando al teorema de incompletitud o considerando directamente un par de reconjuntos recursivamente inseparables (Kaye 1991:154). Estos son restablecimientos separados, por lo que no hay ningún 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 reinicios A y B recursivamente inseparables . Para el número natural x existe una y tal que, para todo i < x , si entonces y si entonces . Por la propiedad de desbordamiento , esto significa que hay alguna x no estándar en M para la cual hay una 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 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 que no sea recursivo. El método de prueba 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 suma de M como oráculo. En particular, si el elemento de M corresponde a 0 y el elemento de M corresponde a 1, entonces para cada uno podemos calcular ( i veces). Para decidir si un número n está en S , primero calcula p , el n- ésimo primo en . Luego, busque un elemento y de M tal 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 AP. Finalmente, tenemos si y sólo si la i encontrada en la búsqueda fue 0. Como 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 en M tampoco es recursiva (Kaye 1991:154).

Grados de Turing de modelos de PA.

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

Referencias

• Boolos, George ; Burgess, John P .; Jeffrey, Richard (2002). Computabilidad y Lógica (4ª ed.). Prensa de la Universidad de Cambridge . ISBN 0-521-00758-5.
• Kaye, Richard (1991). Modelos de aritmética de Peano . Prensa de la Universidad de Oxford . 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 conferencias sobre lógica. vol. 36.ISBN​ 9781107008045.
• Tennenbaum, Stanley (1959). "Modelos aritméticos no de Arquímedes". Avisos de la Sociedad Matemática Estadounidense . 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