Hostname: page-component-586b7cd67f-rcrh6 Total loading time: 0 Render date: 2024-11-25T01:38:58.105Z Has data issue: false hasContentIssue false
  • English
  • Français

Finite axiomatizability for equational theories of computable groupoids

Published online by Cambridge University Press:  12 March 2014

Peter Perkins
Peter Perkins*
Affiliation:
Department of Mathematics, Holy Cross College, Worcester, Massachusetts 01610
Get access Rights & Permissions [Opens in a new window]

Extract

A computable groupoid is an algebra ‹N, g› where N is the set of natural numbers and g is a recursive (total) binary operation on N. A set L of natural numbers is a computable list of computable groupoids iff L is recursive, ‹N, ϕe› is a computable groupoid for each e ∈ L, and e ∈ L whenever e codes a primitive recursive description of a binary operation on N.

Theorem 1. Let L be any computable list of computable groupoids. The set {e ∈ L: the equational theory of ‹N, ϕe› is finitely axiomatizable} is not recursive.

Theorem 2. Let S be any recursive set of positive integers. A computable groupoid GS can be constructed so that S is inifinite iff GS has a finitely axiomatizable equational theory.

The problem of deciding which finite algebras have finitely axiomatizable equational theories has remained open since it was first posed by Tarski in the early 1960's. Indeed, it is still not known whether the set of such finite algebras is recursively (or corecursively) enumerable. McKenzie [7] has shown that this question of finite axiomatizability for any (finite) algebra of finite type can be reduced to that for a (finite) groupoid.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 54 , Issue 3 , September 1989 , pp. 1018 - 1022
Copyright
Copyright © Association for Symbolic Logic 1989

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

REFERENCES

[1]Baker, K., McNulty, G., and Werner, H., Shift-automorphism methods for inherently nonfinitely based varieties of algebras (preprint).Google Scholar
[2]Burris, S. and Sankappanavar, H., A course in universal algebra, Springer-Verlag, Berlin, 1981.CrossRefGoogle Scholar
[3]Jezek, J., Nonfinitely based three-element idempotent groupoids, Algebra Universalis, vol. 20 (1985), pp. 292–301.CrossRefGoogle Scholar
[4]Kleene, S. C., Introduction to metamathematics. Van Nostrand, Princeton, New Jersey, 1952.Google Scholar
[5]Lyndon, R., Identities in finite algebras, Proceedings of the American Mathematical Society, vol. 5 (1954), pp. 8–9.CrossRefGoogle Scholar
[6]Malcev, A. I., Algebraic systems, Springer-Verlag, Berlin, 1973.CrossRefGoogle Scholar
[7]McKenzie, R., A new product of algebras and a type reduction theorem, Algebra Universalis, vol. 18 (1984) pp. 29–69.CrossRefGoogle Scholar
[8]McNulty, G. and Shallon, C., Inherently nonfinitely based finite algebras, Universal algebra and lattice theory (Freese, R. and Garcia, O., editors), Lecture Notes in Mathematics, vol. 1004, Springer-Verlag, Berlin, 1983, pp. 206–231.CrossRefGoogle Scholar
[9]McNulty, G., The decision problem for equational bases of algebras, Annals of Mathematical Logic, vol. 11 (1977), pp. 193–259.Google Scholar
[10]Murskiĭ, V. L., The existence in three valued logic of a closed class with finite basis not having a finite complete set of identities, Doklady Akademii Nauk SSSR, vol. 163 (1965), pp. 815–818; English translation, Soviet Mathematics Doklady, vol. 6 (1965), pp. 1020–1024.Google Scholar
[11]Murskiĭ, V. L., On the number of κ-element algebras with one binary operation without a finite basis of identities, Problemy Kibernetiki, vol. 35 (1979), pp. 5–27. (Russian)Google Scholar
[12]Perkins, P., Unsolvable problems for equational theories, Notre Dame Journal of Formal Logic, vol. 8 (1967), pp. 175–185.CrossRefGoogle Scholar
[13]Perkins, P., Basis questions for general algebras, Algebra Universalis, vol. 19 (1984), pp. 16–23.CrossRefGoogle Scholar