Hostname: page-component-586b7cd67f-dsjbd Total loading time: 0 Render date: 2024-11-20T10:27:34.924Z Has data issue: false hasContentIssue false
  • English
  • Français

Definability and decision problems in arithmetic

Published online by Cambridge University Press:  12 March 2014

Julia Robinson
Julia Robinson*
Affiliation:
University of California
Get access Rights & Permissions [Opens in a new window]

Extract

In this paper, we are concerned with the arithmetical definability of certain notions of integers and rationals in terms of other notions. The results derived will be applied to obtain a negative solution of corresponding decision problems.

In Section 1, we show that addition of positive integers can be defined arithmetically in terms of multiplication and the unary operation of successor S (where Sa = a + 1). Also, it is shown that both addition and multiplication can be defined arithmetically in terms of successor and the relation of divisibility | (where x|y means x divides y).

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 14 , Issue 2 , 23 June 1949 , pp. 98 - 114
Copyright
Copyright © Association for Symbolic Logic 1949

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Bernstein, B. A., Weak definitions of a field, Duke mathematical journal, vol. 14 (1947), pp. 475–482.CrossRefGoogle Scholar
[2]Church, Alonzo, An unsolvable problem of elementary number theory, American journal of mathematics, vol. 58(1936), pp. 345–363.CrossRefGoogle Scholar
[3]Church, Alonzo, A note on the Entscheidungsproblem, this Journal, vol. 1(1936), pp. 40–11, 101–102.Google Scholar
[4]Gödel, Kurt, Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I, Monatshefte für Mathematik und Physik, vol. 38(1931), pp. 173–198.CrossRefGoogle Scholar
[5]Hasse, H., Über die Darstellbarkeit von Zahlen durch quadratische Formen im Körper der rationalen Zahlen, Journal für die reine und angewandte Mathematik, vol. 152 (1923), pp. 129–148.CrossRefGoogle Scholar
[6]Hilbert, D., and Bernays, P., Grundlagen der Mathematik.Google Scholar
[7]Padoa, A., Un nouveau système irréductible de postulats pour l'algèbre, Comptes rendus du 2-e Congrès International des Mathématiciens, 1902, pp. 249–256.Google Scholar
[8]Presburger, M., Über die Vollstandigkeit eines gewissen Systems der Arithmetik, Comptes rendus du I Congris des Pays Slaves, Warsaw 1929.Google Scholar
[9]Rosser, B., Extensions of some theorems of Gödel and Church, this Journal, vol. 1(1936), pp. 87–91.Google Scholar
[10]Tarski, A., Der Wahrheitsbegriff in den formalisierten Sprachen, Studia philosophica, vol. 1(1935), pp. 261–405.Google Scholar
[11]Tarski, A., New investigations on the completeness of deductive theories (abstract), this Journal, vol. 4(1939), p. 176. [Added in proof: A detailed account has since appeared in A. Tarski, A decision method for elementary algebra and geometry. Project RAND, publication R-109, August 1948.]Google Scholar