\documentstyle{SibMatJ} % \TestXML \topmatter \Author Schwidefsky \Initial M. \Initial V. \Gender she \ORCID 0000-0003-4804-8073 \Email m.schwidefsky\@g.nsu.ru \AffilRef 1 \AffilRef 2 \endAuthor \Affil 1 \Organization Novosibirsk State University \City Novosibirsk \Country Russia \endAffil \Affil 2 \Organization Sobolev Institute of Mathematics \City Novosibirsk \Country Russia \endAffil \datesubmitted July 10, 2025\enddatesubmitted \dateaccepted September 1, 2025\enddateaccepted \UDclass 512.58 %08C15, 03C60, 03D35, 08A30 \endUDclass \thanks The research was carried out under the support of the Russian Science Foundation (project 24--21--00075). %\?The work is supported by the Russian Science Foundation (project 24--21--00075). \endthanks \title Decision Problems for Quasivarieties \endtitle \abstract We prove that, under certain circumstances, a quasivariety contains continuum many $Q$\=universal subquasivarieties for which the finite membership problem and the quasiequational theory are undecidable. \endabstract \keywords decision problem, finite membership problem, quasiequational theory, quasivariety \endkeywords \endtopmatter \head 1. Introduction \endhead When certain sufficient conditions are satisfied by a quasivariety $\bold{K}$, $\bold{K}$ turns out to have a highly complicated inner structure. First conditions of this type were offered by M.E. Adams and W. Dziobiak [1] and similar conditions were found by V.A. Gorbunov [2]. Later, stronger conditions than those in [1] were found in [3]; under these conditions, many complexity results for quasivarieties were established in [3--6] as well as in other papers by the same authors. In particular, it was established in [4] that some algorithmic problems are undecidable in a quasivariety $\bold{K}$ once $\bold{K}$ satisfies the conditions from [3]. In [6], more general conditions than those in [3] were introduced; see \Par*{Definition 2.3}. These conditions still imply the conditions of M.E. Adams and W. Dziobiak [1]. Moreover, under these conditions, the results of [3,\,5,\,6] still hold, as demonstrated in [7--9]. Here, we generalize some results from [4] and show that Theorem 6.5 from [4] has a much wider application area than just Corollary 7.8 in [4]. In particular, \Par*{Theorem 4.1}, presents new examples of quasivarieties where certain algorithmic problems are undecidable. For the notation and notions not defined here, we refer to V.A. Gorbunov [2] as well as to [1,\,7]. \head 2. Preliminaries \endhead In this section, we present known results on quasivarieties containing countable subclasses possessing particular properties. \specialhead 2.1. Adams--Dziobiak classes \endspecialhead The following definition is due to M.E. Adams and W. Dziobiak [1]. In the present form, it appears in [10]. \demo{Definition 2.1} Let a class $\bold{A}=\{\Cal{A}_X\mid X\in\Cal{P}_{fin}(\omega)\}$ of structures of finite similarity type $\sigma$ possess the following properties: \itemitem{$(\operatorname{P}_0)$} For each $X\in\Cal{P}_{fin}(\omega)$, the structure $\Cal{A}_X$ is $l$-projective in $\bold{Q}(\bold{A})$ and the trivial congruence $\Delta_{\Cal{A}_X}$ is a dually compact element in $\operatorname{Con}_{\bold{Q}(\bold{A})}\Cal{A}_X$. \itemitem{$(\operatorname{P}_1)$} \Label{D2.1(1)} $\Cal{A}_\varnothing$ is a trivial structure. \itemitem{$(\operatorname{P}_2)$} \Label{D2.1(2)} If $X=Y\cup Z$ in $\Cal{P}_{fin}(\omega)$ then $\Cal{A}_X\in\bold{Q}(\Cal{A}_Y,\Cal{A}_Z)$. \itemitem{$(\operatorname{P}_3)$} \Label{D2.1(3)} If $\varnothing\ne X\in\Cal{P}_{fin}(\omega)$ and $\Cal{A}_X\in\bold{Q}(\Cal{A}_Y)$ then $X=Y$. \itemitem{$(\operatorname{P}_4)$} If $\Cal{A}_X\leq\Cal{B}_0\times\Cal{B}_1$ for some $\Cal{B}_0$, $\Cal{B}_1\in\bold{Q}(\bold{A})$ then there are $Y_0$, $Y_1\in\Cal{P}_{fin}(\omega)$ such that $\Cal{A}_{Y_0}\in\bold{Q}(\Cal{B}_0)$, $\Cal{A}_{Y_1}\in\bold{Q}(\Cal{B}_1)$, and $X=Y_0\cup Y_1$. In this case $\bold{A}$ is called an $\operatorname{AD}$-{\it class}. If each structure from $\bold{A}$ is finite then $\bold{A}$ is called a {\it finite\/} $\operatorname{AD}$-{\it class}. \enddemo For statement \Par{T2.2}{(i)} in the following theorem, we refer to M.E. Adams and W. Dziobiak [1, Theorem~3.3]. For statement \Par{T2.2}{(ii)}, to Corollary 3.5 and Theorem 4.4 in [10]. \proclaim{Theorem 2.2}\Label{T2.2} Let a quasivariety $\bold{K}$ contain an $\operatorname{AD}$-class. Then \Item (i) $\bold{K}$ is $Q$-universal; \Item (ii) $\bold{K}$ contains continuum many classes $\bold{K}^\prime\subseteq\bold{K}$ such that the set of {\rm(}isomorphism types{\rm)} of finite sublattices of the $\bold{K}^\prime$-quasivariety lattice $\operatorname{Lq}(\bold{K}^\prime)$ is not computably enumerable. \endproclaim \specialhead 2.2. $\operatorname{B}^\ast$-Classes \endspecialhead \demo{Definition 2.3 \rm [7]} Let $\bold{M}\subseteq\bold{K}(\sigma)$ be a quasivariety of a finite similarity type $\sigma$ and let $\bold{V}\subseteq\bold{K}(\sigma)$ be a variety. A class $\bold{A}=\{\Cal{A}_F\mid F\in\Cal{P}_{fin}(\omega)\}\subseteq\bold{M}$ is a $\operatorname{B}^\ast$-{\it class with respect to\/} $\bold{M}$ {\it and\/} $\bold{V}$, if $\bold{A}$ satisfies the following conditions. \itemitem{$(\operatorname{B}_0)$} For each nonempty $F\in\Cal{P}_{fin}(\omega)$, the structure $\Cal{A}_F$ is finitely presented in $\bold{M}$; $\Cal{A}_\varnothing$ is a trivial structure. \itemitem{$(\operatorname{B}_1)$} If $F=G\cup H$ in $\Cal{P}_{fin}(\omega)$ then $\Cal{A}_F\in\bold{Q}(\Cal{A}_G,\Cal{A}_H)$. \itemitem{$(\operatorname{B}^\ast_2)$} For each $F,G\in\Cal{P}_{fin}(\omega)$, if $F\ne\varnothing$ and $\Cal{A}_F\in\bold{Q}(\Cal{A}_G,\bold{V})$ then $F=G$. \itemitem{$(\operatorname{B}^\ast_3)$} For every $F\in\Cal{P}_{fin}(\omega)$ and every $i<\omega$, if $f\in\operatorname{Hom}(\Cal{A}_F,\Cal{A}_{\{i\}})$ then either $f(\Cal{A}_F)\in\bold{V}$ or $i\in F$. \itemitem{$(\operatorname{B}^\ast_4)$} $\bold{H}(\bold{A})\cap(\bold{M}{\setminus}\bold{V})\subseteq\bold{A}$. \itemitem{$(\operatorname{B}^\ast)$} For all $F,G\in\Cal{P}_{fin}(\omega)$ such that $\varnothing\ne G\subseteq F$, for all $\Cal{B}\in\bold{V}$, and for all homomorphisms $f\in\operatorname{Hom}(\Cal{A}_F,\Cal{B})$ and $g\in\operatorname{Hom}(\Cal{A}_F,\Cal{A}_G)$, there is a homomorphism $h\in\operatorname{Hom}(\Cal{A}_G,\Cal{B})$ such that $f=hg$. If $\Cal{A}_F$ is a finite structure for every nonempty set $F\in\Cal{P}_{fin}(\omega)$ then $\bold{A}$ a {\it finite\/} $\operatorname{B}^\ast$-{\it class with respect to\/} $\bold{M}$ {\it and\/} $\bold{V}$. \enddemo \demo{Remark 2.4} The $\operatorname{B}$-classes with respect to a quasivariety $\bold{M}\subseteq\bold{K}(\sigma)$ introduced in [3] are nothing else than the $\operatorname{B}^\ast$-classes with respect to $\bold{M}$ and the trivial variety $\bold{T}$. Moreover, each finite $\operatorname{B}^\ast$-class with respect to a variety and a quasivariety is a finite $\operatorname{AD}$-class according to [7, Proposition 3.3]. \enddemo \specialhead 2.3. $\operatorname{C}$-Classes \endspecialhead The following two definitions appear in [5]. \demo{Definition 2.5 \rm [4, Definition 5.1]} Let $\sigma$ be a finite similarity type, let $\bold{M}\subseteq\bold{K}(\sigma)$ be a quasivariety, and let $\bold{C}=\{\Cal{C}_n\mid n<\omega\}\subseteq\bold{M}$ be a class of nontrivial structures with the following properties: \itemitem{$(\operatorname{C}_1)$} \Label{D2.5(1)} For $m,n<\omega$, the structure $\Cal{C}_m$ embeds into the structure $\Cal{C}_n$ if and only if $m=n$. \itemitem{$(\operatorname{C}_2)$} \Label{D2.5(2)} For each $n<\omega$, the structure $\Cal{C}_n$ is $\bold{M}$-subdirectly irreducible and finitely presented in $\bold{M}$. Then $\bold{C}$ is called a $\operatorname{C}$-{\it class with respect to\/} $\bold{M}$. If the structure $\Cal{C}_n$ is finite for all $n<\omega$ then $\bold{C}$ is a~{\it finite\/} $\operatorname{C}$-{\it class with respect to\/} $\bold{M}$. \enddemo We note that the definition of {\it computable sequence\/}, a notion used below, can be found in the second paragraph of Section 6 in [4]. \demo{Definition 2.6 \rm [4, Definition 6.1]} Let $\bold{M}$ be a quasivariety and let $\bold{C}$ be a $\operatorname{C}$-class with respect to $\bold{M}$. Then $\bold{C}$ is an {\it effective\/} $\operatorname{C}$-{\it class with respect to\/} $\bold{M}$ if there is a computable sequence $\Delta=\{(X_n,\Delta_n,A_n)\mid n<\omega\}$, where for all $n<\omega$, $X_n=\{x_0,\dots,x_{l_n}\}$, $\Cal{C}_n\cong\Cal{F}_{\bold{M}}(X_n,\Delta_n)$, and $A_n(x_0,\dots,x_{l_n})$ is a monolith-generating atomic formula for $\Cal{C}_n$ in $\bold{M}$. \enddemo The next statement is a slight modification of [4, Theorem 6.5] and follows from its proof. \proclaim{Theorem 2.7} Let $\sigma$ be a finite similarity type, let $\bold{M}\subseteq\bold{K}(\sigma)$ be a quasivariety, and let $\bold{C}=\{\Cal{C}_n\mid n<\omega\}\subseteq\bold{M}$ be a finite $\operatorname{C}$-class with respect to $\bold{M}$. The following statements hold: \Item (i) There are continuum many quasivarieties $\bold{K}\subseteq\bold{M}$ which have an independent quasiequational basis relative to $\bold{M}$. \Item (ii) If $\bold{C}$ is a finite effective $\operatorname{C}$-class with respect to $\bold{M}$ then there are continuum many quasivarieties $\bold{K}\subseteq\bold{M}$ such that the finite membership problem is undecidable for $\bold{K}$, the quasiequational theory of $\bold{K}$ is undecidable, and $\bold{K}$ has an independent quasiequational basis relative to $\bold{M}$. \endproclaim \head 3. Main Results \endhead The following statement generalizes Lemma 5.2 in [4]. \proclaim{Proposition 3.1} Let $\sigma$ be a finite type and let $\bold{A}=\{\Cal{A}_F\mid F\in\Cal{P}_{fin}(\omega)\}\subseteq\bold{K}(\sigma)$ be a finite $\operatorname{AD}$-class possessing the following property \itemitem{$(\operatorname{P}_5)$} \Label{P3.1(5)} If $\alpha\colon\Cal{A}_{\{n\}}\to\prod_{i\in X}\Cal{A}_{\{i\}}$ is an embedding for some $n\in\omega$ and some finite nonempty set $X\subseteq\omega$ then $n\in X$ and $\pi_n\alpha$ is an embedding. Then $\bold{C}=\{\Cal{A}_{\{n\}}\mid n<\omega\}$ is a finite $\operatorname{C}$-class with respect to $\bold{Q}(\bold{A})$. \endproclaim \demo{Proof} It follows from conditions \Par{D2.1(1)}{$(\operatorname{P}_1)$} and \Par{D2.1(3)}{$(\operatorname{P}_3)$} in \Par*{Definition 2.1} that $\bold{C}$ consists of finite (and thus finitely presented in $\bold{Q}(\bold{A})$) nontrivial structures. Condition \Par{D2.5(1)}{$(\operatorname{C}_1)$} in \Par*{Definition 2.5} follows from condition \Par{D2.1(3)}{$(\operatorname{P}_3)$} in \Par*{Definition 2.1}. In order to prove \Par{D2.5(2)}{$(\operatorname{C}_2)$}, we fix $n<\omega$ and suppose that $\Cal{A}_{\{n\}}=\Cal{C}_n\leq_s\prod_{i\in I}\Cal{B}_i$ is a subdirect decomposition of $\Cal{C}_n$ such that $\Cal{B}_i\in\bold{Q}(\bold{A})$ for all $i\in I$. Since $\Cal{C}_n$ is a finite structure of finite type, $\Cal{C}_n\leq_s\prod_{i\in F}\Cal{B}_i$ for some finite nonempty set $F\subseteq I$. This means that, for each $i\in F$, there is an onto homomorphism $\alpha_i\colon\Cal{C}_n\to\Cal{B}_i$ such that $\Delta_{\Cal{C}_n}=\bigcap_{i\in F}\ker\alpha_i$. Without loss of generality, we may assume that $F$ is a minimal set with this property. Then we also have that, for all $i\in F$, $\Cal{B}_i$ is a finite nontrivial structure of finite type. Since $\Cal{B}_i\in\bold{Q}(\bold{A})$, we conclude by condition \Par{D2.1(2)}{$(\operatorname{P}_2)$} of \Par*{Definition 2.1} that $\Cal{B}_i\in\bold{Q}(\bold{C})$ for all $i\in F$. Hence, there are finite nonempty sets $Z_i\subseteq\omega$, $i\in F$, such that $\Cal{B}_i\leq\prod_{t\in Z_i}\Cal{C}_t$. We may again assume that the set $Z_i$ is minimal with respect to this property. Therefore, for each $i\in F$ and each $t\in Z_i$, there is an onto homomorphism $\beta_{it}\colon\Cal{B}_i\to\Cal{D}_t\leq\Cal{C}_t$ such that $$ \Delta_{\Cal{C}_n}=\bigcap\{\ker\beta_{it}\alpha_i\mid i\in F,\ t\in Z_i\}. $$ In particular, the map $\beta_{it}\alpha_i\colon\Cal{C}_n\to\Cal{C}_t$ is a homomorphism for all $i\in F$ and all $t\in Z_i$. Applying \Par{P3.1(5)}{$(\operatorname{P}_5)$}, we obtain that %\? $n\in Z_i$ for some $i\in F$ and that $\beta_{in}\alpha_i\colon\Cal{C}_n\to\Cal{C}_n$ is an embedding whence $\alpha_i\colon\Cal{C}_n\to\Cal{B}_i$ is an isomorphism. This proves the subdirect irreducibility of $\Cal{C}_n$ in $\bold{Q}(\bold{C})$. \qed\enddemo \proclaim{Lemma 3.2} If a quasivariety $\bold{M}\subseteq\bold{K}(\sigma)$ contains a finite $\operatorname{B}^\ast$-class $\bold{A}=\{\Cal{A}_F\mid F\in\Cal{P}_{fin}(\omega)\}$ with respect to $\bold{M}$ and a variety $\bold{V}\subseteq\bold{K}(\sigma)$ then $\bold{A}$ is a finite $\operatorname{AD}$-class satisfying the %\?убрать condition \Par{P3.1(5)}{$(\operatorname{P}_5)$}. In particular, $\bold{C}=\{\Cal{A}_{\{n\}}\mid n<\omega\}$ is a finite $\operatorname{C}$-class with respect to $\bold{M}$. \endproclaim \demo{Proof} It follows from [7, Proposition 3.3] that $\bold{A}$ is a finite $\operatorname{AD}$-class with respect to $\bold{M}$. For all $i<\omega$, we put $\Cal{C}_i=\Cal{A}_{\{i\}}$ for the sake of brevity. Furthermore, let $n<\omega$ and a finite nonempty set $F\subseteq\omega$ be such that $\alpha\colon\Cal{C}_n\to\prod_{i\in F}\Cal{C}_i$ is an embedding. Since $\Cal{C}_n\notin\bold{V}$ by [7, Lemma 1.3\itm(i)], we conclude that there is $i\in F$ such that $\pi_i\alpha(\Cal{C}_n)\notin\bold{V}$. By condition \Par{P3.1(5)}{$(\operatorname{P}_5)$}, this means that $\pi_i\alpha(\Cal{C}_n)=\pi_i\alpha(\Cal{A}_{\{n\}})\cong\Cal{A}_G$ for some finite nonempty set $G\subseteq\omega$. Then the inclusion $G\subseteq\{n\}$ follows by [7, Lemma 1.3\itm(iii)]. Hence, $G=\{n\}$. Since $\Cal{C}_n$ is a finite structure, we conclude that $\pi_i\alpha$ is an isomorphism and condition \Par{P3.1(5)}{$(\operatorname{P}_5)$} follows. The last statement follows from \Par*{Proposition 3.1}. \qed\enddemo \head 4. Applications \endhead We present in this section some applications of \Par*{Theorem 2.7} and \Par*{Proposition 3.1}. \proclaim{Theorem 4.1}\Label{T4.1} Let $\bold{K}$ be one of the following classes: \Item (a) the quasivariety of pseudocomplemented semilattices generated by the $3$-element chain; \Item (b) the locally variety $\bold{A}_i$, where $i<\omega$, of $(0,1)$-lattices constructed in {\rm [11]}; \Item (c) the variety of idempotent semigroups. Then there is a quasivariety $\bold{M}\subseteq\bold{K}$ which contains continuum many $Q$-universal subquasivarieties $\bold{M}^\prime\subseteq\bold{M}$ such that the finite membership problem is undecidable for $\bold{M}^\prime$, the quasiequational theory of $\bold{M}^\prime$ is undecidable, and $\bold{M}^\prime$ has an independent quasiequational basis relative to $\bold{M}$. \endproclaim \demo{Proof} For each of the classes listed in \Par{T4.1}{(a)}--\Par{T4.1}{(c)}, an effective procedure was given by M.E. Adams {\it et al.} %\? in the papers [12,\,11,\,13] %\?[11--13] respectively to construct a finite $\operatorname{AD}$-class $\bold{A}$. That this $\operatorname{AD}$-class $\bold{A}$ possesses property \Par{P3.1(5)}{$(\operatorname{P}_5)$} follows from [12, Proposition 4.3; 11, Lemma 3.6; 13, Lemma 4.5] %\?[11, Lemma 3.6; 12, Proposition 4.3; 13, Lemma 4.5] respectively. By \Par*{Proposition 3.1}, the quasivariety $\bold{Q}(\bold{A})$ contains an effective $\operatorname{C}$-class with respect to $\bold{Q}(\bold{A})$. The desired statement follows from \Par*{Theorem 2.2} and \Par*{Theorem 2.7}. \qed\enddemo \demo{Remark 4.2} In view of \Par*{Proposition 3.1} and \Par*{Lemma 3.2}, the results of [4, Corollary 7.8] and from~[7] %\?of [7] follow from \Par*{Theorem 2.7} in a uniform way. Other examples where \Par*{Proposition 3.1} and \Par*{Lemma 3.2} apply to obtain the conclusion of \Par*{Theorem~4.1} can be found in M.E. Adams and W. Dziobiak [14,\,15] as well as in V. Koubek and J. Sichler [16--19]. \enddemo \Refs \ref\no 1 \by Adams~M.E. and Dziobiak~W. \paper $Q$-Universal quasivarieties of algebras \jour Proc. Amer. Math. Soc. \yr 1994 \vol 120 \issue 4 \pages 1053--1059 \endref \ref\no 2 \by Gorbunov~V.A. \book Algebraic Theory of Quasivarieties \publaddr New York \publ Plenum \yr 1998 % \finalinfo Siberian School of Algebra and Logic \endref \ref\no 3 \by Kravchenko~A.V., Nurakunov~A.M., and Schwidefsky~M.V. \paper Structure of quasivariety lattices. I. Independent axiomatizability \jour Algebra Logic \yr 2018 \vol 57 \issue 6 \pages 445--462 \endref \ref\no 4 \by Kravchenko~A.V., Nurakunov~A.M., and Schwidefsky~M.V. \paper Structure of quasivariety lattices.~IV. Nonstandard quasivarieties \jour Sib. Math.~J. \yr 2021 \vol 62 \issue 5 \pages 850--858 \endref \ref\no 5 \by Kravchenko~A.V., Nurakunov~A.M., and Schwidefsky~M.V. \paper Structure of quasivariety lattices.~II. Undecidable problems \jour Algebra Logic \yr 2019 \vol 58 \issue 2 \pages 123--136 \endref \ref\no 6 \by Kravchenko~A.V., Nurakunov~A.M., and Schwidefsky~M.V. \paper Structure of quasivariety lattices. III. Finitely partitionable bases \jour Algebra Logic \yr 2020 \vol 59 \issue 3 \pages 222--229 \endref \ref\no 7 \by Schwidefsky~M.V. \paper Existence of independent quasi-equational bases \jour Algebra Logic \yr 2020 \vol 58 \issue 6 \pages 514--537 \endref \ref\no 8 \by Schwidefsky~M.V. \paper The complexity of quasivariety lattices. II \jour Sib. Electr. Math. Reports \yr 2023 \vol 20 \issue 1 \pages 501--513 \endref \ref\no 9 \by Schwidefsky~M.V. \paper On the existence of independent quasi-equational bases. II \jour Algebra Logic \yr 2023 \vol 62 \issue 6 \pages 516--531 \endref \ref\no 10 \by Schwidefsky~M.V. \paper On the complexity of quasivariety lattices \jour Algebra Logic \yr 2015 \vol 54 \issue 3 \pages 245--257 \endref \ref\no 11 \by Adams~M.E. and Dziobiak~W. \paper $Q$-Universal varieties of bounded lattices \jour Algebra Universalis \yr 2002 \vol 48 \issue 3 \pages 333--356 \endref \ref\no 12 \by Adams~M.E., Dziobiak~W., Gould~M., and Schmid~J. \paper Quasivarieties of pseudocomplemented semilattices \jour Fund. Math. \yr 1995 \vol 146 \issue 3 \pages 295--312 \endref \ref\no 13 \by Adams~M.E. and Dziobiak~W. \paper Quasivarieties of idempotent semigroups \jour Internat. J. Algebra Comput. \yr 2003 \vol 13 \issue 6 \pages 733--752 \endref \ref\no 14 \by Adams~M.E. and Dziobiak~W. \paper Lattices of quasivarieties of $3$-element algebras \jour J. Algebra \yr 1994 \vol 166 \issue 1 \pages 181--210 \endref \ref\no 15 \by Adams~M.E. and Dziobiak~W. \paper Joins of minimal quasivarieties \jour Studia Logica \yr 1995 \vol 54 \issue 3 \pages 371--389 \endref \ref\no 16 \by Koubek~V. and Sichler~J. \paper Universality of small lattice varieties \jour Proc. Amer. Math. Soc. \yr 1984 \vol 91 \issue 1 \pages 19--24 \endref \ref\no 17 \by Koubek~V. and Sichler~J. \paper On almost universal varieties of modular lattices \jour Algebra Universalis \yr 2001 \vol 45 \iftex \issue 2--3 \else \issue 2 \fi \pages 191--210 \endref \ref\no 18 \by Koubek~V. and Sichler~J. \paper Almost $ff$-universal and $Q$-universal varieties of modular 0-lattices \jour Colloq. Math. \yr 2004 \vol 101 \issue 2 \pages 161--182 \endref \ref\no 19 \by Koubek~V. and Sichler~J. \paper Finitely generated almost universal varieties of $0$-lattices \jour Comment. Math. Univ. Carolin. \yr 2005 \vol 46 \issue 2 \pages 304--325 \endref \endRefs \enddocument