Aritmética de funciones elementales

Sistema de aritmética en la teoría de la prueba.

En la teoría de la prueba , una rama de la lógica matemática , la aritmética de funciones elementales ( EFA ), también llamada aritmética elemental y aritmética de funciones exponencial , ^[1] es el sistema de aritmética con las propiedades elementales habituales de 0, 1, +, ×,,  juntas con inducción para fórmulas con cuantificadores acotados . ${\displaystyle x^{y}}$

EFA es un sistema lógico muy débil, cuya prueba teórica es ordinal , pero aún parece capaz de probar gran parte de las matemáticas ordinarias que pueden expresarse en el lenguaje de la aritmética de primer orden . ${\displaystyle \omega ^{3}}$

Definición

EFA es un sistema en lógica de primer orden (con igualdad). Su lenguaje contiene:

• dos constantes , , ${\displaystyle 0}$ ${\displaystyle 1}$
• tres operaciones binarias , , , generalmente escritas como , ${\displaystyle +}$ ${\displaystyle \times }$ ${\displaystyle {\textrm {exp}}}$ ${\displaystyle {\textrm {exp}}(x,y)}$ ${\displaystyle x^{y}}$
• un símbolo de relación binaria (esto no es realmente necesario ya que se puede escribir en términos de otras operaciones y a veces se omite, pero es conveniente para definir cuantificadores acotados). ${\displaystyle <}$

Los cuantificadores acotados son aquellos de la forma y que son abreviaturas de y en la forma habitual. ${\displaystyle \forall (x<y)}$ ${\displaystyle \exists (x<y)}$ ${\displaystyle \forall x(x<y)\rightarrow \ldots }$ ${\displaystyle \exists x(x<y)\land \ldots }$

Los axiomas de EFA son

• Los axiomas de la aritmética de Robinson para , , , , ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle +}$ ${\displaystyle \times }$ ${\displaystyle <}$
• Los axiomas de exponenciación: , . ${\displaystyle x^{0}=1}$ ${\displaystyle x^{y+1}=x^{y}\times x}$
• Inducción para fórmulas cuyos cuantificadores están acotados (pero que pueden contener variables libres).

La gran conjetura de Friedman

La gran conjetura de Harvey Friedman implica que muchos teoremas matemáticos, como el último teorema de Fermat , pueden demostrarse en sistemas muy débiles como EFA.

La declaración original de la conjetura de Friedman (1999) es:

"Cada teorema publicado en Annals of Mathematics cuyo enunciado involucra sólo objetos matemáticos finitos (es decir, lo que los lógicos llaman un enunciado aritmético) puede demostrarse en EFA. EFA es el fragmento débil de la Aritmética de Peano basado en los axiomas habituales sin cuantificadores para 0 , 1, +, ×, exp, junto con el esquema de inducción para todas las fórmulas del lenguaje cuyos cuantificadores están acotados."

Si bien es fácil construir enunciados aritméticos artificiales que sean verdaderos pero no demostrables en EFA, el punto de la conjetura de Friedman es que los ejemplos naturales de tales enunciados en matemáticas parecen ser raros. Algunos ejemplos naturales incluyen enunciados de consistencia de la lógica, varios enunciados relacionados con la teoría de Ramsey , como el lema de regularidad de Szemerédi , y el teorema del grafo menor .

Sistemas relacionados

Varias clases de complejidad computacional relacionadas tienen propiedades similares a EFA:

• Se puede omitir el símbolo de la función binaria exp del lenguaje, tomando la aritmética de Robinson junto con la inducción para todas las fórmulas con cuantificadores acotados y un axioma que establezca aproximadamente que la exponenciación es una función definida en todas partes. Esto es similar a EFA y tiene la misma solidez teórica de prueba, pero es más complicado trabajar con él.
• Hay fragmentos débiles de aritmética de segundo orden llamados y que son conservadores sobre EFA para oraciones (es decir, cualquier oración probada o ya probada por EFA). ^[2] En particular, son conservadores para declaraciones de coherencia. Estos fragmentos a veces se estudian en matemáticas inversas (Simpson 2009). ${\displaystyle {\mathsf {RCA}}_{0}^{*}}$ ${\displaystyle {\mathsf {WKL}}_{0}^{*}}$ ${\displaystyle \Pi _{2}^{0}}$ ${\displaystyle \Pi _{2}^{0}}$ ${\displaystyle {\mathsf {RCA}}_{0}^{*}}$ ${\displaystyle {\mathsf {WKL}}_{0}^{*}}$
• La aritmética recursiva elemental ( ERA ) es un subsistema de la aritmética recursiva primitiva (PRA) en el que la recursividad está restringida a sumas y productos acotados . Esto también tiene las mismas oraciones que EFA, en el sentido de que siempre que EFA prueba ∀x∃y P ( x , y ), con P libre de cuantificadores, ERA prueba la fórmula abierta P ( x , T ( x )), con T un término definible en ERA. Al igual que PRA, ERA se puede definir de una manera totalmente libre de lógica ^{[ se necesita aclaración ]} , con solo las reglas de sustitución e inducción, y definiendo ecuaciones para todas las funciones recursivas elementales. Sin embargo, a diferencia de PRA, las funciones recursivas elementales pueden caracterizarse por el cierre bajo composición y proyección de un número finito de funciones básicas y, por lo tanto, solo se necesita un número finito de ecuaciones definitorias. ${\displaystyle \Pi _{2}^{0}}$

Ver también

• Función elemental  – Función matemática
• Jerarquía de Grzegorczyk  : funciones en la teoría de la computabilidad
• Matemáticas inversas  - Rama de la lógica matemática
• Análisis ordinal  : técnica matemática utilizada en la teoría de la prueba.
• Problema de álgebra de la escuela secundaria de Tarski  - Problema matemático

Referencias

1. C. Smoryński, "Modelos no estándar y desarrollos relacionados" (p. 217). De la investigación de Harvey Friedman sobre los fundamentos de las matemáticas (1985), Estudios de lógica y los fundamentos de las matemáticas vol. 117.
2. SG Simpson, RL Smith, "Factorización de polinomios e inducción Σ 1 0 {\displaystyle \Sigma _{1}^{0}}" (1986). Anales de lógica pura y aplicada, vol. 31 (p.305)

• Avigad, Jeremy (2003), "Teoría de números y aritmética elemental", Philosophia Mathematica , Serie III, 11 (3): 257–284, doi :10.1093/philmat/11.3.257, ISSN  0031-8019, MR  2006194
• Friedman, Harvey (1999), grandes conjeturas
• Simpson, Stephen G. (2009), Subsistemas de aritmética de segundo orden, Perspectives in Logic (2ª ed.), Cambridge University Press , ISBN 978-0-521-88439-6, señor  1723993