Is there a category of non-well-founded sets? - MathOverflow

Is there a category of non-well-founded sets?

2010-02-04T10:44:51Z

Is there a category (in the category theory sense) of non-well-founded sets (something analogous to Set, the category of sets), and has it been (well-)studied? Any references are appreciated.

Answer by Neel Krishnaswami for Is there a category of non-well-founded sets?

2010-02-04T11:21:02Z

Yes, there is. See Peter Aczel's 1988 notes on models of non-well-founded set theory, here. The basic idea is that you can model sets as graphs (ie, as a collection of element sets together with a binary relation intuitively suggesting membership), and then the foundation axiom corresponds exactly to the assertion that the membership relation is well-founded. Allowing non-well-founded sets corresponds to allowing arbitrary relations.

These graphs are perfectly ordinary mathematical objects, and so we can collect them into a category exactly the way we do with "normal" sets. The nLab has some notes on this on their page on pure sets, and also on their page on material set theory.

Answer by Mike Shulman for Is there a category of non-well-founded sets?

2010-02-04T14:32:49Z

Starting from any model of a membership-based set theory, be it well-founded or ill-founded, you can construct a category of sets and functions. The basic properties of this category (e.g. it is a well-pointed topos) don't depend on whether the model you started from was well- or ill-founded. In fact, in the presence of the axiom of choice, every ill-founded set is still well-orderable, hence bijective to a well-founded set (a von Neumman ordinal) -- thus the category of sets obtained from a model of ill-founded set theory + choice is equivalent to the subcategory obtained from its submodel of well-founded sets.

You can then ask whether you can reconstruct a model of membership-based set theory from its category of sets; here is where the graphs come in (to model hereditary membership relations), as at nlab:pure set. You can choose to use well-founded graphs or ill-founded ones. If the one you choose matches the type of set theory you started from, then (as long as your set theory is strong enough otherwise) you'll reconstruct the same model. If you choose well-founded graphs starting from an ill-founded set theory, then you'll reconstruct the submodel of well-founded sets, reproducing the proof of relative consistency of the axiom of foundation. And if you choose ill-founded graphs starting from a well-founded set theory, you'll reproduce Aczel's original proof of the relative consistency of the anti-foundation axiom.

Answer by isomorphismes for Is there a category of non-well-founded sets?

2012-06-21T03:06:19Z

According to this doctoral thesis http://www.andrew.cmu.edu/~awodey/students/hughes.pdf by Jesse Hughes (supervised by Steve Awodey), cogebras = coalgebras are the appropriate category to study non-wellfounded sets.