Decidability of Cylindric Set Algebras of Dimension Two and First-Order Logic with Two Variables
Abstract
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, using a combinatorial theorem due to Herwig. The results are proved in the framework of polyadic equality set algebras of dimension two. 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.