UNREASONABLE LATTICES OF QUASIVARIETIES

A quasivariety is a universal Horn class of algebraic structures containing the trivial structure. The set Lq(R) of all subquasivarieties of a quasivariety R forms a complete lattice under inclusion. A lattice isomorphic to Lq(R) for some quasivariety R is called a lattice of quasivarieties or a quasivariety lattice. The Birkhoff-Maltsev Problem asks which lattices are isomorphic to lattices of quasivarieties. A lattice L is called unreasonable if the set of all finite sublattices of L is not computable, that is, there is no algorithm for deciding whether a finite lattice is a sublattice of L. The main result of this paper states that for any signature sigma containing at least one non-constant operation, there is a quasivariety R of signature sigma such that the quasivariety lattice Lq(R) is unreasonable. Moreover, there are uncountable unreasonable lattices of quasivarieties. We also present some corollaries of the main result.