* size_question_encore @ 2011-07-05 23:29 Eduardo Dubuc 2011-07-07 1:23 ` RE : categories: size_question_encore Joyal, André ` (2 more replies) 0 siblings, 3 replies; 7+ messages in thread From: Eduardo Dubuc @ 2011-07-05 23:29 UTC (permalink / raw) To: Categories I have now clarified (to myself at least) that there is no canonical small category of finite sets, but a plethora of them. The canonical one is large. With choice, they are all equivalent, without choice not. When you work with an arbitrary base topos (assume grothendieck) "as if it were Sets" this may arise problems as they are beautifully illustrated in Steven Vickers mail. In Joyal-Tierney galois theory (memoirs AMS 309) page 60, they say S_f to be the topos of (cardinal) finite sets, which is an "internal category" since then they take the exponential S^S_f. Now, in between parenthesis you see the word "cardinal", which seems to indicate to which category of finite sets (among all the NON equivalent ones) they are referring to. Now, it is well known the meaning of "cardinal" of a topos ?. I imagine there are precise definitions, but I need a reference. Now, it is often assumed that any small set of generators determine a small set of generators with finite limits. As before, there is no canonical small finite limit closure, thus without choice (you have to choose one limit cone for each finite limit diagram), there is no such a thing as "the" small finite limit closure. Working with an arbitrary base topos, small means internal, thus without choice it is not clear that a set of generators can be enlarged to have a set of generators with finite limits (not even with a terminal object). Unless you add to the topos structure (say in the hypothesis of Giraud's Theorem) the data of canonical finite limits. For example, in Johnstone book (the first, not the elephant) in page 18 Corollary 0.46 when he proves that there exists a site of definition with finite limits, in the proof, it appears (between parenthesis) the word "canonical" with no reference to its meaning. Without that word, the corollary is false, unless you use choice. With that word, the corollary is ambiguous, since there is no explanation for the technical meaning of "canonical". For example, in theorem 0.45 (of which 0.46 is a corollary), the word does not appear. A topos, is not supposed to have canonical (whatever this means) finite limits. e.d. [For admin and other information see: http://www.mta.ca/~cat-dist/ ] ^ permalink raw reply [flat|nested] 7+ messages in thread
* RE : categories: size_question_encore 2011-07-05 23:29 size_question_encore Eduardo Dubuc @ 2011-07-07 1:23 ` Joyal, André [not found] ` <9076_1310082720_4E16469F_9076_34_1_E1QeyJ6-00024q-CT@mlist.mta.ca> 2011-07-11 2:47 ` size_question_encore Michael Shulman 2 siblings, 0 replies; 7+ messages in thread From: Joyal, André @ 2011-07-07 1:23 UTC (permalink / raw) To: Eduardo Dubuc, Categories Dear Eduardo, I would like to join the discussion on the category of finite sets. As you know, the natural number object in a topos can be given many characterisations. For example, it can be defined to be the free monoid on one generator. Etc Clearly the internal category S_f of finite set in the topos Set has many equivalent descriptions. For example, it is a a category with finite coproducts freely generated by one object u. This means that for every category with finite coproducts C and every object c of C, there is a finite coproducts preserving functor F:S_f--->C together with an isomorphism a:F(u)->c, and moreover that the pair (F,a) is unique up to unique isomorphism of pairs. It folows from this description that the category of finite sets is well defined up to an equivalence of categories, with an equivalence which is unique up to unique isomorphism. The situation is more complicated if we work in a general Grothendieck topos instead of the topos of sets. The problem arises from the fact that in a Grothendieck topos, a local equivalence may not be a global equivalence A "global" equivalence between internal categories is defined to be an equivalence in the 2-category of internal categories of this topos. A "local"equivalence is defined to be a functor which is essentially surjective and fully faithful. Every internal category C has a stack completion C--->C' which is locally equivalent to C. A local equivalence induces a global equivalences after stack completion. Let me remark here that the stack completion can be obtained by using a Quillen model structure introduced by Tierney and myself two decades ago. More precisely, the category of small categories (internal to a Grothendieck topos) admits a model structure in which the weak equivalences are the local equivalences, and the cofibrations are the functors monic on objects. An internal category is a stack iff it is globally equivalent to a fibrant objects of this model structure. I propose using stacks for testing the universality of categorical constructions in a topos. For example, in order to say that the category S_f of finite sets in a topos is freely generated by one object u, we may say that for every stack with finite coproducts C and every (globally defined) object c of C, there is a finite coproduct preserving functor F:S_f--->C together with an isomorphism a:F(u)->c, and moreover that the pair (F,a) is unique up to unique isomorphism of pairs. The category of finite sets so defined is not unique, but its stack completion is unique up to global equivalence. Finally, let me observe that the local equivalences between the categories of finite sets are the 1-cells of a 2-category which is 2-filtered. It is thus a 2-ind object of the 2-category of internal categories. I hope my observations can be useful. Best regards, André -------- Message d'origine-------- De: Eduardo Dubuc [mailto:edubuc@dm.uba.ar] Date: mar. 05/07/2011 19:29 À: Categories Objet : categories: size_question_encore I have now clarified (to myself at least) that there is no canonical small category of finite sets, but a plethora of them. The canonical one is large. With choice, they are all equivalent, without choice not. When you work with an arbitrary base topos (assume grothendieck) "as if it were Sets" this may arise problems as they are beautifully illustrated in Steven Vickers mail. In Joyal-Tierney galois theory (memoirs AMS 309) page 60, they say S_f to be the topos of (cardinal) finite sets, which is an "internal category" since then they take the exponential S^S_f. Now, in between parenthesis you see the word "cardinal", which seems to indicate to which category of finite sets (among all the NON equivalent ones) they are referring to. Now, it is well known the meaning of "cardinal" of a topos ?. I imagine there are precise definitions, but I need a reference. Now, it is often assumed that any small set of generators determine a small set of generators with finite limits. As before, there is no canonical small finite limit closure, thus without choice (you have to choose one limit cone for each finite limit diagram), there is no such a thing as "the" small finite limit closure. Working with an arbitrary base topos, small means internal, thus without choice it is not clear that a set of generators can be enlarged to have a set of generators with finite limits (not even with a terminal object). Unless you add to the topos structure (say in the hypothesis of Giraud's Theorem) the data of canonical finite limits. For example, in Johnstone book (the first, not the elephant) in page 18 Corollary 0.46 when he proves that there exists a site of definition with finite limits, in the proof, it appears (between parenthesis) the word "canonical" with no reference to its meaning. Without that word, the corollary is false, unless you use choice. With that word, the corollary is ambiguous, since there is no explanation for the technical meaning of "canonical". For example, in theorem 0.45 (of which 0.46 is a corollary), the word does not appear. A topos, is not supposed to have canonical (whatever this means) finite limits. e.d. [For admin and other information see: http://www.mta.ca/~cat-dist/ ] ^ permalink raw reply [flat|nested] 7+ messages in thread
[parent not found: <9076_1310082720_4E16469F_9076_34_1_E1QeyJ6-00024q-CT@mlist.mta.ca>]
* RE : size_question_encore [not found] ` <9076_1310082720_4E16469F_9076_34_1_E1QeyJ6-00024q-CT@mlist.mta.ca> @ 2011-07-08 13:00 ` Marta Bunge 0 siblings, 0 replies; 7+ messages in thread From: Marta Bunge @ 2011-07-08 13:00 UTC (permalink / raw) To: joyal.andre, edubuc, categories Dear Andre,I welcome your suggestion of involving stacks in order to test universality when the base topos S does not have Choice. I have been exploiting this implicitly but systematically several times since my own construction of the stack completion of a category object C in any Grothendieck topos S (Cahiers, 1979). For instance, I have used it crucially in my paper on Galois groupoids and covering morphisms (Fields, 2004), not only in distinguishing between Galois groupoids from fundamental groupoids, but also for a neat way of (well) defining the fundamental groupoid topos of a Grothendieck topos as the limit of a filtered 1-system of discrete groupoids, obtained from the naturally arising bifiltered 2-system of such by taking stack completions. This relates to the last remark you make in your posting. Concerning S_fin, it does not matter if, in constructing the object classifier, one uses its stack completion instead, since S is a stack (Bunge-Pare, Cahiers, 1979). In my opinion, stacks should be the staple food of category theory without Choice. For instance, an anafunctor (Makkai's terminology) from C to D is precisely a functor from C to the stack completion of D. More recently (Bunge-Hermida, MakkaiFest, 2011), we have carried out the 2-analogue of the 1-dimensional case along the same lines of the 1979 papers, by constructing the 2-stack completion of a 2-gerbe in "exactly the same way". Concerning this, I have a question for you. Is there a model structure on 2-Cat(S) (or 2-Gerbes(S)), for S a Grothedieck topos, whose weak equivalences are the weak 2-equivalence 2-functors, and whose fibrant objects are precisely the (strong) 2-stacks? Although not needed for our work, the question came up naturally after your paper with Myles Tierney. We could find no such construction in the literature. With best regards, Marta > Subject: categories: RE : categories: size_question_encore > Date: Wed, 6 Jul 2011 21:23:36 -0400 > From: joyal.andre@uqam.ca > To: edubuc@dm.uba.ar; categories@mta.ca > > Dear Eduardo, > > I would like to join the discussion on the category of finite sets. > > As you know, the natural number object in a topos can be given many characterisations. > For example, it can be defined to be the free monoid on one generator. Etc > > Clearly the internal category S_f of finite set in the topos Set has many equivalent descriptions. > For example, it is a a category with finite coproducts freely generated by one object u. > This means that for every category with finite coproducts C and every object c of C, > there is a finite coproducts preserving functor F:S_f--->C > together with an isomorphism a:F(u)->c, and moreover that the > pair (F,a) is unique up to unique isomorphism of pairs. > It folows from this description that the category > of finite sets is well defined up to an equivalence of categories, > with an equivalence which is unique up to unique isomorphism. > > The situation is more complicated if we work in a general > Grothendieck topos instead of the topos of sets. > The problem arises from the fact that in a Grothendieck topos, a local equivalence > may not be a global equivalence > A "global" equivalence between internal categories > is defined to be an equivalence in the 2-category of internal categories of this topos. > A "local"equivalence is defined to be a functor > which is essentially surjective and fully faithful. > Every internal category C has a stack completion C--->C' > which is locally equivalent to C. > A local equivalence induces a global equivalences after stack completion. > > Let me remark here that the stack completion can be obtained by using a Quillen model structure > introduced by Tierney and myself two decades ago. > More precisely, the category of small categories (internal to a Grothendieck topos) admits a model structure > in which the weak equivalences are the local equivalences, > and the cofibrations are the functors monic on objects. > An internal category is a stack iff it is globally > equivalent to a fibrant objects of this model structure. > > > I propose using stacks for testing the universality of categorical constructions in a topos. > For example, in order to say that the category S_f of finite > sets in a topos is freely generated by one object u, we may say > that for every stack with finite coproducts C and every (globally defined) > object c of C, there is a finite coproduct preserving functor F:S_f--->C > together with an isomorphism a:F(u)->c, and moreover that the > pair (F,a) is unique up to unique isomorphism of pairs. > The category of finite sets so defined is not unique, > but its stack completion is unique up to global equivalence. > > Finally, let me observe that the local equivalences > between the categories of finite sets are the 1-cells > of a 2-category which is 2-filtered. It is thus a 2-ind object > of the 2-category of internal categories. > > I hope my observations can be useful. > > Best regards, > André > [For admin and other information see: http://www.mta.ca/~cat-dist/ ] ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: size_question_encore 2011-07-05 23:29 size_question_encore Eduardo Dubuc 2011-07-07 1:23 ` RE : categories: size_question_encore Joyal, André [not found] ` <9076_1310082720_4E16469F_9076_34_1_E1QeyJ6-00024q-CT@mlist.mta.ca> @ 2011-07-11 2:47 ` Michael Shulman 2011-07-14 4:10 ` size_question_encore Toby Bartels [not found] ` <CAOvivQyMSgtRMDwvwmV4+UaUfitN-GRaajkh5WxpCipy+U_c+Q@mail.gmail.com> 2 siblings, 2 replies; 7+ messages in thread From: Michael Shulman @ 2011-07-11 2:47 UTC (permalink / raw) To: Categories Even in a category of sets, I don't see why choice is necessary in order to complete a small subcategory under finite limits and obtain a small subcategory. It seems to me that what is needed is rather the axiom of collection, which implies that we can find some *set* of objects containing *at least one* limit for every finite diagram in the original small subcategory; and then we can iterate countably many times to obtain a small category which contains at least one limit for any finite diagram therein. There is of course no canonical result, and the various results obtained will not necessarily be strongly equivalent, but it seems to me that they should all be weakly equivalent. And it also seems to me that the same approach should work internal to any topos. Collection is true internally to any topos (essentially by the internal definition of "indexed family"), so it should still be possible to enlarge a small internal site of definition to one that has finite limits. Unless there is some other subtlety that I'm not seeing. Mike On Tue, Jul 5, 2011 at 4:29 PM, Eduardo Dubuc <edubuc@dm.uba.ar> wrote: > I have now clarified (to myself at least) that there is no canonical > small category of finite sets, but a plethora of them. The canonical one > is large. With choice, they are all equivalent, without choice not. > > When you work with an arbitrary base topos (assume grothendieck) "as if > it were Sets" this may arise problems as they are beautifully > illustrated in Steven Vickers mail. > > In Joyal-Tierney galois theory (memoirs AMS 309) page 60, they say S_f > to be the topos of (cardinal) finite sets, which is an "internal > category" since then they take the exponential S^S_f. Now, in between > parenthesis you see the word "cardinal", which seems to indicate to > which category of finite sets (among all the NON equivalent ones) they > are referring to. > > Now, it is well known the meaning of "cardinal" of a topos ?. > I imagine there are precise definitions, but I need a reference. > > Now, it is often assumed that any small set of generators determine a > small set of generators with finite limits. As before, there is no > canonical small finite limit closure, thus without choice (you have to > choose one limit cone for each finite limit diagram), there is no such a > thing as "the" small finite limit closure. > > Working with an arbitrary base topos, small means internal, thus without > choice it is not clear that a set of generators can be enlarged to have > a set of generators with finite limits (not even with a terminal > object). Unless you add to the topos structure (say in the hypothesis of > Giraud's Theorem) the data of canonical finite limits. > > For example, in Johnstone book (the first, not the elephant) in page 18 > Corollary 0.46 when he proves that there exists a site of definition > with finite limits, in the proof, it appears (between parenthesis) the > word "canonical" with no reference to its meaning. Without that word, > the corollary is false, unless you use choice. With that word, the > corollary is ambiguous, since there is no explanation for the technical > meaning of "canonical". For example, in theorem 0.45 (of which 0.46 is a > corollary), the word does not appear. A topos, is not supposed to have > canonical (whatever this means) finite limits. > > e.d. > [For admin and other information see: http://www.mta.ca/~cat-dist/ ] ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: size_question_encore 2011-07-11 2:47 ` size_question_encore Michael Shulman @ 2011-07-14 4:10 ` Toby Bartels 2011-07-15 6:03 ` size_question_encore Michael Shulman [not found] ` <CAOvivQyMSgtRMDwvwmV4+UaUfitN-GRaajkh5WxpCipy+U_c+Q@mail.gmail.com> 1 sibling, 1 reply; 7+ messages in thread From: Toby Bartels @ 2011-07-14 4:10 UTC (permalink / raw) To: Categories Mike Shulman wrote in part: >Even in a category of sets, I don't see why choice is necessary in >order to complete a small subcategory under finite limits and obtain a >small subcategory. It seems to me that what is needed is rather the >axiom of collection, which implies that we can find some *set* of >objects containing *at least one* limit for every finite diagram in >the original small subcategory; and then we can iterate countably many >times to obtain a small category which contains at least one limit for >any finite diagram therein. The axiom of collection guarantees only *some* appropriate set of objects, so you need to choose one. To iterate this countably many times, you might need dependent choice. Unless I'm not understanding what you're doing. --Toby [For admin and other information see: http://www.mta.ca/~cat-dist/ ] ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: size_question_encore 2011-07-14 4:10 ` size_question_encore Toby Bartels @ 2011-07-15 6:03 ` Michael Shulman 0 siblings, 0 replies; 7+ messages in thread From: Michael Shulman @ 2011-07-15 6:03 UTC (permalink / raw) To: Toby Bartels; +Cc: Categories On Wed, Jul 13, 2011 at 9:10 PM, Toby Bartels <categories@tobybartels.name> wrote: >>the axiom of collection, which implies that we can find some *set* of >>objects containing *at least one* limit for every finite diagram in >>the original small subcategory; and then we can iterate countably many >>times to obtain a small category which contains at least one limit for >>any finite diagram therein. > > The axiom of collection guarantees only *some* appropriate set of objects, > so you need to choose one. To iterate this countably many times, > you might need dependent choice. That's a good point. However, I think we can get around it as follows. We can make finitely many choices without any axiom of choice. Thus, for any natural number n, by applying collection n times, we can find *some* n^th iterate of the "construction". (Formally, we prove this by induction on n.) Applying the axiom of collection again over the natural numbers, we obtain a set which contains at least one n^th iterate of the "construction" for every natural number n. Taking the union of this set, we should obtain a set of objects whose corresponding full subcategory contains at least one limit of every finite diagram therein. Mike [For admin and other information see: http://www.mta.ca/~cat-dist/ ] ^ permalink raw reply [flat|nested] 7+ messages in thread
[parent not found: <CAOvivQyMSgtRMDwvwmV4+UaUfitN-GRaajkh5WxpCipy+U_c+Q@mail.gmail.com>]
* Re: size_question_encore [not found] ` <CAOvivQyMSgtRMDwvwmV4+UaUfitN-GRaajkh5WxpCipy+U_c+Q@mail.gmail.com> @ 2011-07-15 16:51 ` Toby Bartels 0 siblings, 0 replies; 7+ messages in thread From: Toby Bartels @ 2011-07-15 16:51 UTC (permalink / raw) To: Categories Michael Shulman wrote in part: >We can make finitely many choices without any axiom of >choice. Thus, for any natural number n, by applying collection n >times, we can find *some* n^th iterate of the "construction". >(Formally, we prove this by induction on n.) Applying the axiom of >collection again over the natural numbers, we obtain a set which >contains at least one n^th iterate of the "construction" for every >natural number n. Taking the union of this set, we should obtain a >set of objects whose corresponding full subcategory contains at least >one limit of every finite diagram therein. OK, I buy that. The part where we take the union is the step that doesn't generalise to arbitrary applications of DC. --Toby [For admin and other information see: http://www.mta.ca/~cat-dist/ ] ^ permalink raw reply [flat|nested] 7+ messages in thread
end of thread, other threads:[~2011-07-15 16:51 UTC | newest] Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2011-07-05 23:29 size_question_encore Eduardo Dubuc 2011-07-07 1:23 ` RE : categories: size_question_encore Joyal, André [not found] ` <9076_1310082720_4E16469F_9076_34_1_E1QeyJ6-00024q-CT@mlist.mta.ca> 2011-07-08 13:00 ` RE : size_question_encore Marta Bunge 2011-07-11 2:47 ` size_question_encore Michael Shulman 2011-07-14 4:10 ` size_question_encore Toby Bartels 2011-07-15 6:03 ` size_question_encore Michael Shulman [not found] ` <CAOvivQyMSgtRMDwvwmV4+UaUfitN-GRaajkh5WxpCipy+U_c+Q@mail.gmail.com> 2011-07-15 16:51 ` size_question_encore Toby Bartels
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).