Problema de álgebra de secundaria de Tarski

En lógica matemática , el problema de álgebra de secundaria de Tarski fue una pregunta planteada por Alfred Tarski . Pregunta si existen identidades que involucran adición , multiplicación y exponenciación sobre los números enteros positivos que no se pueden demostrar utilizando once axiomas sobre estas operaciones que se enseñan en matemáticas de nivel secundario . La pregunta fue resuelta en 1980 por Alex Wilkie , quien demostró que tales identidades no demostrables existen.

Planteamiento del problema

Tarski consideró que los siguientes once axiomas sobre la suma ('+'), la multiplicación ('·') y la exponenciación eran axiomas estándar enseñados en la escuela secundaria:

x + y = y + x
( x + y ) + z = x + ( y + z )
x · 1 = x
x · y = y · x
( x · y ) · z = x · ( y · z )
x ·( y + z ) = x · y + x · z
1x ⁼ 1
x1 = x
x ^{y + z} = x ^y · x ^z
( x · y ) ^z = x ^z · y ^z
( x ^y ) ^z = x ^{y · z}

Estos once axiomas, a veces llamados identidades de la escuela secundaria , ^[1] están relacionados con los axiomas de una categoría cerrada bicartesiana o un anillo exponencial . ^[2] El problema de Tarski entonces se convierte en: ¿existen identidades que involucran solo suma, multiplicación y exponenciación, que son verdaderas para todos los números enteros positivos, pero que no se pueden demostrar usando solo los axiomas 1-11?

Ejemplo de una identidad demostrable

Dado que los axiomas parecen enumerar todos los hechos básicos sobre las operaciones en cuestión, no resulta inmediatamente obvio que deba existir algo demostrablemente verdadero que se pueda afirmar utilizando sólo las tres operaciones, pero que no se pueda demostrar con los axiomas. Sin embargo, demostrar afirmaciones aparentemente inocuas puede requerir largas demostraciones utilizando sólo los once axiomas anteriores. Considere la siguiente demostración de que $(x+1)^{2}=x^{2}+2\cdot x+1:$

${\begin{aligned}(x+1)^{2}&=(x+1)^{1+1}\\&=(x+1)^{1}\cdot (x+1)^{1}&&{\text{by 9.}}\\&=(x+1)\cdot (x+1)&&{\text{by two applications of 8.}}\\&=(x+1)\cdot x+(x+1)\cdot 1&&{\text{by 6.}}\\&=x\cdot (x+1)+(x+1)&&{\text{by 4. and 3.}}\\&=(x\cdot x+x\cdot 1)+(x\cdot 1+1)&&{\text{by 6. and 3.}}\\&=x\cdot x+(x\cdot 1+x\cdot 1)+1&&{\text{by two applications of 2.}}\\&=x^{1}\cdot x^{1}+x\cdot (1+1)+1&&{\text{by 6. and two applications of 8.}}\\&=x^{1+1}+x\cdot 2+1&&{\text{by 9.}}\\&=x^{2}+2\cdot x+1&&{\text{by 4.}}\end{aligned}}$

Estrictamente no deberíamos escribir sumas de más de dos términos sin paréntesis, y por lo tanto una prueba completamente formal probaría la identidad (o ) y tendría un conjunto extra de paréntesis en cada línea de ahí en adelante. $(x+1)^{2}=\left(x^{2}+2\cdot x\right)+1$ $(x+1)^{2}=x^{2}+(2\cdot x+1)$ $x\cdot x+(x\cdot 1+x\cdot 1)+1$

La longitud de las pruebas no es un problema; pruebas de identidades similares a la anterior para cosas como tomarían muchas líneas, pero en realidad implicarían poco más que la prueba anterior. $(x+y)^{100}$

Historia del problema

La lista de once axiomas se puede encontrar escrita explícitamente en las obras de Richard Dedekind ^[3] , aunque obviamente eran conocidos y utilizados por los matemáticos mucho antes. Sin embargo, Dedekind fue el primero que pareció preguntarse si estos axiomas eran de alguna manera suficientes para decirnos todo lo que podríamos querer saber sobre los números enteros. La cuestión fue planteada como un problema de lógica y teoría de modelos en algún momento de la década de 1960 por Alfred Tarski ^[1]^[4] , y en la década de 1980 ya se conocía como el problema de álgebra de secundaria de Tarski.

Solución

En 1980, Alex Wilkie demostró que no todas las identidades en cuestión pueden demostrarse utilizando los axiomas anteriores. ^[5] Lo hizo encontrando explícitamente dicha identidad. Al introducir nuevos símbolos de función correspondientes a polinomios que asignan números positivos a números positivos, demostró esta identidad y mostró que estas funciones junto con los once axiomas anteriores eran suficientes y necesarios para demostrarla. La identidad en cuestión es Esta identidad generalmente se denota y es verdadera para todos los números enteros positivos y como se puede ver al factorizar el segundo factor en cada lado; sin embargo, no se puede demostrar que es verdadera utilizando los once axiomas de la escuela secundaria. ${\begin{aligned}&\left((1+x)^{y}+(1+x+x^{2})^{y}\right)^{x}\cdot \left((1+x^{3})^{x}+(1+x^{2}+x^{4})^{x}\right)^{y}\\={}&\left((1+x)^{x}+(1+x+x^{2})^{x}\right)^{y}\cdot \left((1+x^{3})^{y}+(1+x^{2}+x^{4})^{y}\right)^{x}.\end{aligned}}$ $W(x,y)$ $x$ $y,$ $(1-x+x^{2})^{xy}$

