Logic for Programming, Artificial Intelligence, and Reasoning

International audienceIn 1969, Tarski asked whether the arithmetic identities taught in high school are complete for showing all arithmetic equations valid for the natural numbers. We know the answer to this question for various subsystems obtained by restricting in different ways the language of arithmetic expressions, yet, up to now we knew nothing of the original system that Tarski considered when he started all this research, namely the theory of integers under sum, product, exponentiation with two constants for zero and one. This paper closes this long standing open problem, by providing an elementary proof, relying on previous work of R. Gureviccaron, of the fact that Tarskirsquos original system is decidable, yet not finitely aximatisable. We also show some consequences of this result for the theory of isomorphisms of types