Hostname: page-component-78c5997874-8bhkd Total loading time: 0 Render date: 2024-11-12T22:29:36.719Z Has data issue: false hasContentIssue false
  • English
  • Français

Definability in the monadic second-order theory of successor1

Published online by Cambridge University Press:  12 March 2014

J. Richard Buchi  and
Lawrence H. Landweber
J. Richard Buchi
Affiliation:
Purdue University, University of Wisconsin
Lawrence H. Landweber
Affiliation:
Purdue University, University of Wisconsin
Get access Rights & Permissions [Opens in a new window]

Extract

Let be a relational system whereby D is a nonempty set and P1 is an m1-ary relation on D. With we associate the (weak) monadic second-order theory consisting of the first-order predicate calculus with individual variables ranging over D; monadic predicate variables ranging over (finite) subsets of D; monadic predicate quantifiers; and constants corresponding to P1, P2, …. We will often use ambiguously to mean also the set of true sentences of .

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 34 , Issue 2 , 25 July 1969 , pp. 166 - 170
Copyright
Copyright © Association for Symbolic Logic 1969

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 research was supported by the National Science Foundation (Contract 4730-50-395).

References

[1] Büchi, J. R., On a decision procedure in restricted second order arithmetic, Proceedings of the international congress on logic, methodology and the philosophy of science, Stanford University Press, Stanford, California, 1962.Google Scholar
[2] Büchi, J. R. and Landweber, L. H., Solving sequential conditions by finite state operators, Purdue Report CSD TR 14.Google Scholar
[3] Davis, M., Infinitary games of perfect information, Advances in game theory, Princeton University Press, Princeton, New Jersey, 1964, pp. 85–101.Google Scholar
[4] Elgot, C. C. and Rabin, M. O., Decidability and undecidability of extensions of second (first) order theories of (generalized) successor, this Journal , vol. 31 (1966), pp. 169–181.Google Scholar
[5] Kleene, S. C., Introduction to metamathematics, Van Nostrand, New York, Amsterdam and Noordhoff, Groningen, 1952.Google Scholar
[6] Kleene, S. C., Hierarchies of number theoretic predicates, Bulletin of the American Mathematical Society, vol. 61 (1955), pp. 193–213.Google Scholar
[7] McNaughton, R., Testing and generating infinite sequences by a finite automaton, Information and control, vol. 9 (1966), pp. 521–530.Google Scholar
[8] Robinson, R. M., Restricted set theoretical definitions in arithmetic, Proceedings of the American Mathematical Society, vol. 9 (1958), pp. 238–242.Google Scholar
[9] Rogers, H. Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967.Google Scholar