En matemáticas , la aritmética de Robinson es un fragmento finitamente axiomatizado de la aritmética de Peano (PA) de primer orden , expuesta por primera vez por Raphael M. Robinson en 1950. [1] Generalmente se denota como Q. Q es casi [ se necesita aclaración ] PA sin el esquema axiomático de la inducción matemática . Q es más débil que PA pero tiene el mismo lenguaje y ambas teorías están incompletas . Q es importante e interesante porque es un fragmento finitamente axiomatizado de PA que es recursivamente incompleto 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 que no están 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, págs. 202-203). Los primeros 6 de los 13 axiomas de Robinson son necesarios sólo 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 suma mediante la regla x < y ↔ ∃ z ( Sz + x = y ) . De manera equivalente, obtenemos una extensión conservadora definitoria de Q tomando "<" como primitivo y agregando esta regla como un octavo axioma; este sistema se denomina " aritmética R de Robinson " en Boolos, Burgess y Jeffrey (2002, sección 16.4).
Se obtiene una extensión diferente de Q , a la que temporalmente llamamos Q+ , si tomamos "<" como primitivo y sumamos (en lugar del último axioma definitorio) 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 . (Agregar solo 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 24). , pero tenga en cuenta que el segundo de los tres axiomas anteriores no se puede deducir de "la extensión definicional pura" de Q obtenida sumando sólo el axioma x < y ↔ ∃ z ( Sz + x = y ) .)
Entre los axiomas (1) a (7) de Q , el axioma (3) necesita un cuantificador existencial interno. Shoenfield (1967, p. 22) ofrece una axiomatización que sólo tiene cuantificadores universales externos (implícitos), prescindiendo del axioma (3) de Q pero añadiendo 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, sección 16.2), donde se le 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, págs. 256-257).
Sobre las metamatemáticas de Q , véase Boolos, Burgess y Jeffrey (2002, cap. 16), Tarski, Mostowski y Robinson (1953), Smullyan (1991), Mendelson (2015, págs. 202-203) y Burgess (2005, §§ 1.5a, 2.2). La interpretación prevista de Q son los números naturales y su aritmética habitual en la que la suma y la multiplicación tienen su significado habitual, la identidad es la igualdad , Sx = x + 1 y 0 es el número natural cero .
Cualquier modelo (estructura) que satisfaga 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) . (No es necesario satisfacer el axioma (3); por ejemplo, los polinomios con coeficientes enteros no negativos forman un modelo que satisface todos los axiomas excepto (3).)
Q , como 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 computables no estándar. Por ejemplo, existe un modelo computable de Q que consta de 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 tanto, a menudo es posible demostrar en Q cada caso específico 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 la afirmación general x + y = y + x no lo es. De manera similar, no se puede probar que Sx ≠ x . [2] Un modelo de Q que no cumple con muchos de los hechos estándar se obtiene uniendo 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 a número natural estándar distinto de cero, x · a = a para todos los x excepto x = a , x · b = b para todos los x excepto x = b , a · a = b y b · b = a . [3]
Q es interpretable en un fragmento de la teoría axiomática de conjuntos de Zermelo , que consiste en la extensionalidad , la 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). Consulte la teoría general de conjuntos para obtener 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 sólo un cuantificador existencial . Sin embargo, al igual que PA, es incompleto e incompleto en el sentido de los teoremas de incompletitud de Gödel , y esencialmente indecidible. Robinson (1950) derivó los axiomas Q (1) a (7) anteriores observando 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 de inducción del axioma PA es probar un enunciado 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 axiomatizada recursivamente consistente de Q puede probar su propia consistencia, incluso si restringimos adicionalmente el número de pruebas de Gödel a un corte definible. [9] [10] [11]
El primer teorema de incompletitud se aplica sólo a sistemas axiomáticos que definen suficiente aritmética 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 sólidos para este propósito. Por tanto, se puede utilizar la demostración habitual del primer teorema de incompletitud para demostrar que Q es incompleto e indecidible. Esto indica que la incompletitud y la indecidibilidad de PA no pueden atribuirse 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 elimina 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 poco interesantes (es decir, modelos que no son extensiones finales de los números naturales estándar). [ cita necesaria ]
