En matemáticas , la aritmética de Robinson es un fragmento finitamente axiomatizado de la aritmética de Peano (PA) de primer orden , establecida por primera vez por Raphael M. Robinson en 1950. [1] Generalmente se denota Q. Q es casi [ aclaración necesaria ] PA sin el esquema axiomático de inducción matemática . Q es más débil que PA pero tiene el mismo lenguaje, y ambas teorías son incompletas . Q es importante e interesante porque es un fragmento finitamente axiomatizado de PA que es recursivamente incompletable y esencialmente indecidible .
La lógica de fondo de Q es lógica de primer orden con identidad , denotada por el infijo '='. Los individuos, llamados números naturales , son miembros de un conjunto llamado N con un miembro distinguido 0 , llamado cero . Hay tres operaciones sobre N :
Los siguientes axiomas para Q son Q1–Q7 en Burgess (2005, p. 42) (cf. también los axiomas de la aritmética de primer orden ). Las variables no limitadas por un cuantificador existencial están limitadas por un cuantificador universal implícito .
Los axiomas de Robinson (1950) son (1)–(13) en Mendelson (2015, pp. 202–203). Los primeros 6 de los 13 axiomas de Robinson son necesarios solo cuando, a diferencia de aquí, la lógica de fondo no incluye la identidad.
El orden total estricto habitual en N , "menor que" (denotado por "<"), se puede definir en términos de adición a través de la regla x < y ↔ ∃ z ( Sz + x = y ) . De manera equivalente, obtenemos una extensión conservadora definicional de Q al tomar "<" como primitivo y agregar esta regla como un octavo axioma; este sistema se denomina " aritmética de Robinson R " en Boolos, Burgess y Jeffrey (2002, Sec 16.4).
Una extensión diferente de Q , que temporalmente llamamos Q+ , se obtiene si tomamos "<" como primitivo y agregamos (en lugar del último axioma definicional) los siguientes tres axiomas a los axiomas (1)–(7) de Q :
Q+ sigue siendo una extensión conservadora de Q , en el sentido de que cualquier fórmula demostrable en Q+ que no contenga el símbolo "<" ya es demostrable en Q . (Añadir sólo los dos primeros de los tres axiomas anteriores a Q da una extensión conservadora de Q que es equivalente a lo que Burgess (2005, p. 56) llama Q* . Véase también Burgess (2005, p. 230, nota al pie 24), pero tenga en cuenta que el segundo de los tres axiomas anteriores no puede deducirse de "la extensión definicional pura" de Q obtenida añadiendo sólo el axioma x < y ↔ ∃ z ( Sz + x = y ) .)
Entre los axiomas (1)–(7) de Q , el axioma (3) necesita un cuantificador existencial interno. Shoenfield (1967, p. 22) da una axiomatización que tiene solo cuantificadores universales externos (implícitos), al prescindir del axioma (3) de Q pero agregar los tres axiomas anteriores con < como primitivo. Es decir, el sistema de Shoenfield es Q+ menos el axioma (3), y es estrictamente más débil que Q+ , ya que el axioma (3) es independiente de los otros axiomas (por ejemplo, los ordinales menores que forman un modelo para todos los axiomas excepto (3) cuando Sv se interpreta como v + 1). El sistema de Shoenfield también aparece en Boolos, Burgess y Jeffrey (2002, Sec 16.2), donde se lo llama " aritmética mínima " (también denotada por Q ). Una axiomatización estrechamente relacionada, que utiliza "≤" en lugar de "<", se puede encontrar en Machover (1996, pp. 256-257).
Sobre la metamatemática de Q , véase Boolos, Burgess y Jeffrey (2002, cap. 16), Tarski, Mostowski y Robinson (1953), Smullyan (1991), Mendelson (2015, pp. 202-203) y Burgess (2005, §§1.5a, 2.2). La interpretación pretendida de Q son los números naturales y su aritmética habitual en la que la adición y la multiplicación tienen su significado habitual, la identidad es igualdad , Sx = x + 1 y 0 es el número natural cero .
Cualquier modelo (estructura) que satisface todos los axiomas de Q excepto posiblemente el axioma (3) tiene un submodelo único ("la parte estándar") isomorfo a los números naturales estándar ( N , +, ·, S, 0) . (El axioma (3) no necesita ser satisfecho; por ejemplo, los polinomios con coeficientes enteros no negativos forman un modelo que satisface todos los axiomas excepto (3).)
Q , al igual que la aritmética de Peano , tiene modelos no estándar de todas las cardinalidades infinitas . Sin embargo, a diferencia de la aritmética de Peano, el teorema de Tennenbaum no se aplica a Q , y tiene modelos no estándar computables. Por ejemplo, hay un modelo computable de Q que consiste en polinomios de coeficientes enteros con coeficiente principal positivo, más el polinomio cero, con su aritmética habitual.
Una característica notable de Q es la ausencia del esquema axiomático de inducción . Por lo tanto, a menudo es posible probar en Q cada instancia específica de un hecho sobre los números naturales, pero no el teorema general asociado. Por ejemplo, 5 + 7 = 7 + 5 es demostrable en Q , pero el enunciado general x + y = y + x no lo es. De manera similar, no se puede probar que Sx ≠ x . [2] Un modelo de Q que falla en muchos de los hechos estándar se obtiene añadiendo dos nuevos elementos distintos a y b al modelo estándar de números naturales y definiendo Sa = a , Sb = b , x + a = b y x + b = a para todo x , a + n = a y b + n = b si n es un número natural estándar, x · 0 = 0 para todo x , a · n = b y b · n = a si n es un número natural estándar distinto de cero, x · a = a para todo x excepto x = a , x · b = b para todo x excepto x = b , a · a = b y b · b = a . [3]
Q es interpretable en un fragmento de la teoría de conjuntos axiomáticos de Zermelo , que consiste en extensionalidad , existencia del conjunto vacío y el axioma de adjunción . Esta teoría es S' en Tarski, Mostowski y Robinson (1953, p. 34) y ST en Burgess (2005, pp. 90–91, 223). Véase la teoría general de conjuntos para más detalles.
Q es una teoría de primer orden finitamente axiomatizada que es considerablemente más débil que la aritmética de Peano (PA), y cuyos axiomas contienen solo un cuantificador existencial . Sin embargo, al igual que PA, es incompleta e incompletable en el sentido de los teoremas de incompletitud de Gödel , y esencialmente indecidible. Robinson (1950) derivó los axiomas Q (1)–(7) anteriores al señalar exactamente qué axiomas PA se requieren [4] para demostrar que toda función computable es representable en PA. [5] El único uso que esta prueba hace del esquema axiomático PA de inducción es demostrar una afirmación que es el axioma (3) anterior y, por lo tanto , todas las funciones computables son representables en Q. [6] [7] [8] La conclusión del segundo teorema de incompletitud de Gödel también es válida para Q : ninguna extensión recursivamente axiomatizada consistente de Q puede demostrar su propia consistencia, incluso si además restringimos los números de pruebas de Gödel a un corte definible. [9] [10] [11]
El primer teorema de incompletitud se aplica únicamente a sistemas axiomáticos que definen la aritmética suficiente para llevar a cabo las construcciones de codificación necesarias (de las cuales la numeración de Gödel forma parte). Los axiomas de Q se eligieron específicamente para garantizar que sean lo suficientemente fuertes para este propósito. Por lo tanto, la prueba habitual del primer teorema de incompletitud se puede utilizar para mostrar que Q es incompleta e indecidible. Esto indica que la incompletitud e indecidibilidad de PA no se puede achacar al único aspecto de PA que lo diferencia de Q , es decir, el esquema axiomático de inducción .
Los teoremas de Gödel no se cumplen cuando se descarta cualquiera de los siete axiomas anteriores. Estos fragmentos de Q siguen siendo indecidibles, pero ya no son esencialmente indecidibles: tienen extensiones decidibles consistentes, así como modelos sin interés (es decir, modelos que no son extensiones finales de los números naturales estándar). [ cita requerida ]
