8
$\begingroup$

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$?

$\endgroup$

2 Answers 2

8
$\begingroup$

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.

$\endgroup$
10
  • 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$ May 4, 2014 at 19:48
  • $\begingroup$ Yes, my gut feeling also is that the general problem is undecidable. $\endgroup$ 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$ 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$
    – Rob Myers
    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$ May 5, 2014 at 17:41
2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Isn’t this the same argument as in the first paragraph of my answer? $\endgroup$ May 7, 2014 at 14:51
  • $\begingroup$ Seems that way. I read your answer a week ago and forgot. $\endgroup$ 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$ May 7, 2014 at 14:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.