Decision Problem for Separated Distributive Lattices

  • Yuri Gurevich

Journal of Symbolic Logic | , Vol 48: pp. 193-196

It is well known that for all recursively enumerable sets X1, X2 there are disjoint recursively enumerable sets Y1, Y2 such that Yi is a subset of Xi and (Y1 ∪ Y2) = (X1 ∪ X2). Alistair Lachlan called distributed lattices satisfying this property separated. He proved that the first-order theory of finite separated distributed lattices is decidable. We prove here that the first-order theory of all separated distributed lattices is undecidable.