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$?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
10
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.
answered May 4, 2014 at 19:23
-
1$\begingroup$ 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. $\endgroup$ Commented May 4, 2014 at 19:48
-
$\begingroup$ Yes, my gut feeling also is that the general problem is undecidable. $\endgroup$ Commented May 4, 2014 at 20:10
-
$\begingroup$ 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. $\endgroup$ Commented May 4, 2014 at 20:28
-
$\begingroup$ 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. $\endgroup$ Commented May 4, 2014 at 20:34
-
$\begingroup$ 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. $\endgroup$ Commented May 5, 2014 at 17:41
$\begingroup$
$\endgroup$
3
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.
answered May 7, 2014 at 13:03
-
$\begingroup$ Isn’t this the same argument as in the first paragraph of my answer? $\endgroup$ Commented May 7, 2014 at 14:51
-
$\begingroup$ Seems that way. I read your answer a week ago and forgot. $\endgroup$ Commented May 7, 2014 at 14:56
-
1$\begingroup$ The Burris paper also shows it is undec if a finite set of quasi identities defines a variety. $\endgroup$ Commented May 7, 2014 at 14:57