Tarski's high school algebra problem

Last updated October 15, 2024

In mathematical logic, Tarski's high school algebra problem was 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.

Statement of the problem

Tarski considered the following eleven axioms about addition $(+)$ , multiplication $(\cdot )$ , and exponentiation to be standard axioms taught in high school: ${\begin{aligned}x+y&=y+x\\(x+y)+z&=x+(y+z)\\x\cdot 1&=x\\x\cdot y&=y\cdot x\\(x\cdot y)\cdot z&=x\cdot (y\cdot z)\\x\cdot (y+z)&=x\cdot y+x\cdot z\\1^{x}&=1\\x^{1}&=x\\x^{y+z}&=x^{y}\cdot x^{z}\\(x\cdot y)^{z}&=x^{z}\cdot y^{z}\\(x^{y})^{z}&=x^{y\cdot z}\end{aligned}}$

These eleven axioms, sometimes called the high school identities,^[1] are related to the axioms of a bicartesian closed category or an exponential ring.^[2] 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{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}}$

Strictly we should not write sums of more than two terms without brackets, and therefore a completely formal proof would prove the identity $(x+1)^{2}=\left(x^{2}+2\cdot x\right)+1$ (or $(x+1)^{2}=x^{2}+(2\cdot x+1)$ ) and would have an extra set of brackets 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 a lot of 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,^[3] 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,^[1]^[4] 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.^[5] 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 sufficient and necessary to prove it. The identity in question is ${\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}}$ 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 can't 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.

R. 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.^[6]^[7]

Generalisations

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.^[8]

Another problem stemming from Wilkie's result, which remains open, is that which asks what the smallest algebra is for which $W(x,y)$ is not true but the eleven axioms above are. In 1985 an algebra with 59 elements was found that satisfied the axioms but for which $W(x,y)$ was false.^[4] Smaller such algebras have since been found, and it is now known that the smallest such one must have either 11 or 12 elements.^[9]

Notes

1 2 Stanley Burris, Simon Lee, Tarski's high school identities, American Mathematical Monthly, 100, (1993), no.3, pp. 231–236.
↑ Strictly speaking an exponential ring has an exponential function E that takes each element x to something that acts like a^x for a fixed number a. But a slight generalisation gives the axioms for the binary operation of exponentiation. The lack of axioms about additive inverses means the axioms would have described an exponential commutative semiring, except there are no axioms about additive identities in Tarski's axioms either. However, some authors use the term rig to mean a semiring with additive identities, and reserve the term semiring for the general case not necessarily having additive identities. To those authors, the axioms do describe an exponential commutative semiring.
↑ Richard Dedekind, Was sind und was sollen die Zahlen?, 8te unveränderte Aufl. Friedr. Vieweg & Sohn, Braunschweig (1960). English translation: What are numbers and what should they be? Revised, edited, and translated from the German by H. A. Pogorzelski, W. Ryan, and W. Snyder, RIM Monographs in Mathematics, Research Institute for Mathematics, (1995).
1 2 R. Gurevič, Equational theory of positive numbers with exponentiation, Proc. Amer. Math. Soc. 94 no.1, (1985), pp.135–141.
↑ A.J. Wilkie, On exponentiation – a solution to Tarski's high school algebra problem, Connections between model theory and algebraic and analytic geometry, Quad. Mat., 6, Dept. Math., Seconda Univ. Napoli, Caserta, (2000), pp. 107–129.
↑ R. Gurevič, Equational theory of positive numbers with exponentiation is not finitely axiomatizable, Annals of Pure and Applied Logic, 49:1–30, 1990.
↑ Fiore, Cosmo, and Balat. Remarks on Isomorphisms in Typed Lambda Calculi with Empty and Sum Types
↑ C. Ward Henson, Lee A. Rubel, Some applications of Nevanlinna theory to mathematical logic: Identities of exponential functions, Transactions of the American Mathematical Society, vol.282 1, (1984), pp. 1–32.
↑ Jian Zhang, Computer search for counterexamples to Wilkie's identity, Automated Deduction – CADE-20, Springer (2005), pp. 441–451, doi : 10.1007/11532231_32.

