×

zbMATH — the first resource for mathematics

Positive algebras with countable congruence lattices. (English. Russian original) Zbl 0787.08002
Algebra Logic 31, No. 1, 12-23 (1992); translation from Algebra Logika 31, No. 1, 21-37 (1992).
A. I. Mal’tsev was one of the first to investigate algorithmic properties of positive algebras with countable congruence lattices; in particular, he proved constructiveness of positive algebras with finite congruence lattices and constructiveness of finitely generated positive algebras with nonzero congruences of only finite index. W. Baur established constructiveness for associative and commutative rings with identities and Noetherian lattices of ideals. In Algebra Logika 30, No. 3, 293-305 (1991; Zbl 0774.03029), the author constructed examples of nonconstructive positive groupoids with nonzero finite index congruences; descriptions of such algebras were given. All the lattices for all the algebras mentioned above are obviously countable.
In this paper we study the most general properties of positive algebras with countable lattices of congruences. For such algebras, in particular we infer an algebraic criterion of effective infinity, prove local finiteness of noneffectively infinite algebras, and construct an example of an algebra that is finitely defined in a finitely based variety and has Noetherian congruence lattice and an undecidable word problem. We also prove that for any natural \(n\), there exists a positive algebra with exactly \(n\) nonrecursively enumerable congruences.

MSC:
08A30 Subalgebras, congruence relations
03D45 Theory of numerations, effectively presented structures
03C57 Computable structure theory, computable model theory
08A50 Word problems (aspects of algebraic structures)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Yu. L. Ershov, Decidability Problems and Constructive Models [in Russian], Nauka, Moscow (1980).
[2] N. Kh. Kasymov, ”On algebras with residually finite positively representable enrichments,” Algebra Logika,26, No. 6, 715–730 (1987). · Zbl 0661.03038
[3] N. Kh. Kasymov, ”Positive algebras with congruences of finite index,” Algebra Logika,30, No. 3, 293–305 (1991). · Zbl 0774.03029
[4] N. Kh. Kasymov, and B. M. Khusainov, ”Finitely generated enumerable and absolutely locally finite algebras,” Vychisl. Sistemy, No. 116, 3–15 (1986). · Zbl 0646.03042
[5] A. I. Mal’tsev, ”Constructive algebras. I,” Usp. Mat. Nauk, No. 3, 3–60 (1961).
[6] H. Rogers, Theory of Recursive Functions and Effective Computability, McGraw-Hill, New York (1967). · Zbl 0183.01401
[7] W. Baur, ”Rekursive Algebren mit Kettenbedingungen”, Z. Math. Logik Grundl. Math.,20, No. 1, 37–46 (1974). · Zbl 0317.02050
[8] J. A. Bergstra and J. V. Tucker, ”A characterization of computable data types by means of a finite equational specifications method,” Lect. Not. Comp. Sci., No. 85, 76–90 (1980). · Zbl 0449.68003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.