Is there a category of non-well-founded sets? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T06:45:52Z http://mathoverflow.net/feeds/question/14133 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/14133/is-there-a-category-of-non-well-founded-sets Is there a category of non-well-founded sets? Noam Zeilberger 2010-02-04T10:44:51Z 2012-06-21T03:06:19Z <p>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.</p> http://mathoverflow.net/questions/14133/is-there-a-category-of-non-well-founded-sets/14135#14135 Answer by Neel Krishnaswami for Is there a category of non-well-founded sets? Neel Krishnaswami 2010-02-04T11:21:02Z 2010-02-04T11:21:02Z <p>Yes, there is. See Peter Aczel's 1988 notes on models of non-well-founded set theory, <a href="http://standish.stanford.edu/pdf/00000056.pdf" rel="nofollow">here</a>. 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. </p> <p>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 <a href="http://ncatlab.org/nlab/show/pure+set" rel="nofollow">their page on pure sets</a>, and also on their page on <a href="http://ncatlab.org/nlab/show/set+theory#material%5Fset%5Ftheory%5F4" rel="nofollow">material set theory</a>.</p> http://mathoverflow.net/questions/14133/is-there-a-category-of-non-well-founded-sets/14150#14150 Answer by Mike Shulman for Is there a category of non-well-founded sets? Mike Shulman 2010-02-04T14:32:49Z 2010-02-04T14:32:49Z <p>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 <em>equivalent</em> to the subcategory obtained from its submodel of well-founded sets.</p> <p>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 <a href="http://ncatlab.org/nlab/show/pure+set" rel="nofollow">nlab:pure set</a>. 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.</p> http://mathoverflow.net/questions/14133/is-there-a-category-of-non-well-founded-sets/100200#100200 Answer by isomorphismes for Is there a category of non-well-founded sets? isomorphismes 2012-06-21T03:06:19Z 2012-06-21T03:06:19Z <p>According to this doctoral thesis <a href="http://www.andrew.cmu.edu/~awodey/students/hughes.pdf" rel="nofollow">http://www.andrew.cmu.edu/~awodey/students/hughes.pdf</a> by Jesse Hughes (supervised by Steve Awodey), cogebras = coalgebras are the appropriate category to study non-wellfounded sets.</p>