A survey of computable set theory
Abstract
This paper surveys various decidability results in the set theory. In the first part, we focus on certain classes of unquantified set-theoretic formulae involving the relations ∊ “membership”, = “equality”, and the operators ⋂ “intersection”, ⋃ “binary union”, \ “set difference”, ⋅ “singleton”, pow “powerset”, Un“general union”, η “choice operator”, etc. The unquantified theory basic to the results presented is the so called Multilevel Syllogistic (MLS) which is the set of all quantifier-free formulae in the language ∊, =, ⋂, ⋃ ,\ .
The second part of the paper covers the quantified case and, among others, we consider: a quantified version of MLS, the class of formulae quantified over sets in which the membership predicate is not allowed, the class of prenex set-theoretic formulae having three quantifiers and the class having a prefix of the form ∀∀ ... ∀∃ .
In the third part, some applications to domains different from pure set theory will be reviewed.
Some undecidability results will be discussed in the last section.
An appendix on Zermelo-Fraenkel set-theory concludes the paper.
Downloads
Published
Issue
Section
License
The authors retain all rights to the original work without any restrictions.
License for Published Contents
"Le Matematiche" published articlesa are distribuited with Creative Commons Attribution 4.0 International. You are free to copy, distribute and transmit the work, and to adapt the work. You must attribute the work in the manner specified by the author or licensor (but not in any way that suggests that they endorse you or your use of the work).
License for Metadata
"Le Matematiche" published articles metadata are dedicated to the public domain by waiving all publisher's rights to the work worldwide under copyright law, including all related and neighboring rights, to the extent allowed by law.
You can copy, modify, distribute and perform the work, even for commercial purposes, all without asking permission.
No Fee Charging
No fee is required to complete the submission/review/publishing process of authors paper.
