A decidable quantified fragment of set theory with ordered pairs and some undecidable extensions

• Published in: Electronic proceedings in theoretical computer science 2012-10, Vol.96 (Proc. GandALF 2012), p.224-237
• Main Authors: Cantone, Domenico, Longo, Cristiano
• Format: Article
• Language: English
• ISSN: 2075-2180; 2075-2180
• DOI: 10.4204/EPTCS.96.17

In this paper we address the decision problem for a fragment of set theory with restricted quantification which extends the language studied in [4] with pair related quantifiers and constructs, in view of possible applications in the field of knowledge representation. We will also show that the decision problem for our language has a non-deterministic exponential time complexity. However, for the restricted case of formulae whose quantifier prefixes have length bounded by a constant, the decision problem becomes NP-complete. We also observe that in spite of such restriction, several useful set-theoretic constructs, mostly related to maps, are expressible. Finally, we present some undecidable extensions of our language, involving any of the operators domain, range, image, and map composition. [4] Michael Breban, Alfredo Ferro, Eugenio G. Omodeo and Jacob T. Schwartz (1981): Decision procedures for elementary sublanguages of set theory. II. Formulas involving restricted quantifiers, together with ordinal, integer, map, and domain notions. Communications on Pure and Applied Mathematics 34, pp. 177-195