Related Research Articles

In mathematics, a complex number is an element of a number system that extends the real numbers with a specific element denoted $i$ , called the imaginary unit and satisfying the equation $; every complex number can be expressed in the form, where a and b are real numbers. Because no real number satisfies the above equation, i was called an imaginary number by René Descartes. For the complex number, a is called the real part, and b is called the imaginary part . The set of complex numbers is denoted by either of the symbols or C . Despite the historical nomenclature, "imaginary" complex numbers have a mathematical existence as firm as that of the real numbers, and they are fundamental tools in the scientific description of the natural world.$

Euler's formula, named after Leonhard Euler, is a mathematical formula in complex analysis that establishes the fundamental relationship between the trigonometric functions and the complex exponential function. Euler's formula states that, for any real number $x$ , one has $where e is the base of the natural logarithm, i is the imaginary unit, and cos and sin are the trigonometric functions cosine and sine respectively. This complex exponential function is sometimes denoted cis x . The formula is still valid if x is a complex number, and is also called Euler's formula in this more general case.$

<span class="mw-page-title-main">Exponential function</span> Mathematical function, denoted exp(x) or e^x

The exponential function is a mathematical function denoted by $or . Unless otherwise specified, the term generally refers to the positive-valued function of a real variable, although it can be extended to the complex numbers or generalized to other mathematical objects like matrices or Lie algebras. The exponential function originated from the operation of taking powers of a number, but various modern definitions allow it to be rigorously extended to all real arguments, including irrational numbers. Its ubiquitous occurrence in pure and applied mathematics led mathematician Walter Rudin to consider the exponential function to be "the most important function in mathematics".$

Multiplication is one of the four elementary mathematical operations of arithmetic, with the other ones being addition, subtraction, and division. The result of a multiplication operation is called a product.

In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th-century Italian mathematician Giuseppe Peano. These axioms have been used nearly unchanged in a number of metamathematical investigations, including research into fundamental questions of whether number theory is consistent and complete.

In mathematics, a transcendental number is a real or complex number that is not algebraic – that is, not the root of a non-zero polynomial with integer coefficients. The best-known transcendental numbers are $π$ and $e$ . The quality of a number being transcendental is called transcendence.

In mathematics, rings are algebraic structures that generalize fields: multiplication need not be commutative and multiplicative inverses need not exist. Informally, a ring is a set equipped with two binary operations satisfying properties analogous to those of addition and multiplication of integers. Ring elements may be numbers such as integers or complex numbers, but they may also be non-numerical objects such as polynomials, square matrices, functions, and power series.

<span class="mw-page-title-main">Exponentiation</span> Arithmetic operation

In mathematics, exponentiation is an operation involving two numbers: the base and the exponent or power. Exponentiation is written as $b n$ , where $b$ is the base and $n$ is the power; this is pronounced as " $b$ (raised) to the $n$ ". When $n$ is a positive integer, exponentiation corresponds to repeated multiplication of the base: that is, $b n$ is the product of multiplying $n$ bases:

Hilbert's tenth problem is the tenth on the list of mathematical problems that the German mathematician David Hilbert posed in 1900. It is the challenge to provide a general algorithm that, for any given Diophantine equation, can decide whether the equation has a solution with all unknowns taking integer values.

In mathematics, the distributive property of binary operations is a generalization of the distributive law, which asserts that the equality $is always true in elementary algebra. For example, in elementary arithmetic, one has Therefore, one would say that multiplication distributes over addition.$

In abstract algebra, a semiring is an algebraic structure. Semirings are a generalization of rings, dropping the requirement that each element must have an additive inverse. At the same time, semirings are a generalization of bounded distributive lattices.

<span class="mw-page-title-main">Tetration</span> Arithmetic operation

