Computable set theory. Vol. 1. (English) Zbl 0755.03024

International Series of Monographs on Computer Science. 6. Oxford: Univ. Press. XII, 347 p. (1989).
This book brings together work of the authors and of others on fragments of set theory. For the most part these fragments consist of collections of quantifier-free formulas in a relational language richer than just the one with \(\varepsilon\) and =. The issue is usually wether these fragments have a decidable satisfiability problem where variables are interpreted by finite sets or by hereditarily finite sets. The authors present a host of positive results. These achievements tend to build on each other as more primitives are added and decidability maintained. The new proofs may, however, require new techniques.
The text itself begins with an introductory chapter, where the motivation for this line of inquiry is described and an overview of the book’s contents is given. The remainder of the text is in two parts:
Part I, Fundamentals, has six chapters. The first of these describes the informal meta-set theory in which the authors operate. It is essentially a Kelly-Morse theory with a rank respecting well-ordering of the universe. The second chapter gives the syntactical and semantical setting for the results that follow. The rest of part I (4 chapters) presents specific results and techniques. Chapter 7 is noteworthy, since it is the place where positive results for quantified formulae are reported.
Part II, Extended Multilevel Syllogistics, has four chapters. Three of these are devoted to particular operators — powerset, unionset, and choice. Chapter 9 concerns the addition of operators and relations to the language in order to express properties of mappings.
The book lacks a general index. It does have an index of referenced statements.


03E30 Axiomatics of classical set theory and its fragments
03B25 Decidability of theories and sets of sentences
03-02 Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations