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.
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:
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?
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
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.
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.
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.
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.
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 .
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]
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]