In mathematics, tetration is an operation based on iterated, or repeated, exponentiation. There is no standard notation for tetration, though Knuth's up arrow notation $and the left-exponent x b are common.$

In mathematics, a real closed field is a field F that has the same first-order properties as the field of real numbers. Some examples are the field of real numbers, the field of real algebraic numbers, and the field of hyperreal numbers.

Transcendental number theory is a branch of number theory that investigates transcendental numbers, in both qualitative and quantitative ways.

In mathematics, specifically transcendental number theory, Schanuel's conjecture is a conjecture made by Stephen Schanuel in the 1960s concerning the transcendence degree of certain field extensions of the rational numbers.

In mathematics and abstract algebra, the two-element Boolean algebra is the Boolean algebra whose underlying setB is the Boolean domain. The elements of the Boolean domain are 1 and 0 by convention, so that B = {0, 1}. Paul Halmos's name for this algebra "2" has some following in the literature, and will be employed here.

In mathematics, a real number is a number that can be used to measure a continuous one-dimensional quantity such as a distance, duration or temperature. Here, continuous means that pairs of values can have arbitrarily small differences. Every real number can be almost uniquely represented by an infinite decimal expansion.

In mathematics, an exponential field is a field with a further unary operation that is a homomorphism from the field's additive group to its multiplicative group. This generalizes the usual idea of exponentiation on the real numbers, where the base is a chosen positive real number.

In proof theory, a branch of mathematical logic, elementary function arithmetic (EFA), also called elementary arithmetic and exponential function arithmetic, is the system of arithmetic with the usual elementary properties of 0, 1, +, ×, $, together with induction for formulas with bounded quantifiers.$

References

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

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[BurrisLee-1] 1 2 Stanley Burris, Simon Lee, Tarski's high school identities, American Mathematical Monthly, 100, (1993), no.3, pp. 231–236.

[2] Strictly speaking an exponential ring has an exponential function E that takes each element x to something that acts like a^x for a fixed number a. But a slight generalisation gives the axioms for the binary operation of exponentiation. The lack of axioms about additive inverses means the axioms would have described an exponential commutative semiring, except there are no axioms about additive identities in Tarski's axioms either. However, some authors use the term rig to mean a semiring with additive identities, and reserve the term semiring for the general case not necessarily having additive identities. To those authors, the axioms do describe an exponential commutative semiring.

[3] Richard Dedekind, Was sind und was sollen die Zahlen?, 8te unveränderte Aufl. Friedr. Vieweg & Sohn, Braunschweig (1960). English translation: What are numbers and what should they be? Revised, edited, and translated from the German by H. A. Pogorzelski, W. Ryan, and W. Snyder, RIM Monographs in Mathematics, Research Institute for Mathematics, (1995).

[Gurevic-4] 1 2 R. Gurevič, Equational theory of positive numbers with exponentiation, Proc. Amer. Math. Soc. 94 no.1, (1985), pp.135–141.

[5] A.J. Wilkie, On exponentiation – a solution to Tarski's high school algebra problem, Connections between model theory and algebraic and analytic geometry, Quad. Mat., 6, Dept. Math., Seconda Univ. Napoli, Caserta, (2000), pp. 107–129.

[Gurevic2-6] R. Gurevič, Equational theory of positive numbers with exponentiation is not finitely axiomatizable, Annals of Pure and Applied Logic, 49:1–30, 1990.

[Fiore-7] Fiore, Cosmo, and Balat. Remarks on Isomorphisms in Typed Lambda Calculi with Empty and Sum Types

[8] C. Ward Henson, Lee A. Rubel, Some applications of Nevanlinna theory to mathematical logic: Identities of exponential functions, Transactions of the American Mathematical Society, vol.282 1, (1984), pp. 1–32.

[9] Jian Zhang, Computer search for counterexamples to Wilkie's identity, Automated Deduction – CADE-20, Springer (2005), pp. 441–451, doi : 10.1007/11532231_32.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]