The structure of decidable locally finite varieties (Q1187715)

A variety is a class of similar algebras defined by some set of equations. A variety is called locally finite if every finitely generated algebra in it is finite. A variety is called decidable if its first order theory is decidable. The authors study the question: Which locally finite varieties are decidable? The works by W. Szmielew (1955), Yu. L. Ershov (1972) and A. P. Zamyatin (1978) gave a description of decidable varieties of groups: a variety of groups is decidable if it is Abelian. Inspired by Zamyatin's ideas, S. Burris and R. McKenzie (1981) considered locally finite congruence-modular varieties; in the book under review the authors generalize these results removing the hypothesis of congruence- modularity. To formulate the main results of the book we need some definitions. A variety is said to be affine if it is polynomially equivalent to the variety of modules over some ring. A variety is said to be strongly Abelian if for every algebra A in it, for every term \(f(x,\bar y)\), and for all \(a_ 1\), \(a_ 2\), a, \(\bar c_ 1\), \(\bar c_ 2\) in A, \(f(a_ 1,\bar c_ 1)= f(a_ 2,\bar c_ 2)\) implies \(f(a,\bar c_ 1)= f(a,\bar c_ 2)\). (A simple example of a strongly Abelian variety is any variety of unary algebras.) A variety \({\mathcal V}\) is called a discriminator variety if there exists a term t(x,y,z) such that \({\mathcal V}\) is generated by its algebras A with the property that \(t^ A(a,b,c)\) is c if \(a=b\), and is a if \(a\neq b\). (A natural example of a discriminator variety is the variety of Boolean algebras.) A variety \({\mathcal V}\) is said to be the product of its subvarieties \({\mathcal V}_ 1,...,{\mathcal V}_ n\) if \({\mathcal V}\) is generated by \({\mathcal V}_ 1\cup...\cup {\mathcal V}_ n\) and there exists a term \(t(x_ 1,...,x_ n)\) such that \(t\approx x_ i\) in \({\mathcal V}\) for \(i=1,...,n\). In this case every algebra A in \({\mathcal V}\) is isomorphic to the product \(A_ 1\times...\times A_ n\) with \(A_ i\in {\mathcal V}_ i\), and the algebras \(A_ i\) are determined up to isomorphism; so one writes \({\mathcal V}={\mathcal V}_ 1\otimes...\otimes {\mathcal V}_ n\). The authors call a class \({\mathcal K}\) of similar structures unstructured (\(\omega\)-unstructured) iff the class of all graphs (finite graphs) is interpretable in \({\mathcal K}\) (the class of finite members of \({\mathcal K})\). I. A. Lavrov (1963) showed that the class of all finite graphs is hereditary undecidable, therefore a variety that is not hereditary undecidable must be \(\omega\)-structured and structured. The main result of the book is as follows. Let \({\mathcal V}\) be any structured locally finite variety. There exist a strongly Abelian variety \({\mathcal V}_ 1\), an affine variety \({\mathcal V}_ 2\), and a discriminator variety \({\mathcal V}_ 3\) such that \({\mathcal V}={\mathcal V}_ 1\otimes {\mathcal V}_ 2\otimes {\mathcal V}_ 3\); these three subvarieties of \({\mathcal V}\) are uniquely determined. By Feferman-Vaught, \({\mathcal V}\) is decidable iff \({\mathcal V}_ 1\), \({\mathcal V}_ 2\), \({\mathcal V}_ 3\) are decidable. So the problem of determining decidable locally finite varieties is reduced to the analogous but more restricted problem for strongly Abelian varieties, for varieties of modules over finite rings, and for discriminator varieties. Concerning the first problem, the second author found necessary and sufficient conditions for a locally finite, strongly Abelian variety of finite type to be decidable. It turned out that for such varieties, the properties of being undecidable, hereditary undecidable, unstructured, or \(\omega\)- unstructured, all coincide. A decidable variety of this kind is definitionally equivalent with a class of k-sorted multi-unary algebras for some integer k. As a byproduct of the above results, the authors supply an algorithm, which produces, given a finite algebra of finite type, a finite ring with unit such that the algebra generates a decidable variety iff the variety of modules over the ring is decidable. The authors formulate the following open problems. (1) Which locally finite discriminator varieties are undecidable (unstructured, \(\omega\)- unstructured)? (2) Which finite rings R with unit have the property that the variety of left unitary modules over r is decidable (\(\omega\)- structured)? (3) Which locally finite quasivarieties are undecidable (unstructured, \(\omega\)-unstructured)? (4) Which locally finite varieties are \(\omega\)-unstructured? For which locally finite varieties is the class of finite members undecidable? The authors note that recently, using the methods of the book, B. Hart and M. Valeriote have determined the possible infinite spectrum functions of locally finite varieties. Other related work: \textit{S. Burris} and \textit{R. McKenzie}: Decidability and Boolean representations [Mem. Am. Math. Soc. 246 (1981; Zbl 0483.03019)]; \textit{R. Freese} and \textit{R. McKenzie}: Commutator theory for congruence modular varieties (1987; Zbl 0636.08001); \textit{D. Hobby} and \textit{R. McKenzie}: The structure of finite algebras, Contemp. Math. 76 (1988). Reviewer's remark. In a comment about problem (2) the authors note that a class of modules is structured, because every module is stable. But, by the same reason, the class of modules over any ring is \(\omega\)- structured: if the class of finite graphs were interpretable in the class of modules, the compactness argument would provide a module with the order property, contrary to its stability. So the second part of problem (2) seems trivial.