# Is HSP(A) = ISP(A) decidable?

Let $A$ be a finite algebra for some finitary signature.

Is it decidable whether $\mathbb{H}\mathbb{S}\mathbb{P}(A) = \mathbb{I}\mathbb{S}\mathbb{P}(A)$?

That is, whether the variety generated by $A$ equals the quasivariety generated by $A$?

-

First, note that the problem is $\Pi^0_1$: $\mathrm{HSP}(A)=\mathrm{ISP}(A)$ iff every quasiidentity valid in $A$ holds in $\mathrm{HSP}(A)$. The latter can be algorithmically checked, as a quasiidentity in $n$ variables that fails in an algebra from $\mathrm{HSP}(A)$ also fails in an $n$-generated such algebra, i.e., a quotient of the free $\mathrm{HSP}(A)$-algebra over $n$ generators. The latter is finite and can be explicitly computed.

For various classes of algebras, the problem is in fact decidable.

For a simple case, $\mathrm{HSP}(A)=\mathrm{ISP}(A)$ is decidable if it is known a priori that $V=\mathrm{HSP}(A)$ is congruence-distributive. Namely, $V$ is ISP-generated by its subdirectly irreducible algebras, and by Jónsson’s lemma, these are all in $\mathrm{HS}(A)$. Moreover, a subdirectly irreducible algebra is in $\mathrm{ISP}(A)$ iff it is in $\mathrm{IS}(A)$. It is decidable whether a finite algebra is subdirectly irreducible, hence you can test whether $\mathrm{HSP}(A)=\mathrm{ISP}(A)$ by enumerating all subdirectly irreducible algebras in $\mathrm{HS}(A)$ (up to isomorphism, there are only finitely many), and checking that each is in $\mathrm{IS}(A)$.

More generally, assume that $A$ comes from a class of algebras such that we can compute a finite upper bound $b$ on the size of subdirectly irreducible algebras in $\mathrm{HSP}(A)$, or determine that there is no bound. (Such classes of algebras are said to satisfy the recursive RS conjecture.) Then $\mathrm{HSP}(A)=\mathrm{ISP}(A)$ iff $b$ exists and all s.i. algebras from $\mathrm{HSP}(A)$ of size at most $b$ are in $\mathrm{IS}(A)$, which is a decidable criterion.

Various results related to the RS conjecture are summarized in [1]. In particular, $\mathrm{HSP}(A)=\mathrm{ISP}(A)$ is decidable in the following cases:

• $\mathrm{HSP}(A)$ is congruence-modular (Thm. 4.2, due to Freese and McKenzie).

• More generally, if the congruence lattices of all algebras in $\mathrm{HSP}(A)$ satisfy a nontrivial lattice equation (Thm. 5.13, due to Hobby and McKenzie).

• $\mathrm{HSP}(A)$ is abelian (Thm. 6.17, due to Kearnes, Kiss, and Valeriote).

On the other hand, the recursive RS conjecture is false in general (Thm. 6.5, McKenzie). This suggests that $\mathrm{HSP}(A)=\mathrm{ISP}(A)$ might also be undecidable in full generality, however this does not seem to directly follow from any of the result I could find.

Reference:

[1] Ross Willard, An overview of modern universal algebra, in: Logic Colloquium 2004 (eds. A. Andretta, K. Kearnes, and D. Zambella), Lecture Notes in Logic, vol. 29, Cambridge University Press, 2008, pp. 197–220.

-
In contrast there are results e.g. Japheth Wood's "Type 4 is not computable", which suggests to me that the general problem is undecidable. This is only a suggestion; I have no proof that one has a bearing on the other. – The Masked Avenger May 4 '14 at 19:48
Yes, my gut feeling also is that the general problem is undecidable. – Emil Jeřábek May 4 '14 at 20:10
I can’t access JSTOR from home, but there may be something relevant to the general problem in jstor.org/stable/2695083 or among its references. – Emil Jeřábek May 4 '14 at 20:28
Thanks, that's very useful to know. I am also interested in the case where all of $A$'s operations commute. The generated commutative variety is rarely (perhaps never) congruence-distributive because e.g. $y = f(f(x,y,y),f(x,y,x),f(y,y,x)) = f(f(x,x,y),f(y,y,y),f(y,x,x)) = x$. Do you know of any techniques to handle such cases? Any help much appreciated. – Rob Myers May 4 '14 at 20:34
I hope I am not confusing various definitions of abelian/commutative algebras, however it seems your case is covered by the result quoted as Theorem 6.17 in Willard’s paper. – Emil Jeřábek May 5 '14 at 17:41

The paper www.math.uwaterloo.ca/~snburris/htdocs/MYWORKS/PAPERS/Reducts.pdf may be relevant. It proves that given a finite set of quasiidentities defining a quasivariety generated by a finite algebra $A$ you can decide if the quasivariety is a variety. Other related results are there.

-
Isn’t this the same argument as in the first paragraph of my answer? – Emil Jeřábek May 7 '14 at 14:51
Seems that way. I read your answer a week ago and forgot. – Benjamin Steinberg May 7 '14 at 14:56
The Burris paper also shows it is undec if a finite set of quasi identities defines a variety. – Benjamin Steinberg May 7 '14 at 14:57