FOM: anti-foundation and the category of sets

[Colin McLarty]

	Steve Simpson 10:04 AM 6/13/00 has offered a theorem:

>THEOREM.  Let V be the standard intended model of ZFC.  Let V* be the
>standard intended model of Aczel's theory 
>
>       ZFC*  =  ZFC - foundation + anti-foundation.
>
>Let C, C* be the category of all sets and mappings in V, V*
>respectively.  Then: C and C* are isomorphic as categories.

Certainly this is true. I want to mention that from a categorical viewpoint
a much simpler fact aleady shows that the category of sets is unaffected by
well-founding or antiwell-founding of membership:

Aczel's theory proves every set is isomorphic to a well founded set.
(Indeed to an ordinal, by the axiom of choice).

	Steve's version is stronger, I'll discuss the technical differences below.

	Categorical set theory only describes sets up to isomorphism, so this weak
version already shows categorical set theory makes no distinction between
well founded and non-well founded sets. 

	Happily, that does not prevent categorical set theory discussing well
orderings, defined in the familiar way: A well ordering on a set S is a
order such that every non-empty subset of S has a unique least member.

	The difference between ZF and categorical set theory here is only that in ZF
each well-ordering is isomorphic to the membership relation on some
set--and indeed on a unique transitively closed set (a von Neumann
ordinal). Categorical set theory has no analogue. On the other hand,
Aczel's theory AFA makes each directed graph isomorphic to the membership
relation on some set. (That is every directed graph is isomorphic to one
where "x has an arrow to y" iff x is a member of y). In ZF only
well-founded graphs have such representations.

	Yet ZF set theorists have no more trouble dealing with graphs than AFA set
theorists do. Realizing each graph as membership on a set is cute, but not
really important.

	Categorical set theory has no more problem dealing with well-founded
relations than ZF has with graphs. In each case, we merely do not represent
them by membership on transitively closed sets.

	As to the relation between Steve's theorem and the weaker version above:
Obviously the category C has a full and faithful inclusion functor into C*.
The weak version says this functor is onto for isomorphism types. Such a
functor is called an "equivalence". When you describe a single category you
rarely define it more specifically than this: up to equivalence. So the
weak theorem shows that the usual methods of category theory, applied to a
single category of sets, will not distinguish C from C*.

	In other words, the weak version already shows that C and C* have all the
same isomorphism classes of sets. Normal working methods in most of
mathematics are isomorphism invariant--I hope this point is well taken and
I can skip the routine arguments. So normal working methods in math go just
the same in C as in C*. Pen Maddy discusses this point in NATURALISM IN
MATHEMATICS p.212. I discussed it with specific attention to Barwise and
Etchemendy's book THE LIAR in an article "Anti-foundation and
self-reference" J. OF PHILOSOPHICAL LOGIC 22, 1993, 19-28.

	Mathematicians (and not just category theorists) often say that two
categories are practically the same when they are equivalent. See for
example Gelfand and Manin METHODS OF HOMOLOGICAL ALGEBRA pp.70-71. The weak
version shows C and C* are practically the same, in this sense. But there
is a catch, as mathematicians often assume global choice without comment
(Gelfand and Manin do) and this makes a difference. 

	By assuming global choice, as Steve does, we can strengthen the theorem to
say the inclusion functor of C into C* has a two sided adjoint, sometimes
called a "quasi-inverse"--a functor taking taking each C* set back to an
isomorphic C set. Such a pair of functors is called an "adjoint
equivalence". In principle this is stronger than mere equivalence. But
since the difference is just the axiom of global choice, people often do
not distinguish them. Gelfand and Manin give a quick proof that every
equivalence is adjoint, where they import global choice without comment in
the phrase "for every X we fix a Y such that...". 

	Adjoint equivalence is still a weaker thing than isomorphism of
categories, as is obvious from the fact that the inclusion of C into C* has
a "quasi-inverse". Using global choice again, plus the fact that each
non-empty set is isomorphic to a proper class of other sets, we get Steve's
proof. C and C* are isomorphic. But now we cannot specify what either
functor actually is.

	Is there any explicitly definable isomorphism between C and C*? This is a
question about the relation of Mostowski trees to accessible strongly
extensional pointed graphs and I have no strong intuition either way.

best, Colin