FOM: Non-Well-Founded Sets

[Allen Hazen]

   A couple of weeks ago, I typed up some notes on how I see the history of
this topic. I hope they are of some interest:
   	Notes on Non-well-founded sets.
	In his presentation to the Melbourne Philosophy Colloquium,
19.v.2000, C.A. Anderson presented a theorem depending on the set-theoretic
axiom of Foundation, defending this by saying he knew that there were
theories without this axiom, but that he was interested in "sets, not
schmets."  This struck me because, a decade or so back, this not only would
have been but was my response to the idea of non-well-founded sets.
	The idea that axiomatic set theory is an effort to describe the
universe of well-founded sets-- the so-called iterative conception of set--
seems to have been part of the common lore of workers in the field long
before it was widely appreciated in the general philosophical community.
(My guess is that G=F6del's work on the consistency of AC and CH  had done
much to make set theorists aware of the cumulative hierarchy of w.f. sets.
Ironically, since his proofs make use of the sub-hierarchy L!)  The general
impression among philosophers was that the ZF axioms (other than
extensionality) were an unprincipled ("arbitrary") collection of instances
of comprehension, justified only by the empirical finding that they allowed
the derivation of nice set theory without allowing the known paradoxes.
McNaughton's papers on "conceptual schemes" in set theory ("Philosophical
Review" 66 (1957) and "Philosophy of Science" 21 (1954)) did not suffice to
correct this misimpression, and even as expert a a set-theorist as Quine
was apparently surprised to discover in the late 1950s how Zermelo's axioms
can be seen as descriptive of a cumulative type-theoretic universe (cf. his
remarks at the San Marino conference in Leonardi & Santambrogio, eds., "On
Quine," Cambridge 1995).  Standard introductory textbooks on set theory
(Suppes, Halmos) did not mention the iterative "conceptual scheme," and
Quine could write that "intuition ... is bankrupt" in the foundations of
the subject ("Set Theory and its Logic," x).
	This changed around 1970 when Shoenfield used the iterative
conception to motivate the ZF axioms (in the set theory chapter of his 1967
"Mathematical Logic" and again in an article in Barwise, ed., "Handbook of
Mathematical Logic") and (probably more widely read by the general
philosophical community) Boolos's 1971 paper in the "Journal of Philosophy"
(repr. in his "Logic, Logic, & Logic").  Textbooks after this introduced
the axioms by reference to the iterative hierarchy, and, increasingly
through the 1970s and 1980s, this was seen by philosophers as the intended
model of set theory.  Pictures of the set-theoretic universe as a conical
structure proliferated, and the ordering of the "ranks" of sets came to be
interpreted metaphysically.  James Van Aken's "Axioms for the Set-Theoretic
Hierarchy" ("Journal of Symbolic Logic" 51 (1986), pp. 992-1004) spoke of
sets as "presupposing" their members, and other philosophers spoke in
almost causal terms of sets being brought into existence by their members
(an idea which could be seen as implicit in Nelson Goodman's much earlier
metaphor of a "generating" relation).  The culmination of this
metaphysicalizing tradition is perhaps David Lewis's elegant monograph
"Parts of Classes" (Blackwell, 1991), in which the membership relation is
described as a mysterious, indefinable, "I know not what" of a relation,
but one we must (on the authority of the mathematicians) accept as
"something" real.
	I was part of this movement.
	When, in the mid-1980s, Anil Gupta told me that Peter Aczel had
developed a fascinating theory of non-well-founded sets (and that Barwise
and Etchemendy were using it in semantic studies) my initial reaction was
that "non-well-founded sets" was a misnomer-- Aczel might have developed an
interesting theory with formal analogies to set theory, but the real sets
were the things that lived in the transfinite cumulative type hierarchy,
and Aczel's theory was no more a theory of THEM than Quine's notorious
systems were.
	This is essentially Anderson's reaction.
	A month or so later, Anil gave me a prepublication copy of chapter
3 ("The Universe of Hypersets") of Barwise and Etchemendy's "The Liar"
(this would probably have been in 1985, but may have been in early 1986:
the book was published in 1986).  To my great surprise, Aczel's theory
looked like... set theory!  (I had been expecting something weird and
wonderful, perhaps based on his earlier work on "Frege structures.")
(Reference: Aczel discusses Frege Structures in his contribution to Barwise
et al., eds., "The Kleene Symposium," North-Holland 1980; this work is
completely independent of the work on non-wf set theory.)  The basic theory
was simply ZFC:  ZFC without, of course, the axiom of foundation, but with
a perspicuous and well-motivated alternative to it.  Classical logic and
most standard set-theoretic methods were available (proof by induction on
membership, to be sure, went with foundation, but a partial substitute was
available).  The intended universe was as clearly defined as the standard,
well-founded, V, and could even be visualized as roughly conical: held up
by a rigid central cone of well-founded sets (the very same well-founded
sets recognized by the iterative conception), but with a fringe of
non-well-founded "tassles" decorating it along the edges...
	What is perhaps most impressive about the iterative conception is
that it gives an almost unique specification of the intended interpretation
of set-theoretic language, one that is definite enough to give a clear
distinction between standard models and nonstandard.  The height of the
intended hierachy is unspecifiable (other than by the unhelpful "as high as
sets go, as high as it is possible to form new sets"), so the standard
models are best taken as initial segments of the full hierachy: cones
starting from the same point at the bottom, but perhaps having a top (to
put ice-cream into).  This, however, is the only way in which the
conception is indefinite: of any two standard models, one is the bottom
part of the other: the cones are all equally wide (all "flare out" at the
same angle).  The expressive power of First Order Logic is, of course,
insufficient to specify intended models with this degree of definiteness,
but suppose we replace the Axiom Schemata, Aussonderung and Replacement, of
ZFC with Second Order Axioms.  Then we don't quite have a categoricity
result-- different standard models don't have to be isomorphic because they
can be of different heights-- but we have an almost-categoricity theorem:
models of Second Order ZFC are all segments of the same big cone, can
differ from each other only in height.  (Analogous to the familiar theorem
that Peano Arithmetic with a Second Order induction axiom replacing the
induction axiom schema of First Order PA is categorical.)
	The sense of objectivity we have about set theory, the sense that
we have more than an empirical mixture ("empiric" is a term of abuse in
medicine: quack) of axioms and that our axioms describe an intended model,
I think, rests in part on this, even for those philosophers who are unaware
of the theorem: the intuitive idea behind the theorem is simple enough that
I think anyone presented with the axioms and an informal description of the
iterative conception will have at least a vague presentiment of it.
	Now, the point I want to emphasize here is that Aczel's
non-well-founded set theory has the same kind of objectivity, is in the
same sense a description of a unique intended model.  ...  Since the proof
of the theorem for ZF with foundation makes use of induction on rank, it
isn't immediately obvious that this should be so.  The trick is to
determine at what rank (how far up the cone) to attach the "decorative
tassles": if this can be stipulated in a systematic way, the induction can
be worked.  Fortunately there is a natural measure of the "complexity" of a
non-well-founded set-- cardinality of its transitive closure-- which can
serve as such a "pseudo-rank."  In slightly more detail, it follows from
Aczel's axiom (or from such alternatives as Scott's) that every
non-well-founded set is "represented" by well-founded sets: models (in the
standard model-theoretic sense: M =3D <D,R>, where  D is a set and R a set o=
f
ordered pairs of members of D) isomorphic to the membership relation
restricted to the transitive closure of the non-well-founded set.  A
non-well-founded set is not in the cone, and so doesn't have a rank, but we
can say it occurs at, and has as pseudo-rank, the lowest rank in which
there is a model representing it.
	(This almost-categoricity result is essentially Theorem 3.10 in
Aczel's Non-Well-Founded Sets (CSLI Monograph series #14, 1988), that ZFC
with his Anti-Foundation Axiom in place of foundation has a "full" class
model that is unique up to isomorphism-- fullness is what second-order
Aussonderung and Replacement are invoked for in my discussion above.)
	So, from the point of view of "objectivity," and being a
description of some genuine intended model, Aczel's set theory seems on a
par with the well-founded ordinary version of ZFC.  Is there any reason not
to grant it equal status as a set theory?
	Well, there is the question of the metaphysical nature of sets and
membership.  Obviously there is a reason to prefer foundation if one thinks
of sets as presupposing, or as quasi-causally generated by, their members.
This metaphysics, however, was not without its problems in the first place!
Sets were sui generis objects, and membership a sui generis relation: the
sort of thing that immediately awakens sceptical worries.  Sets are, one
wants to say, abstract entities, but what does this mean?  (Lewis, op.
cit., complains that there is no clear account of this notion.)  My
generation of philosophers learned about the ontological issues of set
theory in part from Quine's "Logic and the Reification of Universals," but
sets are quite unlike the familiar kinds of universals considered in
philosophical tradition: they are not properties, they are not relations.
Since it seems essential to a set that it have the particular members it
has, sets seem tied to other objects-- to concrete objects, if they have
urelements as members! -- in a way that universals shouldn't be.  Etc etc
etc.
	So, is there an alternative metaphysics of sets?  I find it
tempting to think of them as universals, but this needs a shift in
perspective: the members cease to be what generates a set.  Properties are
universals, what is a set a property of?  ...  As a mathematician
acquaintance of mine once said, "sets are trees."  The straightforward and
na=EFve construal of the slogan "mathematics is about structures" would be
that there is a special category of universals, the structures, or
isomorphism types, and that mathematics is the doctrine of such items.
Now, every set in the in the well-founded hierarchy can be seen as
"standing for" a certain structure, that displayed by the items in its
transitive closure (it is technically neater to say "in the transitive
closure of its unit set") under the membership relation.  Keeping to pure
sets for simplicity and ignoring the fact that an object can be reached by
several distinct downward membership paths from a given set (e.g.: every
maximal path terminates at the null set), we can say this structure is that
of a well-founded tree.  Distinct sets have non-isomorphic tree structures.
Restrict trees a bit to extensional trees (those in which no node has
distinct children which are roots of isomorphic subtrees), and we can even
say the correspondence is bijective: not only does every set stand for a
distinct well-founded extensional tree, but every well-founded extensional
tree is represented by some set.  So, ontologically, set theory is about a
particularly convenient fragment of the universe of universals!
	But if this is the correct metaphysical interpretation of set
theory, there is no reason to restrict one's attention to well-founded
sets.  Well-foundedness is just an ad hoc restriction: relax it and we get
a class of structures represented by the sets in an "anti-founded" set
theoretic hierarchy (not actually Aczel's, but that defined by Scott's
alternative anti-foundation axiom)!
	And some such metaphysical reinterpretation seems to be under way.
Around 1990, it seems to me, the tide of opinion perhaps turned: the high
water of the metaphysicalizing construal of the iterative conception began
to recede.  George Boolos's "Iteration Again" ("Philosophical Topics" 17
(1989); repr. in Logic, Logic, and Logic) pointed out that the idea of
"limitation of size" motivated many of the ZF axioms, including
replacement, which his earlier article held separate from the iterative
conception.  The primacy of size, as opposed to generation, in set theory
comes out in Lewis's "Parts of Classes" as well-- not in the official dogma
of the main text, but in the discussion of "structuralist" construals of
set theory in the Appendix. This is even more apparent in Lewis's slightly
later "Philosophia Mathematica" article (reprinted in his "Essays on
Philosophical Logic"), "Mathematics is Megethology."
	My conclusion, then, is that the choice between ZFC with the axiom
of foundation and ZFC with some such alternative as Aczel's is not a matter
of metaphysical correctness, but a pragmatic one: the set theory to choose
is the one most convenient for the task at hand.
	Which, of course, leaves it open that C.A. Anderson's task is one
for which well-founded set theory is best.  Perhaps it gives the neatest
theory of possible languages, perhaps non-well-founded sets, in this
application, are a needless complication.

Allen Hazen
Lecturer in Philosophy
University of Melbourne