In
mathematical logic
Mathematical logic is the study of logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of for ...
, Tarski's high school algebra problem was a question posed by
Alfred Tarski
Alfred Tarski (, born Alfred Teitelbaum;School of Mathematics and Statistics, University of St Andrews ''School of Mathematics and Statistics, University of St Andrews''. January 14, 1901 – October 26, 1983) was a Polish-American logician a ...
. It asks whether there are
identities involving
addition
Addition (usually signified by the Plus and minus signs#Plus sign, plus symbol ) is one of the four basic Operation (mathematics), operations of arithmetic, the other three being subtraction, multiplication and Division (mathematics), division. ...
,
multiplication
Multiplication (often denoted by the cross symbol , by the mid-line dot operator , by juxtaposition, or, on computers, by an asterisk ) is one of the four elementary mathematical operations of arithmetic, with the other ones being additi ...
, and
exponentiation
Exponentiation is a mathematical operation, written as , involving two numbers, the '' base'' and the ''exponent'' or ''power'' , and pronounced as " (raised) to the (power of) ". When is a positive integer, exponentiation corresponds to re ...
over the positive
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
s that cannot be
proved using eleven
axiom
An axiom, postulate, or assumption is a statement that is taken to be true, to serve as a premise or starting point for further reasoning and arguments. The word comes from the Ancient Greek word (), meaning 'that which is thought worthy or f ...
s about these operations that are taught in high-school-level
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
. The question was solved in 1980 by
Alex Wilkie
Alex James Wilkie FRS (born 1948 in Northampton) is a British mathematician known for his contributions to model theory and logic. Previously Reader in Mathematical Logic at the University of Oxford, he was appointed to the Fielden Chair of Pur ...
, who showed that such unprovable identities do exist.
Statement of the problem
Tarski considered the following eleven axioms about addition ('+'), multiplication ('·'), and exponentiation to be standard axioms taught in high school:
# ''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''
# 1
''x'' = 1
# ''x''
1 = ''x''
# ''x''
''y'' + ''z'' = ''x''
''y'' · ''x''
''z''
# (''x'' · ''y'')
''z'' = ''x''
''z'' · ''y''
''z''
# (''x''
''y'')
''z'' = ''x''
''y'' · ''z''
These eleven axioms, sometimes called the ''high school identities'',
[Stanley Burris, Simon Lee, ''Tarski's high school identities'', ]American Mathematical Monthly
''The American Mathematical Monthly'' is a mathematical journal founded by Benjamin Finkel in 1894. It is published ten times each year by Taylor & Francis for the Mathematical Association of America.
The ''American Mathematical Monthly'' is an e ...
, 100, (1993), no.3, pp. 231–236. are related to the axioms of a
bicartesian closed category
In category theory, a Category (mathematics), category is Cartesian closed if, roughly speaking, any morphism defined on a product (category theory), product of two Object (category theory), objects can be naturally identified with a morphism defin ...
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
Strictly we should not write sums of more than two terms without brackets, and therefore a completely
formal proof
In logic and mathematics, a formal proof or derivation is a finite sequence of sentences (called well-formed formulas in the case of a formal language), each of which is an axiom, an assumption, or follows from the preceding sentences in the seque ...
would prove the identity
(or
) and would have an extra set of brackets in each line from
onwards.
The length of proofs is not an issue; proofs of similar identities to that above for things like
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
Julius Wilhelm Richard Dedekind (6 October 1831 – 12 February 1916) was a German mathematician who made important contributions to number theory, abstract algebra (particularly ring theory), and
the axiomatic foundations of arithmetic. His ...
, 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
Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premises ...
and
model theory
In mathematical logic, model theory is the study of the relationship between formal theories (a collection of sentences in a formal language expressing statements about a mathematical structure), and their models (those structures in which the s ...
sometime in the 1960s by Alfred Tarski,
[R. Gurevič, ''Equational theory of positive numbers with exponentiation'', Proc. Amer. Math. Soc. 94 no.1, (1985), pp.135–141.] 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
polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exa ...
s 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
This identity is usually denoted
and is true for all positive integers
and
as can be seen by factoring
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
Reasoning about that polynomial and the subterm
requires a concept of
negation
In logic, negation, also called the logical complement, is an operation that takes a proposition P to another proposition "not P", written \neg P, \mathord P or \overline. It is interpreted intuitively as being true when P is false, and false ...
or
subtraction
Subtraction is an arithmetic operation that represents the operation of removing objects from a collection. Subtraction is signified by the minus sign, . For example, in the adjacent picture, there are peaches—meaning 5 peaches with 2 taken ...
, 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
coefficient
In mathematics, a coefficient is a multiplicative factor in some term of a polynomial, a series, or an expression; it is usually a number, but may be any expression (including variables such as , and ). When the coefficients are themselves var ...
s.
R. Gurevič showed in 1988 that there is no
finite axiomatization In mathematical logic, an axiom schema (plural: axiom schemata or axiom schemas) generalizes the notion of axiom.
Formal definition
An axiom schema is a formula in the metalanguage of an axiomatic system, in which one or more schematic variable ...
for the valid equations for the positive
natural number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''Cardinal n ...
s with 1, addition, multiplication, and exponentiation.
[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 Type]
/ref>
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 In the mathematical field of complex analysis, Nevanlinna theory is part of the
theory of meromorphic functions. It was devised in 1925, by Rolf Nevanlinna. Hermann Weyl called it "one of the few great mathematical events of (the twentieth) century ...
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, which remains open, is that which asks what the smallest algebra
Algebra () is one of the broad areas of mathematics. Roughly speaking, algebra is the study of mathematical symbols and the rules for manipulating these symbols in formulas; it is a unifying thread of almost all of mathematics.
Elementary a ...
is for which 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 was false. Smaller such algebras have since been found, and it is now known that the smallest such one must have either 11 or 12 elements.[Jian Zhang, ''Computer search for counterexamples to Wilkie's identity'', Automated Deduction – CADE-20, ]Springer
Springer or springers may refer to:
Publishers
* Springer Science+Business Media, aka Springer International Publishing, a worldwide publishing group founded in 1842 in Germany formerly known as Springer-Verlag.
** Springer Nature, a multinationa ...
(2005), pp. 441–451, .
See also
*
*
*
*
*
Notes
References
* Stanley N. Burris, Karen A. Yeats, ''The saga of the high school identities'', Algebra Universalis
''Algebra Universalis'' is an international scientific journal focused on universal algebra and lattice theory. The journal, founded in 1971 by George Grätzer, is currently published by Springer-Verlag. Honorary editors in chief of the journal i ...
52 no.2–3, (2004), pp. 325–342, .
{{DEFAULTSORT:Tarski's High School Algebra Problem
Theorems in the foundations of mathematics
Universal algebra