Decidability results for sets with atoms

• Published in: ACM transactions on computational logic 2006-04, Vol.7 (2), p.269-301
• Main Authors: Dovier, Agostino, misano, Andrea, Omodeo, Eugenio G
• Format: Article
• Language: English
• Subjects: Algorithms; Atoms & subatomic particles; Logic; Set theory; Studies; Theory
• ISSN: 1529-3785; 1557-945X
• DOI: 10.1145/1131313.1131317

Formal set theory is traditionally concerned with pure sets; consequently, the satisfiability problem for fragments of set theory was most often addressed (and in many cases positively solved) in the pure framework. In practical applications, however, it is common to assume the existence of a number of primitive objects (sometimes called atoms ) that can be members of sets but behave differently from them. If these entities are assumed to be devoid of members, the standard extensionality axiom must be revised; then decidability results can sometimes be achieved via reduction to the pure case and sometimes can be based on direct goal-driven algorithms. An alternative approach to modeling atoms that allows one to retain the original formulation of extensionality was proposed by Quine: atoms are self-singletons. In this article we adopt this approach in coping with the satisfiability problem: We show the decidability of this problem relativized to ∃*∀-sentences, and develop a goal-driven unification algorithm.