Intuitivamente, la identidad no se puede probar porque los axiomas de la escuela secundaria no se pueden usar para discutir el polinomio. El razonamiento sobre ese polinomio y el subtérmino requiere un concepto de negación o resta , y estos no están presentes en los axiomas de la escuela secundaria. Al carecer de esto, es imposible usar los axiomas para manipular el polinomio y probar propiedades verdaderas sobre él. Los resultados de Wilkie de su artículo muestran, en un lenguaje más formal, que la "única brecha" en los axiomas de la escuela secundaria es la incapacidad de manipular polinomios con coeficientes negativos . $1-x+x^{2}.$ $-x$

R. Gurevič demostró en 1988 que no existe una axiomatización finita para las ecuaciones válidas para los números naturales positivos con 1, adición, multiplicación y exponenciación. ^[6]^[7]

Generalizaciones

Wilkie demostró que hay afirmaciones sobre los números enteros positivos que no se pueden demostrar utilizando los once axiomas anteriores y mostró qué información adicional se necesita para poder demostrar dichas afirmaciones. Utilizando la teoría de Nevanlinna también se ha demostrado que si se restringen los tipos de exponenciales que se toman, los once axiomas anteriores son suficientes para demostrar cada afirmación verdadera. ^[8]

Otro problema que se deriva del resultado de Wilkie, que sigue abierto, es el que plantea la pregunta de cuál es la álgebra más pequeña para la cual no es verdadera pero sí lo son los once axiomas anteriores. En 1985 se encontró una álgebra con 59 elementos que satisfacía los axiomas pero para la cual era falsa. ^[4] Desde entonces se han encontrado álgebras más pequeñas de este tipo, y ahora se sabe que la más pequeña de ellas debe tener 11 o 12 elementos. ^[9] $W(x,y)$ $W(x,y)$

Véase también

Función elemental – Función matemática
Aritmética de funciones elementales – Sistema de aritmética en la teoría de la demostración
Teorema de Liouville (álgebra diferencial) : dice cuándo las antiderivadas de funciones elementales pueden expresarse como funciones elementales.
Integral no elemental – Integrales que no se pueden expresar en forma cerrada a partir de funciones elementales
Teorema de Richardson – Indecidibilidad de la igualdad de números reales

Notas

^ ab Stanley Burris, Simon Lee, Las identidades de Tarski en la escuela secundaria , American Mathematical Monthly , 100 , (1993), n.º 3, págs. 231–236.
^ Estrictamente hablando, un anillo exponencial tiene una función exponencial E que lleva cada elemento x a algo que actúa como una ^x para un número fijo a . Pero una ligera generalización proporciona los axiomas para la operación binaria de exponenciación. La falta de axiomas sobre inversos aditivos significa que los axiomas habrían descrito un semianillo conmutativo exponencial , excepto que tampoco hay axiomas sobre identidades aditivas en los axiomas de Tarski. Sin embargo, algunos autores usan el término rig para referirse a un semianillo con identidades aditivas, y reservan el término semianillo para el caso general que no necesariamente tiene identidades aditivas. Para esos autores, los axiomas describen un semianillo conmutativo exponencial.
^ Richard Dedekind, ¿Fue sind y fue sollen die Zahlen? , 8te unveränderte Aufl. Friedr. Vieweg y Sohn, Braunschweig (1960). Traducción al inglés: ¿Qué son los números y cuáles deberían ser? Revisado, editado y traducido del alemán por HA Pogorzelski , W. Ryan y W. Snyder, RIM Monographs in Mathematics, Research Institute for Mathematics, (1995).
^ ab R. Gurevič, Teoría ecuacional de números positivos con exponenciación , Proc. Amer. Math. Soc. 94 no.1, (1985), pp.135–141.
^ AJ Wilkie, Sobre la exponenciación: una solución al problema de álgebra de secundaria de Tarski , Conexiones entre la teoría de modelos y la geometría algebraica y analítica, Quad. Mat., 6 , Dept. Math., Seconda Univ. Napoli, Caserta, (2000), págs. 107-129.
^ R. Gurevič, La teoría de ecuaciones de números positivos con exponenciación no es finitamente axiomatizable , Annals of Pure and Applied Logic, 49:1–30, 1990.
^ Fiore, Cosmo y Balat. Observaciones sobre isomorfismos en cálculos lambda tipificados con tipos vacíos y suma [1]
^ C. Ward Henson, Lee A. Rubel, Algunas aplicaciones de la teoría de Nevanlinna a la lógica matemática: Identidades de funciones exponenciales , Transactions of the American Mathematical Society , vol. 282 1 , (1984), págs. 1–32.
^ Jian Zhang, Búsqueda por computadora de contraejemplos a la identidad de Wilkie , Deducción automática – CADE-20, Springer (2005), págs. 441–451, doi :10.1007/11532231_32.

Referencias

Stanley N. Burris, Karen A. Yeats , La saga de las identidades de la escuela secundaria , Algebra Universalis 52 no.2–3, (2004), pp. 325–342, MR 2161657.