School of Computer and Information Science, Syracuse University, Syracuse, NY
This textbook presents a novel approach to set theory that is entirely operational. This approach avoids the existential axioms that are associated with traditional Zermelo-Fraenkel set theory, endeavoring to provide both a foundations for set theory and a practical approach to learning the subject. It is written at the professional-graduate student level, and will be of interest to mathematical logicians, philosophers of mathematics, and students of theoretical computer science. A Guide to the Exercises is available to instructors who intend to use the book in the classroom (send request to sanchis@top.cis.syr.edu).
The book is recommended for graduate classes and undergraduate senior classes with some mathematical maturity and some background in set theory via a good course in discrete mathematics. Students in computer science will enjoy the crucial role that induction and recursion plays in this presentation. On the other hand, students in philosophy will profit from the explicit philosophical discussions.
The point this work tries to make is that set theory deals with some type of reality, only it is an ambiguous sort of reality. In particular, the universe of sets cannot be constructed as a complete collection where global quantification is legitimate. More precisely, the role of set theory is to make explicit different possible constructions where sets are derived from given sets. At the same time the fact must be recognized that there is no actual construction for the universe of sets, and this situation must be taken into account in the formulation of the theory.
This distinction is expressed by means of a classical terminology in the foundations of mathematics. Constructions that involve the universe are called impredicative. As a consequence, this work is committed to constructions that are predicative (i.e., non-impredicative). This implies a large view of what is predicative, that goes beyond the usual practice. In particular, it is legitimate to accept constructions where a set is introduced by a reference to a totality that contains the set, provided such a totality has been introduced by a legitimate (= predicative) construction. References to the universe are not predicative, because there is no predicative construction of the universe. In this monograph references to a complete universe are eliminated via a formal system consisting of set operation rules and set predicate rules, where every rule is derived from some objective construction involving sets from the universe, but not the universe itself. Such constructions must be objective, in the sense that they are completely determined independently of the universe. On the other hand, an objective construction may involve a transcendental or creative element that goes beyond the given sets. The basic premise in this work is that in spite of such creativeness, a construction involving a reference to the universe as a complete totality is not objective, and as a consequence is not admissible.
For example, the standard ``definition'' of the power-set of a set $X$, as the collection of all subsets of $X$ is not objective in the sense explained above. The reason is that this is an impredicative construction, since the potential sets to be selected by the property of being a subset of $X$ are taken from the universe. Actually, the definition says that the elements of the power-set of $X$ are those sets in the universe that are subsets of $X$. In Chapter 8 a predicative construction of the power-set is given that involves the axiom of choice.
The system is described by means of rules that introduce set predicates and set operations. In particular, there is a rule of set induction that allows the introduction of inductive predicates, and a rule of set recursion (relative to a previously defined predicate) for recursive set operations. When the predicate is "ordinal" this rules provides for standard transfinite recursion. The book contains two chapters where the logic of the system is formalized via Gentzen sequent rules. While the classical system applies to local expressions, we require intuitionistic logic to deal with non-local expressions.
MORE INFORMATION ABOUT THE BOOK is available as follows: a)CORRECTIONS: A file with errors in the text and the required corrections. Send empty message with subject:CORRECTIONS, to sanchis@top.cis.syr.edu.
b)EXERCISES: A file with solutions to the exercises in the book. Send empty message with subject:EXERCISES, to sanchis@top.cis.syr.edu.
CHAPTER 1, Operations and Predicates
CHAPTER 2, Replacement
CHAPTER 3, Set Induction
CHAPTER 4, Applications
CHAPTER 5, Set Recursion
CHAPTER 6, Ordinals
CHAPTER 7, Omega
CHAPTER 8, Power-Set and Cardinals
CHAPTER 9, Formalization: Classical Logic
CHAPTER 10, Formalization: Intuitionistic Logic
APPENDIX A, Enumeration
BIBLIOGRAPHY
PRIMITIVE RULES
FORMAL DEFINITIONS
INDEX
Published by Gordon and Breach, 1996