Splitting epis by wishful thinking
On Mathoverflow there is a discussion (see http://mathoverflow.net/questions/117921/relative-consistency-of-etcs-over-t...) which got me thinking. Is there a construction which "freely" splits all epis in a category C? Something like: we add sections to every epi and wish we are done? The question is somewhat lose, but I think it is clear nontheless. With kind regards, Andrej [For admin and other information see: http://www.mta.ca/~cat-dist/ ]
Hi Andrej, This isn't exactly what you want, but it's along the right lines. Given a small category with cokernel pairs, one can construct another category with cokernel pairs in which all epis have been "freely" split. By this, I mean that a chosen section has been freely added to every epi in the category, even the ones that already had a section; thus the construction is not idempotent. Basically one uses the small object argument. Consider the category K of small categories with cokernel pairs, and functors preserving such. Let C be the free category with cokernel pairs containing an epi e: it can be obtained by first forming the free category with cokernel pairs on an arrow f, and then coinverting the codiagonal of f. Let D be the free category with cokernel pairs containing a section-retraction pair (i,p). There is an obvious map C --> D in K which sends e to p. Now some E in K satisfies the axiom of choice if and only if it is projective (has the weak right lifting property) with respect to this map C --> D. K is locally finitely presentable, and so the map C --> D generates via the small object argument a weak factorisation system (L,R) on it. By the above argument, the fibrant objects for (L,R) are those small categories with cokernel pairs satisfying the axiom of choice. If one uses the algebraic version of the small object argument, the fibrant replacement for this w.f.s. is a monad, S, say. The action of this monad on objects freely adjoins sections for all epis; its algebras are precisely the small categories with cokernel pairs with a chosen section for each epi. One can ask what happens if one drops the assumption of cokernel pairs. Consider the category Cat_ac, whose objects are small categories in which every epi comes equipped with a chosen section. There is an obvious forgetful functor Cat_ac ---> Cat, and a more precise formulation of your original question would be to ask if this functor has a left adjoint. This is unclear to me; at the moment I feel like it probably doesn't. What does seem clear is that, if it does have a left adjoint, then it can't possibly be monadic, so whatever construction one gives won't be entirely honest or straightforward. Richard On 3 January 2013 23:36, Andrej Bauer <andrej.bauer@andrej.com> wrote:
On Mathoverflow there is a discussion (see
http://mathoverflow.net/questions/117921/relative-consistency-of-etcs-over-t... ) which got me thinking.
Is there a construction which "freely" splits all epis in a category C? Something like: we add sections to every epi and wish we are done?
The question is somewhat lose, but I think it is clear nontheless.
With kind regards,
Andrej
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
Dear Andrej, The following formulation of your question has negative answers: Let Cat be the category of small categories and functors between them, and SCat be its full sub-category of small categories in which all epis split. Let U : SCat -> Cat be the full inclusion. U does not have a left adjoint, nor a right adjoint. Proof: Let C be the following category: It has 3 objects: 0 - an initial object A and B. Apart from the identities and the initial maps, C has the following 3 morphisms: a parallel pair f, g : A -> B an endomorphism h : B -> B The non-trivial compositions are given by: x o h = x, for x = f, g, and h. Note that C is in SCat, as it has no trivial epimorphisms: the non-trivial arrow into A equalises f and g, which are different, and the non-trivial arrows into B equalise h and id. Let F : C -> C be the endofunctor that swaps f with g. If U had a left adjoint, then SCat was a full reflective subcategory of Cat, it was complete. Consider the equaliser of F, Id : C->C. Whatever it is in SCat, this coequaliser cannot be preserved by U, as the equaliser in Cat is given by dropping f and g. This resulting subcategory has an epi, the initial arrow into A, that doesn't split. Similarly, if U had a right adjoint, then SCat was cocomplete. Then the coequaliser of F, Id : C->C in Cat would be C with g dropped (=identified with f). But then the initial map into A becomes epi, without a section. Thus this colimit is not in SCat, and U doesn't preserve it. The same construction actually lies within the category Cat_ac that Richard described (with specified sections), as C has no non-trivial sections. Thus the same proof applies to his formulation, and his forgetful functor also isn't a right nor a left adjoint. Ohad. On 4 January 2013 04:04, Richard Garner <richard.garner@mq.edu.au> wrote:
Hi Andrej,
This isn't exactly what you want, but it's along the right lines. Given a small category with cokernel pairs, one can construct another category with cokernel pairs in which all epis have been "freely" split. By this, I mean that a chosen section has been freely added to every epi in the category, even the ones that already had a section; thus the construction is not idempotent. Basically one uses the small object argument.
Consider the category K of small categories with cokernel pairs, and functors preserving such. Let C be the free category with cokernel pairs containing an epi e: it can be obtained by first forming the free category with cokernel pairs on an arrow f, and then coinverting the codiagonal of f. Let D be the free category with cokernel pairs containing a section-retraction pair (i,p). There is an obvious map C --> D in K which sends e to p. Now some E in K satisfies the axiom of choice if and only if it is projective (has the weak right lifting property) with respect to this map C --> D.
K is locally finitely presentable, and so the map C --> D generates via the small object argument a weak factorisation system (L,R) on it. By the above argument, the fibrant objects for (L,R) are those small categories with cokernel pairs satisfying the axiom of choice. If one uses the algebraic version of the small object argument, the fibrant replacement for this w.f.s. is a monad, S, say. The action of this monad on objects freely adjoins sections for all epis; its algebras are precisely the small categories with cokernel pairs with a chosen section for each epi.
One can ask what happens if one drops the assumption of cokernel pairs. Consider the category Cat_ac, whose objects are small categories in which every epi comes equipped with a chosen section. There is an obvious forgetful functor Cat_ac ---> Cat, and a more precise formulation of your original question would be to ask if this functor has a left adjoint. This is unclear to me; at the moment I feel like it probably doesn't. What does seem clear is that, if it does have a left adjoint, then it can't possibly be monadic, so whatever construction one gives won't be entirely honest or straightforward.
Richard
On 3 January 2013 23:36, Andrej Bauer <andrej.bauer@andrej.com> wrote:
On Mathoverflow there is a discussion (see
http://mathoverflow.net/questions/117921/relative-consistency-of-etcs-over-t... ) which got me thinking.
Is there a construction which "freely" splits all epis in a category C? Something like: we add sections to every epi and wish we are done?
The question is somewhat lose, but I think it is clear nontheless.
With kind regards,
Andrej
-- The University of Edinburgh is a charitable body, registered in Scotland, with registration number SC005336. [For admin and other information see: http://www.mta.ca/~cat-dist/ ]
Of course, the case I'm really interested in is where we start with a well-pointed topos with nno and recover at least a boolean topos with nno satisfying *IAC*.
From this we can use stack semantics to get a model of ETCS.
Best, David Roberts On 5 January 2013 01:52, Ohad Kammar <ohad.kammar@ed.ac.uk> wrote:
Dear Andrej,
The following formulation of your question has negative answers:
Let Cat be the category of small categories and functors between them, and SCat be its full sub-category of small categories in which all epis split. Let U : SCat -> Cat be the full inclusion.
U does not have a left adjoint, nor a right adjoint.
Proof:
Let C be the following category: It has 3 objects: 0 - an initial object A and B.
Apart from the identities and the initial maps, C has the following 3 morphisms: a parallel pair f, g : A -> B an endomorphism h : B -> B
The non-trivial compositions are given by:
x o h = x, for x = f, g, and h.
Note that C is in SCat, as it has no trivial epimorphisms: the non-trivial arrow into A equalises f and g, which are different, and the non-trivial arrows into B equalise h and id.
Let F : C -> C be the endofunctor that swaps f with g.
If U had a left adjoint, then SCat was a full reflective subcategory of Cat, it was complete. Consider the equaliser of F, Id : C->C. Whatever it is in SCat, this coequaliser cannot be preserved by U, as the equaliser in Cat is given by dropping f and g. This resulting subcategory has an epi, the initial arrow into A, that doesn't split.
Similarly, if U had a right adjoint, then SCat was cocomplete. Then the coequaliser of F, Id : C->C in Cat would be C with g dropped (=identified with f). But then the initial map into A becomes epi, without a section. Thus this colimit is not in SCat, and U doesn't preserve it.
The same construction actually lies within the category Cat_ac that Richard described (with specified sections), as C has no non-trivial sections. Thus the same proof applies to his formulation, and his forgetful functor also isn't a right nor a left adjoint.
Ohad.
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
Preliminary thoughts: 1. Certainly for any category C and any set of morphisms in it you can freely freely adjoin splittings for all those morphisms. In particular you might start with the set of all epis in C. (They're going to become epi anyway.) This construction is just universal algebra, but the universal algebra dooen't answer questions like (a) Is the functor from C faithful? (b) Does the new category inherit nice properties of C? (c) Do all epis split in the new category? 2. Suppose you are willing to restrict to categories with finite colimits. Then epis can be characterized equationally, so there is a cartesian theory of finite colimit categories in which every epi has a chosen splitting. Then the forgetful functor from such categories to finite colimit categories has a left adjoint. You can extend this to deal with categories with additional structure on top of the finite colimits, so long as the additional structure can be expressed as cartesian theory. Happy New Year, Steve. On 3 Jan 2013, at 12:36, Andrej Bauer <andrej.bauer@andrej.com> wrote:
On Mathoverflow there is a discussion (see http://mathoverflow.net/questions/117921/relative-consistency-of-etcs-over-t...) which got me thinking.
Is there a construction which "freely" splits all epis in a category C? Something like: we add sections to every epi and wish we are done?
The question is somewhat lose, but I think it is clear nontheless.
With kind regards,
Andrej
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
Dear all,
1. Certainly for any category C and any set of morphisms in it you can freely freely adjoin splittings for all those morphisms. In particular you might start with the set of all epis in C. (They're going to become epi anyway.)
This construction is just universal algebra, but the universal algebra dooen't answer questions like (a) Is the functor from C faithful? (b) Does the new category inherit nice properties of C? (c) Do all epis split in the new category?
For the case where it works (that is, where we really start with a *set* rather than a proper class of epis), a) is answered in the positive in my APCS paper "Free adjunction of morphisms", see http://www8.informatik.uni-erlangen.de/~schroeder/papers/freeadj.pdf The idea is basically to apply rewriting theory: Check that the rewrite relation that reduces, for each (non-isomorphic) epi e with newly added section s and each suitable morphism f, the term (fe)s to f (where (fe) and s are meant to be letters in a "category of words") is locally confluent. Since this implies a normal form result, I expect it would also help answer c). When we want to add sections for a proper class of epis in a large category, then we run into problems if we insist that the resulting category remain locally small: clearly, the "category of words" arising from adding a proper class of new sections will typically fail to be locally small, and I expect the above confluence result, which says that the result of freely adding sections has as many morphisms as there are irreducible words under the mentioned rewrite relation, can be applied easily to produce a counterexample (not just to faithfulness, but to existence of the free extension). One maybe interesting question is whether one gets "spurious" free extensions where the free extension by sections for a class of epis exists only because local smallness forces some morphisms to be identified for non-algebraic reasons. (A related example has I believe recently been found by Paul Levy and Nathan Bowler, who proved that there exist spurious tensors of monads in a similar sense.) Happy New Year, Lutz
2. Suppose you are willing to restrict to categories with finite colimits. Then epis can be characterized equationally, so there is a cartesian theory of finite colimit categories in which every epi has a chosen splitting. Then the forgetful functor from such categories to finite colimit categories has a left adjoint. You can extend this to deal with categories with additional structure on top of the finite colimits, so long as the additional structure can be expressed as cartesian theory.
Happy New Year,
Steve.
On 3 Jan 2013, at 12:36, Andrej Bauer <andrej.bauer@andrej.com> wrote:
On Mathoverflow there is a discussion (see http://mathoverflow.net/questions/117921/relative-consistency-of-etcs-over-t...)
which got me thinking.
Is there a construction which "freely" splits all epis in a category C? Something like: we add sections to every epi and wish we are done?
The question is somewhat lose, but I think it is clear nontheless.
With kind regards,
Andrej
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
-- -------------------------------------- Prof. Dr. Lutz Schr?der Friedrich-Alexander-Universit?t Erlangen-N?rnberg Department of Computer Science Chair 8 -- Theoretical Computer Science Martensstr. 3 91058 Erlangen +49-9131-85-64059 lutz.schroeder@informatik.uni-erlangen.de lutz.schroeder@cs.fau.de http://www8.cs.fau.de/~schroeder/ -------------------------------------- [For admin and other information see: http://www.mta.ca/~cat-dist/ ]
On Thu, 03 Jan 2013 08:55:07 PM EST Andrej Bauer <andrej.bauer@andrej.com> asked
Is there a construction which "freely" splits all epis in a category ... ?
To the responses already received I thought it perhaps worth adding the idea of freely (or generically) splitting everything, after a fashion I first heard described by Bill Lawvere -- that is, freely adjoining, for each map e (epi or not), a map f with efe = e (and perhaps, if you like, fef = f) . Note that, with e epi, efe = e will entail ef = id, i.e., f will be a section for e. Likewise, for e mono, efe = e will entail fe = id, i.e., f will be a retraction for e. (In these two cases, of course, it will follow that fef = f. In general, tho', ... .) One should, of course, ask oneself whether one should really be wanting sections for quite all epimorphisms -- in the category [R] of unital rings R, for example, should one really ever want the trivializing homomorphisms !: R --> 1 to the terminal ring to split, anywhere? Cheers, -- Fred [For admin and other information see: http://www.mta.ca/~cat-dist/ ]
On 03/01/13 09:36, Andrej Bauer wrote:
On Mathoverflow there is a discussion (see http://mathoverflow.net/questions/117921/relative-consistency-of-etcs-over-t...) which got me thinking.
Is there a construction which "freely" splits all epis in a category C? Something like: we add sections to every epi and wish we are done?
The question is somewhat lose, but I think it is clear nontheless.
With kind regards,
Andrej
I found pertinent (or related) to this problem to recall the following beautiful construction construction due to Joyal. A key step in Joyal approach to (Godel type) completeness theorem consists in freely adding constants (Henkin's proof). Given a regular category CC, for any epi B --->> 1, we freely add a constant 1 --->> B (in the 2-category of regular categories and regular functors). This is easily done by talking the slice category CC/B. We have CC ---> CC/B. Product of epis is epi so this yields a filtered system of regular categories. Let CC' be its colimit. We have CC ---> CC'. Doing this denumerable times, we get CC ---> sCC, where sCC is regular, every epi B ---> 1 in sCC splits and sCC has the corresponding universal property. e.d. [For admin and other information see: http://www.mta.ca/~cat-dist/ ]
participants (8)
-
Andrej Bauer -
David Roberts -
Eduardo J. Dubuc -
Fred E.J. Linton -
Lutz Schröder -
Ohad Kammar -
Richard Garner -
Steve Vickers