How analogous are categorial and material set theories?
Dear All, I'm very interested in how categorial and material set theories interact, and in particular the advantages of each. It's well-known that categorial viewpoints are good for isolating schematic structural relationships. We can look at sets through this lens, by considering a categorial set theory like ETCS (possibly augmented, e.g. with replacement). A remark one sometimes finds is that once you have defined membership via arrows from terminal objects, you could use ETCS for all the purposes to which ZFC is normally put. My question is the following: (Q) To what extent can you ``do almost the same work'' with a categorial set theory like ETCS vs. a material set theory like ZFC? Just to give a bit more detail concerning what I'm thinking of: Something material set theory is reasonably good at is building models (say to analyse relative consistency), or comparing cardinality. However, there's no denying that for representing abstract relationships the language is somewhat clunky, since the same abstract schematic type can be multiply instantiated by structures with very different set-theoretic properties. So, to what extent can a categorial set theory like ETCS supply the good bits of the fineness of grain associated with material set theories, whilst modding out the `noise'? For example, the following are easily stated in material set theory: 1. \aleph_17 is an accessible cardinal. In material set theory, it's easy to define the aleph function and then state that the 17th position in this function can be reached by iterating powerset and replacement. But I wouldn't even know how to talk about specific sets of different cardinalities categorially. I suppose you could say something in terms of isomorphism between subobjects, and then exponentials, but it's quite unclear to me how the specifcs would go. Is that an easily claim to state (and prove) in ETCS? 2. How would you state that {{}} and {\beth_\omega} are very different objects? Set-theoretically, these look very different (just consider their transitive closures, for instance). But category-theoretically they should look the same---since they are both singletons they are isomorphic. So is this a case where their different set-theoretic propeties are considered just `noise', or where ETCS just wouldn't see a relationship, or where ETCS can in fact see some of these properties (and I'm just missing something)? 3. How would ETCS deal with model theory and cardinality ascriptions? (This links to a question asked earlier on this mailing list concerning syntactic theories in category theory, and whether from the categorial viewpoint we should be taking notice of them at all.) For instance, it's an interesting theorem (for characterising structure) that a first-order theory categorical in one uncountable power is categorical in every uncountable power (Morley's Theorem). But I have no idea how one might formalise this in something like ETCS---I know of Makkai and Reyes textbook (which I am currently reading) on categorial logic (where theories are represented by categories and models by functors), but I don't see how you could get categoricity-in-power claims out of the set up there. Can this be done? Any help and/or discussion would be greatly appreciated! Best Wishes, Neil -- Dr. Neil Barton Postdoctoral Research Fellow Kurt Gödel Research Center for Mathematical Logic University of Vienna Web: https://neilbarton.net/ [For admin and other information see: http://www.mta.ca/~cat-dist/ ]
Dear Neil, Others in this list are much more prominent to answer to your question, but let me provide one viewpoint. Set theoryvis really about the theory of sets. Functions and powersets are there, and complicated structures can evolve. However, a striking thing about sets is that they are "untyped", which can be given a number of meanings. When we move into category theory, the category of sets and functions is the simplest one. Sets come with no structure, so functions do not prserve any such structure. Now, functors over a category become important, the powerset functor over that most simple and unstructured category of sets being a prime example. We need structure, and many real world applications require quite elaborate structure. Functors over more elaborate categories become important, where monoidal closed categories as unnderlying categories bring in fundamental algebraic structures, even for a generalized powerset functors. Let me also speak warmly about the term functor, i.e., the functor that formally constructs terms over a given signature. Such a term functor over the category of sets and functions produces nothing but conventional terms, but a term functor over a monoidal category with more structure can provide terms and expressions with richer structure and attributes. Stochastic and many-valued aspects are good examples, and I often refer to nomenclatures in health care, where additions structure is needed. Expressions e.g. involving diagnoses, functioning and drugs do not run over the same category, and doing all of it in set theory is basically ridiculous. Not sure if these remarks help you at all, so I sincerely hope that more prominent category theorists subscribing to this mailing list will provide more enriched comments. All the best and good luck with your work! Patrik On 2017-11-25 00:36, Neil Barton wrote:
Dear All,
I'm very interested in how categorial and material set theories interact, and in particular the advantages of each.
It's well-known that categorial viewpoints are good for isolating schematic structural relationships. We can look at sets through this lens, by considering a categorial set theory like ETCS (possibly augmented, e.g. with replacement). A remark one sometimes finds is that once you have defined membership via arrows from terminal objects, you could use ETCS for all the purposes to which ZFC is normally put.
My question is the following:
(Q) To what extent can you ``do almost the same work'' with a categorial set theory like ETCS vs. a material set theory like ZFC?
Just to give a bit more detail concerning what I'm thinking of: Something material set theory is reasonably good at is building models (say to analyse relative consistency), or comparing cardinality. However, there's no denying that for representing abstract relationships the language is somewhat clunky, since the same abstract schematic type can be multiply instantiated by structures with very different set-theoretic properties. So, to what extent can a categorial set theory like ETCS supply the good bits of the fineness of grain associated with material set theories, whilst modding out the `noise'?
For example, the following are easily stated in material set theory:
1. \aleph_17 is an accessible cardinal.
In material set theory, it's easy to define the aleph function and then state that the 17th position in this function can be reached by iterating powerset and replacement. But I wouldn't even know how to talk about specific sets of different cardinalities categorially. I suppose you could say something in terms of isomorphism between subobjects, and then exponentials, but it's quite unclear to me how the specifcs would go. Is that an easily claim to state (and prove) in ETCS?
2. How would you state that {{}} and {\beth_\omega} are very different objects? Set-theoretically, these look very different (just consider their transitive closures, for instance). But category-theoretically they should look the same---since they are both singletons they are isomorphic. So is this a case where their different set-theoretic propeties are considered just `noise', or where ETCS just wouldn't see a relationship, or where ETCS can in fact see some of these properties (and I'm just missing something)?
3. How would ETCS deal with model theory and cardinality ascriptions? (This links to a question asked earlier on this mailing list concerning syntactic theories in category theory, and whether from the categorial viewpoint we should be taking notice of them at all.) For instance, it's an interesting theorem (for characterising structure) that a first-order theory categorical in one uncountable power is categorical in every uncountable power (Morley's Theorem). But I have no idea how one might formalise this in something like ETCS---I know of Makkai and Reyes textbook (which I am currently reading) on categorial logic (where theories are represented by categories and models by functors), but I don't see how you could get categoricity-in-power claims out of the set up there. Can this be done?
Any help and/or discussion would be greatly appreciated!
Best Wishes,
Neil
-- Dr. Neil Barton Postdoctoral Research Fellow Kurt G??del Research Center for Mathematical Logic University of Vienna Web: https://neilbarton.net/
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
Dear Neil, This is not an answer to your question, so please ignore it if you're not so interested in these broader issues. My broad question is this. When you look at making set theory more categorical, are you just looking for a categorical way to do essentially the same thing, or are you trying more deeply to expose possible limitations of set theory? One thing shared by ETCS and ZFC is the well-pointedness: that the object is determined by its global elements (morphisms from 1). That can seem obvious if what you're trying to capture is some idea of collection, but in fact it breaks down when the collection has topological structure. The cohesion between points goes beyond what can be explained in terms of the global points themselves, and in point-free topology we see non-trivial spaces with no global points at all. This is not necessarily a pathology of point-free topology but can be related to topological facts such as the existence of principal bundles with no continuous global sections. It also feeds back into "sets" as discrete spaces, with non-well-pointed toposes of sheaves (= local homeomorphisms = fibrewise discrete bundles). In these terms, many questions about cardinalities - such as that of the real line - become artifacts of the way in which you strip off the topology to get a set of global points. Abandoning well-pointedness also allows us to be more relaxed about whether we need to use principles such as choice to assert the existence of elements that we know we can never construct. Regards, Steve Vickers p.s. -
2. How would you state that {{}} and {\beth_\omega} are very different objects?
I would say the answer is that you find an object X where {} and \beth_\omega are very different elements, and treat {{}} and {\beth_\omega} as subobjects of X. In other words, you elucidate their different structures by working over X.
On 24 Nov 2017, at 22:36, bartonna@gmail.com wrote:
Dear All,
I'm very interested in how categorial and material set theories interact, and in particular the advantages of each.
It's well-known that categorial viewpoints are good for isolating schematic structural relationships. We can look at sets through this lens, by considering a categorial set theory like ETCS (possibly augmented, e.g. with replacement). A remark one sometimes finds is that once you have defined membership via arrows from terminal objects, you could use ETCS for all the purposes to which ZFC is normally put.
My question is the following:
(Q) To what extent can you ``do almost the same work'' with a categorial set theory like ETCS vs. a material set theory like ZFC?
Just to give a bit more detail concerning what I'm thinking of: Something material set theory is reasonably good at is building models (say to analyse relative consistency), or comparing cardinality. However, there's no denying that for representing abstract relationships the language is somewhat clunky, since the same abstract schematic type can be multiply instantiated by structures with very different set-theoretic properties. So, to what extent can a categorial set theory like ETCS supply the good bits of the fineness of grain associated with material set theories, whilst modding out the `noise'?
For example, the following are easily stated in material set theory:
1. \aleph_17 is an accessible cardinal.
In material set theory, it's easy to define the aleph function and then state that the 17th position in this function can be reached by iterating powerset and replacement. But I wouldn't even know how to talk about specific sets of different cardinalities categorially. I suppose you could say something in terms of isomorphism between subobjects, and then exponentials, but it's quite unclear to me how the specifcs would go. Is that an easily claim to state (and prove) in ETCS?
2. How would you state that {{}} and {\beth_\omega} are very different objects? Set-theoretically, these look very different (just consider their transitive closures, for instance). But category-theoretically they should look the same---since they are both singletons they are isomorphic. So is this a case where their different set-theoretic propeties are considered just `noise', or where ETCS just wouldn't see a relationship, or where ETCS can in fact see some of these properties (and I'm just missing something)?
3. How would ETCS deal with model theory and cardinality ascriptions? (This links to a question asked earlier on this mailing list concerning syntactic theories in category theory, and whether from the categorial viewpoint we should be taking notice of them at all.) For instance, it's an interesting theorem (for characterising structure) that a first-order theory categorical in one uncountable power is categorical in every uncountable power (Morley's Theorem). But I have no idea how one might formalise this in something like ETCS---I know of Makkai and Reyes textbook (which I am currently reading) on categorial logic (where theories are represented by categories and models by functors), but I don't see how you could get categoricity-in-power claims out of the set up there. Can this be done?
Any help and/or discussion would be greatly appreciated!
Best Wishes,
Neil
-- Dr. Neil Barton Postdoctoral Research Fellow Kurt Gödel Research Center for Mathematical Logic University of Vienna Web: https://neilbarton.net/
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
Dear All, Thanks so much for your kind and patient responses, and apologies for the slow reply (I wanted to check out some of Michael's recommendations before replying). @Patrik: Thanks for the nice examples and applications. I certainly don't want to deny that category theory has applications where material set theory would be inappropriate, but rather to specifically see if there were any applications to which material set theory was more suited (and how this can then be incorporated into the structural setting). However, your examples are useful to see just how different the two perspectives are (I agree that systematising certain subject matters in material set theory would be a fruitless project). @Michael: Thanks very much for the reference. I think I see the proof: One recovers a model of ZFC not by considering the membership relation of ETCS (given by various f: 1--> X), but rather by finding the `membership graph' for the relevant sets in a category satisfying ETCS (with the replacement stack axiom added). I do have a question here though---here we are expected to take the *class* of all well-founded extensional accessible pointed graphs, and note that ZFC holds within this class. Whilst I'm happy that the lemmas showing that the required graphs exist in the category Set are categorial, it seems to me that to isolate all these and talk about the *class* of all of them requires some material-set-theoretic machinery. Is there a *purely categorial* way of talking about this `collection' of subgraphs in Set? Or have I missed something? I suppose this is equivalent to the requirement of asking for a (set) model of ZFC in material set theory. So could one simply state an extra axiom to be added to ETCS+: ``Set contains an well-founded extensional accessible pointed graphs such that...[list the APG ZFC axioms].''. Is this acceptable in a *pure* categorial framework, or do you think that presupposes some material set theory? I suppose there is also the question of how to recover the cumulative hierarchy in this framework---in the paper you sent me this is done with a non-categorial theory of ordinals (possibly given by material set theory). (This relates to a more general question I have concerning categorial foundations: Are there people who claim we should do foundational research *solely* in the language of category theory, or does almost everyone accept that the `external' (possibly material set-theoretic) perspective is also allowed? So, for example, when considering the category of sheaves over a topological space, whilst I could take a purely categorial outlook, nonetheless sometimes I might want to just look at the equivalence class of an open set U relative to a point i in the topological space defined in material set theory. The two perspectives seem to complement rather than contradict each other, but I wonder what the general feeling is concerning the interellation of the two foundational systems.) (This in turn relates to the wider question: How can material and structural set theories inform one another? It *seems* to me (without any deep arguments for the claim) that material set theory is just better suited to certain roles (such as the formulation of large cardinal hypotheses) whilst structural set theory better suited to systematising the algebraic roles we want sets to perform. This is despite the fact that we can simulate one perspective within the other; for example just because you *can* simulate talk of categories with, say, Grothendieck universes, doesn't mean that it's a particularly *natural* interpretation.) @Steve. You ask: When you look at making set theory more categorical, are you just looking for a categorical way to do essentially the same thing, or are you trying more deeply to expose possible limitations of set theory? I don't think I'm clearly aiming at either (though I am interested in these questions). I'm trying to understand more clearly what purposes each foundation is best suited to, and how we can relate the two. I suppose it's a mixture of the two---the present paper I'm currently writing looks to modify material set theory to get something more `structure respecting', but nonetheless facilitating the combinatorial power and conceptual simplicity it offers (allowing us to easily work with notions such as cardinality). I'm trying to get a better picture of the landscape though, and doing this requires understanding the other direction (i.e. how one can mimic material set-theoretic claims in the structural setting). Thanks again! Best Wishes, Neil On 27 November 2017 at 17:49, Steve Vickers <s.j.vickers@cs.bham.ac.uk> wrote:
Dear Neil,
This is not an answer to your question, so please ignore it if you're not so interested in these broader issues.
My broad question is this. When you look at making set theory more categorical, are you just looking for a categorical way to do essentially the same thing, or are you trying more deeply to expose possible limitations of set theory?
One thing shared by ETCS and ZFC is the well-pointedness: that the object is determined by its global elements (morphisms from 1).
That can seem obvious if what you're trying to capture is some idea of collection, but in fact it breaks down when the collection has topological structure. The cohesion between points goes beyond what can be explained in terms of the global points themselves, and in point-free topology we see non-trivial spaces with no global points at all. This is not necessarily a pathology of point-free topology but can be related to topological facts such as the existence of principal bundles with no continuous global sections. It also feeds back into "sets" as discrete spaces, with non-well-pointed toposes of sheaves (= local homeomorphisms = fibrewise discrete bundles).
... [For admin and other information see: http://www.mta.ca/~cat-dist/ ]
participants (3)
-
Neil Barton -
Patrik Eklund -
Steve Vickers