Non-Well-Founded Sets

Foreword To my way of thinking, mathemtical logic is a branch of applied mathematics. It applies mathematics to model and study various sorts of symbolic systems: axioms, proofs, programs, computers, or people talking and reasoning together. This is the only view of mathematical logic which does justice to the logician's intuition that logic really is a field, not just the union of several unrelated fields. One expects that logic, 88 a branch of applied mathematics, will not only use existing tools from mathematics, but also that it will lead to the creation of new mathematical tools, tools that arise out of the need to model some real world phenomena not ad- equately modeled by previously known mathematical structures. Turing's analysis of the notion of algorithm by means of Turing machines is an obvious example. In this way, by reaching out and studying new pheonemona, applied mathematics in general, and mathematical logic in particular, enriches mathematics, not only with new theorems, but also with new mathematical structures, structures for the mathematician to study and for others to apply in new domains. The theory of circular and otherwise extra-ordinary sets pre- sented in this book is an excellent example of this synergistic process. Aczel's work W88 motivated by work of Robin Milner in computer science modeling concurrent processes. The fact that these processes are inherently circular makes them awkward to model in traditonal set theory, since most straightforward ideas run afoul of the axiom of foundation. As a result, Milner's own treatment was highly syntactic. Aczel's original aim was to find a version of set theory where these circular phenomena could be modeled in a straightforward way, using standard techniques from set theory. This forced him to develop an alternative conception of set, the conception that lies at the heart of this book. Aczel returns to his starting point in the final chapter of this book. Before learning of Aczel's work, I had run up against similar difficulties in my work in situation theory and situation seman- tics. It seemed that in order to understand common knowledge (a crucial feature of communication), circular propositions, vari- ous aspects of perceptual knowledge and self-awareness, we had to admit that there are situations that are not wellfounded under the "constituent of' relation. This meant that the most natural route to modeling situations was blocked by the axiom of founda- tion. As a result, we either had to give up the tools of set theory which are so well loved in mathematical logic, or we had to enrich the conception of set, finding one that admits of circular sets, at least. I wrestled with this dilemma for well over a year before I argued for the latter move in (Barwise 1986). It was at just this point that Aczel visited CSLI and gave the seminar which formed the basis of this book. Since then, I have found several applications of Aczel's set theory, far removed from the problems in computer science that originally motivated Aczel. Others have gone on to do interesting work of a strictly mathematical nature exploring this expanded universe of sets. I feel quite certain that there is still a lot to be done with this universe of sets, on both fronts, that there are mathematical prob- lems to be solved, and further applications to be found. However, there is a serious linguistic obstacle to this work, arising out of the dominance of the cumulative conception of set. Just as there used to be complaints about referring to complex numbers as numbers, so there are objections to referring to non-well-founded sets as sets. While there is clear historical justification for this usage, the objection persists and distracts from the interest and importance of the subject. However, I am convinced that readers who approach this book unencumbered by this linguistic prob- lem will find themselves amply rewarded for their effort. The AFA theory of non-well-founded sets is a beautiful one, full of po- tential for mathematics and its applications to symbolic systems. I am delighted to have played a small role, as Director of CSLI during Aczel's stay, in helping to bring this book into existence. JON BARWISE