Problem algebry licealnej Tarskiego

Problem algebry licealnej Tarskiego, to problem z zakresu logiki matematycznej postawiony przez Alfreda Tarskiego. Jego istotą jest kwestia istnienia takich tożsamości zawierających dodawanie, mnożenie i potęgowanie dodatnich liczb całkowitych, które nie mogą zostać udowodnione, korzystając jedynie z jedenastu aksjomatów dotyczących tych działań, zawartych w programie matematyki licealnej. Problem rozwiązał Alex Wilkie w roku 1980, pokazując, że takie tożsamości istnieją.

Wypowiedź problemu

Tarski uważał poniższe 11 aksjomatów o dodawaniu ('+'), mnożeniu ('·') i potęgowaniu za standard nauczany w liceum:

1. x + y = y + x
2. (x + y) + z = x + (y + z)
3. x · 1 = x
4. x · y = y · x
5. (x · y) · z = x · (y · z)
6. x · (y + z) = x · y + x ·z
7. 1^x = 1
8. x¹ = x
9. x^y + z = x^y · x^z
10. (x · y)^z = x^z · y^z
11. (x^y)^z = x^y · z.

Twierdzenia te, czasem nazywane tożsamościami licealnymi, są powiązane z aksjomatami pierścieni wykładniczych. Uściślony w ten sposób problem Tarskiego brzmi: czy istnieją tożsamości zawierające wyłącznie dodawanie, mnożenie oraz potęgowanie, które są prawdziwe dla każdej dodatniej liczby całkowitej, a nie da się ich dowieść, korzystając jedynie z aksjomatów 1–11?

Przykład twierdzenia możliwego do udowodnienia

Powyższe aksjomaty wydają się wyczerpywać wszystkie podstawowe fakty na temat rozważanych działań, dlatego intuicyjnie wydaje się, że dowolne stwierdzenia utworzone tylko za pomocą tych trzech operacji można udowodnić. Zupełnie inną kwestią jest długość dowodu, który nawet przy pozornie prostych twierdzeniach może być długi, jeśli rzeczywiście ograniczymy się wyłącznie do wymienionych jedenastu aksjomatów. Rozważmy następujący dowód, że (x + 1)² = x² + 2 · x + 1:

(x + 1)²

= (x + 1)^1 + 1

= (x + 1)¹ · (x + 1)¹,  (9)

= (x + 1) · (x + 1),  (8)

= (x + 1) · x + (x + 1) · 1,  (6)

= x · (x + 1) + x + 1,  (4), (3)

= x · x + x · 1 + x · 1 + 1,  (6), (3)

= x¹ · x¹ + x · (1 + 1) + 1,  (8), (6)

= x^1 + 1 + x · 2 + 1,  (9)

= x² + 2 · x + 1,  (4)

Tam, gdzie nie jest to mylące, opuszczamy nawiasy na mocy aksjomatu 2.

Długość dowodu nie jest problematyczna. Dowód podobnej tożsamości tego typu, przykładowo (x + y)¹⁰⁰, zajmowałby o wiele więcej miejsca, ale nie zawierałby koncepcji innych niż użyte wyżej.

Historia problemu

Listę jedenastu aksjomatów możemy znaleźć zapisaną jawnie w pracach Richarda Dedekinda, chociaż już dużo wcześniej były one szeroko znane wśród matematyków i uważane za oczywiste. Dedekind był pierwszym, który zwrócił uwagę, czy lista ta jest wyczerpująca, jeśli chodzi o użyteczne własności liczb całkowitych. Problem został ściśle postawiony jako dotyczący logiki i teorii modeli po roku 1960 przez Alfreda Tarskiego, a do roku 1980 był już znany jako Problem algebry licealnej Tarskiego.

Rozwiązanie

W 1980 roku Alex Wilkie udowodnił, że nie każda tożsamość może zostać udowodniona przy pomocy powyższych aksjomatów. Dokonał tego podając odpowiedni przykład. Korzystając z wprowadzonych przez siebie symboli funkcji odpowiadających wielomianom, które odwzorowują liczby dodatnie w liczby dodatnie, przeprowadził dowód tej tożsamości, a zarazem pokazał, że użyte funkcje, w połączeniu z jedenastoma powyższymi aksjomatami, są warunkiem koniecznym i wystarczającym do jego przeprowadzenia. Tożsamość jest postaci

${\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}}$

Zwykle oznacza się ją W(x,y) i jest prawdziwa dla każdych dodatnich liczb całkowitych x i y, co można pokazać rozkładając drugie wyrazy na iloczyn zawierający $(1-x+x^{2})^{xy}$. Pomimo prawdziwości, tożsamości tej nie można udowodnić używając jedenastu szkolnych aksjomatów.

W ujęciu intuicyjnym, tożsamość jest niemożliwa do udowodnienia, bo aksjomaty licealne nie mogą zostać użyte do orzekania o wielomianie $1-x+x^{2}$. Dyskusja o tym wielomianie i wyrazie $-x$ wymaga pojęcia negacji lub odejmowania, a te nie są obecne wśród aksjomatów szkolnych, a bez ich wykorzystania nie jest możliwe operowanie wymienionym wielomianem i dowodzenie jego własności. Wynik Wilkie'go wyrażony w sposób formalny w jego pracy pokazuje, że jedyną "luką" w aksjomatach licealnych jest właśnie niemożliwość operowania wielomianami o ujemnych współczynnikach.

Uogólnienia

Wilkie pokazał, że są twierdzenia o dodatnich liczbach całkowitych, które nie mogą zostać udowodnione przy użyciu powyższych jedenastu aksjomatów i wskazał jakie dodatkowe informacje są potrzebne do przeprowadzenia ich dowodów. Korzystając z teori Nevanlinna można również dowieść, że jeśli ograniczymy się do pewnych klas funkcji wykładniczych, to aksjomaty szkolne są wystarczające do udowodnienia każdego prawdziwego twierdzenia tego typu.

Innym wciąż otwartym problemem wynikającym z rezultatu Wilkie'go jest wskazanie najmniejszej algebry takiej, dla której W(x, y) nie jest prawdziwa, jednak aksjomaty szkolne są. W roku 1985 wskazano odpowiednią algebrę 59-elementową. Od tej pory znaleziono też mniejsze algebry i znany jest fakt, że najmniejsza musi mieć 11 albo 12 elementów.

Bibliografia

• Stanley N. Burris, Karen A. Yeats, The saga of the high school identities, Algebra Universalis 52 no.2–3, (2004), pp. 325–342, MR2161657.