Distributive lattices with a decidable monadic second order theory. (Q1771945)

Monadic second-order logic lies between elementary and second-order logic, it allows to quantify over sets, but not over relations of arity at least 2 or, equivalently, quantification is restricted to unary relations. The decidability of the elementary theory of all finite members of a variety has attracted considerable interest. It is known that no variety of lattices containing a non-singleton lattice has this nice property. Due to this negative result, the author considers arbitrary classes of finite distributive lattices. He proves that a class of finite distributive lattices has a decidable monadic second-order theory iff the join irreducible elements of its members have a decidable second-order theory and the width of the lattices is bounded. Similar results are obtained for the monadic chain and the monadic antichain theory where quantification is restricted to chains and antichains, respectively. Furthermore, it is shown that there is no maximal set of finite distributive lattices with a finite decidable monadic theory.