Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



Equational theory of positive numbers with exponentiation

Author: R. Gurevič
Journal: Proc. Amer. Math. Soc. 94 (1985), 135-141
MSC: Primary 03C05; Secondary 03B25, 03C13, 03C65
MathSciNet review: 781071
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: A. Tarski asked if all true identities involving 1, addition, multiplication, and exponentiation can be derived from certain so-called "high-school" identities (and a number of related questions). I prove that equational theory of $ ({\mathbf{N}},1, + , \cdot , \uparrow )$ is decidable ( $ a \uparrow b$ means $ {a^b}$ for positive $ a,b$) and that entailment relation in this theory is decidable (and present a similar result for inequalities). A. J. Wilkie found an identity not derivable from Tarski's axioms with a difficult proof-theoretic argument of nonderivability. I present a model of Tarski's axioms consisting of 59 elements in which Wilkie's identity fails.

References [Enhancements On Off] (What's this?)

  • [1] Leon Henkin, The logic of equality, Amer. Math. Monthly 84 (1977), no. 8, 597–612. MR 0472649
  • [2] A. G. Hovanskiĭ, A class of systems of transcendental equations, Dokl. Akad. Nauk SSSR 255 (1980), no. 4, 804–807 (Russian). MR 600749
  • [3] Angus Macintyre, The laws of exponentiation, Model theory and arithmetic (Paris, 1979–1980) Lecture Notes in Math., vol. 890, Springer, Berlin-New York, 1981, pp. 185–197. MR 645003
  • [4] D. Richardson, Solution of the identity problem for integral exponential functions., Z. Math. Logik Grundlagen Math. 15 (1969), 333–340. MR 0262068
  • [5] Alex J. Wilkie, On exponentiation—a solution to Tarski’s high school algebra problem, Connections between model theory and algebraic and analytic geometry, Quad. Mat., vol. 6, Dept. Math., Seconda Univ. Napoli, Caserta, 2000, pp. 107–129. MR 1930684

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 03C05, 03B25, 03C13, 03C65

Retrieve articles in all journals with MSC: 03C05, 03B25, 03C13, 03C65

Additional Information

Keywords: Exponentiation of positive reals, exponentiation of positive integers, Tarski's high school algebra problem, decidability of equational theory, decidability of entailment relation, differential ring, finite model of Tarski's axioms
Article copyright: © Copyright 1985 American Mathematical Society