Hostname: page-component-586b7cd67f-t8hqh Total loading time: 0 Render date: 2024-11-20T07:02:28.092Z Has data issue: false hasContentIssue false
  • English
  • Français

Two Undecidability Results using Modified Boolean Powers

Published online by Cambridge University Press:  20 November 2018

Stanley Burris  and
John Lawrence
Stanley Burris
Affiliation:
University of Waterloo, Waterloo, Ontario
John Lawrence
Affiliation:
University of Waterloo, Waterloo, Ontario
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

In this paper we will give brief proofs of two results on the undecidability of a first-order theory using a construction which we call a modified Boolean power. Modified Boolean powers were introduced by Burris in late 1978, and the first results were announced in [2]. Subsequently we succeeded in using this construction to prove the results in this paper, namely Ershov's theorem that every variety of groups containing a finite non-abelian group has an undecidable theory, and Zamjatin's theorem that a variety of rings with unity which is not generated by finitely many finite fields has an undecidable theory. Later McKenzie further modified the construction mentioned above, and combined it with a variant of one of Zamjatin's constructions to prove the sweeping main result of [3]. The proofs given here have the advantage (over the original proofs) that they use a single construction.

Type
Research Article
Information
Canadian Journal of Mathematics , Volume 34 , Issue 2 , 01 April 1982 , pp. 500 - 505
Copyright
Copyright © Canadian Mathematical Society 1982

References

1. Arens, R. F. and Kaplansky, I., Topological representations of algebras, Trans. Amer. Math. Soc. 63 (1948), 457–481.Google Scholar
2. Burris, S., An algebraic test for undecidability, N.A.M.S. 26 (1979).Google Scholar
3. Burris, S. and McKenzie, R., Decidability and Boolean representations, Memoirs Amer. Math. Soc. 32, No. 246 (1981).Google Scholar
4. Comer, S., Elementary properties of structures of sections, Bol. Soc. Mat. Mexicana 19 (1974), 78–85.Google Scholar
5. Yu. L., Ersov, Theories of non-abelian varieties of groups, Proc. of Symposium in Pure Mathematics 25 (A.M.S., Providence, Rhode Island, 1974), 255–264. Google Scholar
6. Scott, W. R., Group theory (Prentice Hall, 1964).Google Scholar
7. Zamjatin, A. P., Varieties of associative rings whose elementary theory is decidable, Soviet Math. Doklady 17 (1976), 996–999.Google Scholar