Decision Problem for Separated Distributive Lattices
Gurevich, Yuri
J. Symbolic Logic, Tome 48 (1983) no. 1, p. 193-196 / Harvested from Project Euclid
Text on Project Euclid
PDF
Alt PDF
It is well known that for all recursively enumerable sets $X_1, X_2$ there are disjoint recursively enumerable sets $Y_1, Y_2$ such that $Y_1 \subseteq X_1, Y_2 \subseteq X_2$ and $Y_1 \cup Y_2 = X_1 \cup X_2$. Alistair Lachlan called distributive lattices satisfying this property separated. He proved that the first-order theory of finite separated distributive lattices is decidable. We prove here that the first-order theory of all separated distributive lattices is undecidable.
Publié le : 1983-03-14
Classification:  
@article{1183741204,
     author = {Gurevich, Yuri},
     title = {Decision Problem for Separated Distributive Lattices},
     journal = {J. Symbolic Logic},
     volume = {48},
     number = {1},
     year = {1983},
     pages = { 193-196},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183741204}
}

Gurevich, Yuri. Decision Problem for Separated Distributive Lattices. J. Symbolic Logic, Tome 48 (1983) no. 1, pp.  193-196. http://gdmltest.u-ga.fr/item/1183741204/