Small Substructures and Decidability Issues for First-Order Logic with Two Variables
Emanuel Kieroński, Martin Otto · 2006
We study first-order logic with two variables FO/sup 2/ and establish a small substructure property. Similar to the small model property for FO/sup 2/ we obtain an exponential size bound on embedded substructures, relative to a fixed surrounding structure that may be infinite. We apply this technique to analyse the satisfiability problem for FO/sup 2/ under constraints that require several binary relations to be interpreted as equivalence relations. With a single equivalence relation, FO/sup 2/ has the finite model property and is complete for non-deterministic exponential time, just as for plain FO/sup 2/. With two equivalence relations, FO/sup 2/ does not have the finite model property, but is shown to be decidable via a construction of regular models that admit finite descriptions even though they may necessarily be infinite. For three or more equivalence relations, FO/sup 2/ is undecidable.