Complexity of quasivariety lattices

M. V. Schwidefsky

Algebra i logika, Tome 54 (2015) no. 3, pp. 381-398

Résumé

If a quasivariety $\mathbf A$ of algebraic systems of finite signature satisfies some generalization of a sufficient condition for $Q$-universality treated by M. E. Adams and W. A. Dziobiak, then, for any at most countable set $\{\mathcal S_i\mid i\in I\}$ of finite semilattices, the lattice $\prod_{i\in I}\operatorname{Sub}(\mathcal S_i)$ is a homomorphic image of some sublattice of a quasivariety lattice $\operatorname{Lq}(\mathbf A)$. Specifically, there exists a subclass $\mathbf{K\subseteq A}$ such that the problem of embedding a finite lattice in a lattice $\operatorname{Lq}(\mathbf K)$ of $\mathbf K$-quasivarieties is undecidable. This, in particular, implies a recent result of A. M. Nurakunov.

Détail

Keywords: computable set, lattice, quasivariety, $Q$-universality, undecidable problem, universal class, variety.