Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question

2 Answers 2

up vote 7 down vote accepted

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.

share|improve this answer
1  
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 at 19:48
    
Yes, my gut feeling also is that the general problem is undecidable. –  Emil Jeřábek May 4 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 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 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 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.

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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