Hostname: page-component-cd9895bd7-p9bg8 Total loading time: 0 Render date: 2025-01-03T10:52:36.854Z Has data issue: false hasContentIssue false
  • English
  • Français

The decision problem for standard classes

Published online by Cambridge University Press:  12 March 2014

Yuri Gurevich
Yuri Gurevich*
Affiliation:
University of the Neger, Beer Sheva, Israel
Get access Rights & Permissions [Opens in a new window]

Extract

The standard classes of a first-order theory T are certain classes of prenex T-sentences defined by restrictions on prefix, number of monadic, dyadic, etc. predicate variables, and number of monadic, dyadic, etc. operation variables. In [3] it is shown that, for any theory T, (1) the decision problem for any class of prenex T-sentences specified by such restrictions reduces to that for the standard classes, and (2) there are finitely many standard classes K 1, …, Kn such that any undecidable standard class contains one of K 1, …, Kn . These results give direction to the study of the decision problem.

Below T is predicate logic with identity and operation variables. The Main Theorem solves the decision problem for the standard classes admitting at least one operation variable.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 41 , Issue 2 , June 1976 , pp. 460 - 464
Copyright
Copyright © Association for Symbolic Logic 1976

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

I am grateful to Dr. Avraham Feintuch for correcting my English, and to the two referees who greatly improved earlier versions of this paper. The results of this paper were obtained in 1971, and were included (save for the theorem of Shelah in §2, which was mentioned as a hypothesis) in an article accepted for publication by the Institute of Philosophy of the Soviet Academy of Science. That article has not appeared.

References

REFERENCES

[1] Gödel, K., Zum Entscheidungsproblem des logischen Funktionenkalküls, Monatshefte für Mathematik und Physik, vol. 40 (1933), pp. 433–443.CrossRefGoogle Scholar
[2] Gurevich, Y., On the effective recognizing of satisfiability of predicate formulas, Algebra and Logic, vol. 5 (1966), pp. 25–55.Google Scholar
[3] Gurevich, Y., The decision problem for the logic of predicates and operations, Algebra and Logic, vol. 8 (1969), pp. 284–308.CrossRefGoogle Scholar
[4] Gurevich, Y. and Koriakov, I., Remark on the R. Berger's paper on the domino problem, Siberian Mathematical Journal, vol. 13 (1972), pp. 459–463.CrossRefGoogle Scholar
[5] Kostirko, V., The reduction class ∀x∀y∃zF(x, y, z) ∧ ∀n A(F), Cybernetics (Kiev, USSR), 1971, no. 5, pp. 1–3.Google Scholar
[6] Lifshitz, V., Some reduction classes and undecidable theories, Proceedings of the Leningrad Branch of Steklov Math Institute, vol. 4 (1967), pp. 65–68.Google Scholar
[7] Rabin, M. O., Decidability of second order theories and automata on infinite trees, Transactions of the American Mathematical Society, vol. 141 (1969), pp. 1–35.Google Scholar
[8] Wang, H., Dominoes and the AEA case of the decision problem, Proceedings of the Symposium on Mathematical Theory of Automata, Polytechnic Institute of Brooklyn, New York, 1962.Google Scholar