Hostname: page-component-586b7cd67f-rdxmf Total loading time: 0 Render date: 2024-11-29T17:00:10.587Z Has data issue: false hasContentIssue false
  • English
  • Français

Decision problems for multiple successor arithmetics1

Published online by Cambridge University Press:  12 March 2014

J. W. Thatcher
J. W. Thatcher*
Affiliation:
Ibm Watson Research Center Yorktown Heights, New York
Get access Rights & Permissions [Opens in a new window]

Extract

Let Nk denote the set of words over the alphabet Σk = {1, …, k}. Nk contains the null word which is denoted λ. We consider decision problems for various first-order interpreted predicate languages in which the variables range over Nk (k ≧ 2). Our main result is that there is no decision procedure for truth in the interpreted language which has the subword relation as its only non-logical primitive. This, together with known results summarized in Section 4, settles the decision problem for any language constructed on the basis of the relations and functions listed below.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 31 , Issue 2 , June 1966 , pp. 182 - 190
Copyright
Copyright © Association for Symbolic Logic 1966

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.)

Footnotes

1

This paper is part of a Ph.D thesis submitted to the Program in Communication Sciences at the University of Michigan and was presented to the American Mathematical Society, Notices of the American Mathematical Society, 11, Abstract 64T-359 (1964) 582.

The author gratefully acknowledges the suggestions and corrections offered by J. H. Bennett, C. C. Elgot and E. C. Wagner. The author is especially grateful to J. B. Wright who has provided so much encouragement through many englightening and stimulating discussions.

This work was supported in part by the following government agencies through contracts and grants administered by the University of Michigan; Office of Naval Research contact Nonr 1224(21); National Science Foundation grant G-22258; U. S. Army Research Office (Durham) grant DA-ARO(D)-31–121-G433; and through U. S. Air Force (Rome Air Development Center) contract AF 30(602)-3340 administered by the IBM Watson Research Center.

References

[1]Asser, G., Rekursive Wortfunktionen, Fundamenta Mathematicae, vol. 6 (1960), pp. 258–278.Google Scholar
[2]Büchi, J. R., Weak second-order arithmetic and finite automata, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 6 (1960), pp. 66–92.CrossRefGoogle Scholar
[3]Elgot, C. C., Decision problems of finite automata design and related arithmetics. Doctoral Dissertation, The University of Michigan, Ann Arbor, Michigan, 1959.Google Scholar
[4]Hilbert, D. and Bernays, P., Grundlagen der Mathematik, Berlin, 1939.Google Scholar
[5]Presburger, M., Über die Vollständigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritte, Comptes Rendus du I Congress des Mathématiciens des Pays Slavs (Warszawa 1929), pp. 29–101 and 395.Google Scholar
[6]Quine, W. V., Concatenation as a basis of arithmetic, this Journal, vol. 11 (1946), pp. 105–114.Google Scholar
[7]Tarski, A., Der Wahrheitsbegriff in den formalisierten Sprachen, Studia Philosophica, vol. 1 (1930), pp. 361–404.Google Scholar
[8]Thatcher, J. W., Decision problems and definability for generalized arithmetic, Doctoral Dissertation, The University of Michigan, Ann Arbor, Michigan, 1964.Google Scholar