Tarski's high school algebra problem

Template:More citations neededTemplate:Short description In mathematical logic, Tarski's high school algebra problem is a question posed by Alfred Tarski. It asks whether there are identities involving addition, multiplication, and exponentiation over the positive integers that cannot be proved using eleven axioms about these operations that are taught in high-school-level mathematics. The question was solved in 1980 by Alex Wilkie, who showed that such unprovable identities do exist.

Tarski's problem more formally asks if the equational theory of the High School Axioms ${\text{Th}}_{Eq}(\mathrm{H}\mathrm{S})$ (that is, the set of identities provable from them in equational logic) is equal to the equational theory of ${ℝ}_{\ge 0}$ (that is, the set of all true identities).

This turns out to be analogous to Hilbert's program and Gödel's incompleteness theorem in the 1920s and 1930s. First, note that Garrett Birkhoff proved with his HSP theorem that the equational theory of ${ℝ}_{\ge 0}$ is equal to the equational theory of all commutative semirings, in particular the equational theory of $\mathbb{N}$. In other words, to test if an identity is true one only needs to test it for natural numbers.

Then, one can ask if the first-order theory of some finite set of axioms (that is, the set of formulas provable from them in first-order logic) is equal to the first-order theory of the natural numbers, $\text{Th}(\mathbb{N})$ (that is, the set of all true formulas). In Tarski's question the goal is for ${\text{Th}}_{Eq}(\mathrm{H}\mathrm{S})={\text{Th}}_{Eq}(\mathbb{N})$; in Hilbert's question the goal is for a theory $T$ for which $\text{Th}(T)=\text{Th}(\mathbb{N})$.

In both cases this does not work out. Gödel's first incompleteness theorem, which shows that $\text{Th}(\mathbb{N})$ is not computably axiomatizable, is then analogous to Wilkie and Ruben H. Gurevič's results that the equational theory is not finitely axiomatizable.Template:Citation needed

Statement of the problem

Tarski considered the following eleven axioms about addition $(+)$, multiplication $(\cdot )$, and exponentiation involving positive integers to be standard axioms taught in high school: $$\begin{array}{cccc}& (1)& x+y& =y+x\\ & (2)& (x+y)+z& =x+(y+z)\\ & (3)& x\cdot 1& =x\\ & (4)& x\cdot y& =y\cdot x\\ & (5)& (x\cdot y)\cdot z& =x\cdot (y\cdot z)\\ & (6)& x\cdot (y+z)& =x\cdot y+x\cdot z\\ & (7)& 1^x& =1\\ & (8)& x^1& =x\\ & (9)& x^{y+z}& =x^y\cdot x^z\\ & (10)& (x\cdot y{)}^z& =x^z\cdot y^z\\ & (11)& (x^y{)}^z& =x^{y\cdot z}\end{array}$$

These eleven axioms, sometimes called the high school identities, are related to the axioms of a bicartesian closed category or an exponential ring. Tarski's problem then becomes: are there identities involving only addition, multiplication, and exponentiation, that are true for all positive integers, but that cannot be proved using only the axioms 1–11?

Example of a provable identity

Since the axioms seem to list all the basic facts about the operations in question, it is not immediately obvious that there should be anything provably true one can state using only the three operations, but cannot prove with the axioms. However, proving seemingly innocuous statements can require long proofs using only the above eleven axioms. Consider the following proof that $(x+1{)}^2=x^2+2\cdot x+1:$

$$\begin{array}{cc}(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{array}$$

Strictly we should not write sums of more than two terms without parentheses, and therefore a completely formal proof would prove the identity $(x+1{)}^2=(x^2+2\cdot x)+1$ (or $(x+1{)}^2=x^2+(2\cdot x+1)$) and would have an extra set of parentheses in each line from $x\cdot x+(x\cdot 1+x\cdot 1)+1$ onwards.

The length of proofs is not an issue; proofs of similar identities to that above for things like $(x+y{)}^{100}$ would take many lines, but would really involve little more than the above proof.

History of the problem

The list of eleven axioms can be found explicitly written down in the works of Richard Dedekind, although they were obviously known and used by mathematicians long before then. Dedekind was the first, though, who seemed to be asking if these axioms were somehow sufficient to tell us everything we could want to know about the integers. The question was put on a firm footing as a problem in logic and model theory sometime in the 1960s by Alfred Tarski, and by the 1980s it had become known as Tarski's high school algebra problem.

Solution

In 1980 Alex Wilkie proved that not every identity in question can be proved using the axioms above. He did this by explicitly finding such an identity. By introducing new function symbols corresponding to polynomials that map positive numbers to positive numbers he proved this identity, and showed that these functions together with the eleven axioms above were both necessary and sufficient to prove it. The identity in question is $$\begin{array}{cc}& {((1+x{)}^y+(1+x+x^2{)}^y)}^x\cdot {((1+x^3{)}^x+(1+x^2+x^4{)}^x)}^y\\ =& {((1+x{)}^x+(1+x+x^2{)}^x)}^y\cdot {((1+x^3{)}^y+(1+x^2+x^4{)}^y)}^x.\end{array}$$ This identity is usually denoted $W(x,y)$ and is true for all positive integers $x$ and $y,$ as can be seen by factoring $(1-x+x^2{)}^{xy}$ out of the second factor on each side; yet it cannot be proved true using the eleven high school axioms.

Intuitively, the identity cannot be proved because the high school axioms cannot be used to discuss the polynomial $1-x+x^2.$ Reasoning about that polynomial and the subterm $-x$ requires a concept of negation or subtraction, and these are not present in the high school axioms. Lacking this, it is then impossible to use the axioms to manipulate the polynomial and prove true properties about it. Wilkie's results from his paper show, in more formal language, that the only "gap" in the high school axioms is the inability to manipulate polynomials with negative coefficients.

Generalizations

Ruben Gurevič showed in 1988 that there is no finite axiomatization for the valid equations for the positive natural numbers with 1, addition, multiplication, and exponentiation.

Wilkie proved that there are statements about the positive integers that cannot be proved using the eleven axioms above and showed what extra information is needed before such statements can be proved. Using Nevanlinna theory it has also been proved that if one restricts the kinds of exponential one takes then the above eleven axioms are sufficient to prove every true statement.

Another problem stemming from Wilkie's result asks us to find the smallest algebra such that $W(x,y)$ is not true but the eleven axioms above are. In 1985 such an algebra with 59 elements was found. Smaller such algebras have been found, and it is now known that the smallest algebras are of size 12. Moreover, it is known that there are exactly 8,957,952 countermodels of size 12 modulo isomorphism.

See also

• Template:Annotated link
• Template:Annotated link
• Template:Annotated link
• Template:Annotated link
• Template:Annotated link

References

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