Decidability of Cylindric Set Algebras of Dimension Two and First-Order Logic with Two Variables
Marx, Maarten ; Mikulas, Szabolcs
J. Symbolic Logic, Tome 64 (1999) no. 1, p. 1563-1572 / Harvested from Project Euclid
The aim of this paper is to give a new proof for the decidability and finite model property of first-order logic with two variables (without function symbols), using a combinatorial theorem due to Herwig. The results are proved in the framework of polyadic equality set algebras of dimension two (Pse$_2$). The new proof also shows the known results that the universal theory of Pse$_2$ is decidable and that every finite Pse$_2$ can be represented on a finite base. Since the class Cs$_2$ of cylindric set algebras of dimension 2 forms a reduct of Pse$_2$, these results extend to Cs$_2$ as well.
Publié le : 1999-12-14
Classification: 
@article{1183745938,
     author = {Marx, Maarten and Mikulas, Szabolcs},
     title = {Decidability of Cylindric Set Algebras of Dimension Two and First-Order Logic with Two Variables},
     journal = {J. Symbolic Logic},
     volume = {64},
     number = {1},
     year = {1999},
     pages = { 1563-1572},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183745938}
}
Marx, Maarten; Mikulas, Szabolcs. Decidability of Cylindric Set Algebras of Dimension Two and First-Order Logic with Two Variables. J. Symbolic Logic, Tome 64 (1999) no. 1, pp.  1563-1572. http://gdmltest.u-ga.fr/item/1183745938/