Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
Thank you Neel and Mike for your answers. I found the nLab notes helpful, as well as <a href="plato.stanford.edu/entries/nonwellfounded-set-theory/… section</a> of the SEP article. Sorry, though, I think I meant to ask a more open-ended question, perhaps unsuitable for mathoverflow. I am interested in references where a category of non-well-founded sets is used as an alternative to the category of sets. –  Noam Zeilberger Feb 4 '10 at 22:41
add comment

3 Answers 3

up vote 14 down vote accepted

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.

share|improve this answer
1  
I was aware of Aczel's notes, but the nLab links were helpful, and this answers the title question. My question was meant a bit more open-endedly, though, especially whether a category of non-well-founded sets has been studied/used systematically, like say in categorical logic. –  Noam Zeilberger Feb 4 '10 at 22:48
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.