RUS  ENG
Full version
JOURNALS // Algebra i logika // Archive

Algebra Logika, 2015 Volume 54, Number 3, Pages 381–398 (Mi al699)

This article is cited in 17 papers

Complexity of quasivariety lattices

M. V. Schwidefskyab

a Sobolev Institute of Mathematics, pr. Akad. Koptyuga 4, Novosibirsk, 630090, Russia
b Novosibirsk State University, ul. Pirogova 2, Novosibirsk, 630090, Russia

Abstract: 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.

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

UDC: 512.56+512.57+510.53

Received: 17.09.2014
Revised: 03.05.2015

DOI: 10.17377/alglog.2015.54.305


 English version:
Algebra and Logic, 2015, 54:3, 245–257

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2026