Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-23T06:49:33.895Z Has data issue: false hasContentIssue false
  • English
  • Français

Negative solution of the decision problem for sentences true in every subalgebra of 〈N, +〉

Published online by Cambridge University Press:  12 March 2014

Ralph Mckenzie
Ralph Mckenzie*
Affiliation:
University of California, Berkley, California 94720
Get access Rights & Permissions [Opens in a new window]

Extract

It was shown by Taiclin [6], and independently announced by Tarski [7], that the elementary theory of commutative cancellation semigroups is hereditarily undecidable. In his proof Tarski exhibited a subsemigroup of 〈N, ·〉, the natural numbers with multiplication, whose theory is both hereditarily and essentially undecidable. (The details of his construction were published by V. H. Dyson [1].) In connection with these results, Tarski suggested to the author that it would be of interest to solve the decision problem for the theory K which consists of all elementary sentences which are true in every subalgebra (i.e. every subsemigroup) of 〈N, +〉. The object of this note is to prove that the theory K is hereditarily undecidable.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 36 , Issue 4 , December 1971 , pp. 607 - 609
Copyright
Copyright © Association for Symbolic Logic 1972

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]Dyson, V. H., On the decision problem for theories of finite models, Israel Journal of Mathematics, vol. 2 (1964), pp. 55–70.CrossRefGoogle Scholar
[2]Ershov, Y. L., Lavrov, I. A., Taimanov, A. D. and Taiclin, M. A., Elementary theories, Russian mathematic surveys, vol. 20 (1965), pp. 35–105.CrossRefGoogle Scholar
[3]Lavrov, I. A., Effective inseparability of the sets of identically true formulae and finitely refutable formulae for certain elementary theories, Algebra i Logika Seminar 2, vol. 1 (1963), pp. 5–19 [Russian].Google Scholar
[4]Rabin, M. O., A simple method for undecidability proofs and some applications, Logic, methodology and philosophy of science, Proceedings of the 1964 International Congress, Bar-Hillel, ed., Amsterdam, 1965, pp. 58–68.Google Scholar
[5]Rogers, H. Jr., Certain logical reduction and decision problems, Annals of Mathematics, vol. 64 (1956), pp. 264–284.Google Scholar
[6]Taiclin, M. A., Undecidability of the elementary theory of commutative cancellation semigroups, Sibü. Matematičeski Žurnal, vol. 3 (1962), pp. 308–309 [Russian].Google Scholar
[7]Tarski, A., Solution of the decision problem for the elementary theory of commutative semigroups. Notices of the American Mathematical Society, vol. 9 (1962), p. 205.Google Scholar
[8]Vaught, R. L., Cobham's theorem on undecidable theories, Logic methodology and philosophy of science, Proceedings of the 1960 International Congress, Nagel, Suppes and Tarski, eds., Stanford 1962, pp. 14–25.Google Scholar