Not signed in (Sign In)

Not signed in

Want to take part in these discussions? Sign in if you have an account, or apply for one below

  • Sign in using OpenID

Site Tag Cloud

2-category 2-category-theory abelian-categories adjoint algebra algebraic algebraic-geometry algebraic-topology analysis analytic-geometry arithmetic arithmetic-geometry book bundles calculus categorical categories category category-theory chern-weil-theory cohesion cohesive-homotopy-type-theory cohomology colimits combinatorics comma complex complex-geometry computable-mathematics computer-science constructive cosmology deformation-theory descent diagrams differential differential-cohomology differential-equations differential-geometry digraphs duality elliptic-cohomology enriched fibration finite foundation foundations functional-analysis functor gauge-theory gebra geometric-quantization geometry graph graphs gravity grothendieck group group-theory harmonic-analysis higher higher-algebra higher-category-theory higher-differential-geometry higher-geometry higher-lie-theory higher-topos-theory homological homological-algebra homotopy homotopy-theory homotopy-type-theory index-theory integration integration-theory k-theory lie-theory limits linear linear-algebra locale localization logic mathematics measure-theory modal modal-logic model model-category-theory monad monads monoidal monoidal-category-theory morphism motives motivic-cohomology nlab noncommutative noncommutative-geometry number-theory of operads operator operator-algebra order-theory pages pasting philosophy physics pro-object probability probability-theory quantization quantum quantum-field quantum-field-theory quantum-mechanics quantum-physics quantum-theory question representation representation-theory riemannian-geometry scheme schemes set set-theory sheaf simplicial space spin-geometry stable-homotopy-theory stack string string-theory superalgebra supergeometry svg symplectic-geometry synthetic-differential-geometry terminology theory topology topos topos-theory tqft type type-theory universal variational-calculus

Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.

Welcome to nForum
If you want to take part in these discussions either sign in now (if you have an account), apply for one now (if you don't).
    • CommentRowNumber1.
    • CommentAuthorPieter
    • CommentTimeFeb 2nd 2019

    As I mentioned in my “new member” post (I don’t know how to do fancy references to other posts yet), I am looking for a notion of “remainder” in category theory.

    I’m describing a “system behavior” and a map of that behavior to the behavior of a “component” of the system. The question at hand is: what is the best description I can find of the behavior of the other components?

    Because a composition of components (and synchronization between) them, in my category leads to a “jointly monic family” of maps from the system behavior to the behavior of the components, I could therefore say that I’m looking for the “smallest” component that allows me to form a “jointly monic pair” with the map into the “known” component.

    I got to this definition at first:

    • given a map f:XYf : X \rightarrow Y, a “remainder” of ff is any object ZZ for which there exists a map g:XZg : X \rightarrow Z such that (f,g)(f,g) is jointly monic, and in addition it holds that for any other g:XZg' : X \rightarrow Z' such that (f,g)(f,g') is jointly monic, there is a unique k:ZZk : Z \rightarrow Z' such that kg=gkg = g'.

    I though it was a rather natural notion, but have not found references to it yet.

    Mike Shulman and David Roberts already responded with two questions:

    1) can I give an example of whether such a remainder can exist at all? He didn’t think it would exist for Set.

    2) Isn’t it a trivial notion? If you take Y=XY = X, the identity might do the job.

    As to 1)… I’m going to think about it. I think I have an example in the category of prefix orders, on which I just posted a page, but I still need to check it. (Apologies for asking the question before doing my homework… but sometimes you can spend hours figuring out what other people already know ;-)

    As to 2)… shoot… that is a suggestion I overlooked. In my own examples there are often “smaller” candidates for YY than XX, but they do not seem to come out this way. Intuitively, in Set, the map gg should not be injective at points where ff is already injective. But the definition still allows that apparently. Back to the drawing board… Any suggestions?

    • CommentRowNumber2.
    • CommentAuthorMike Shulman
    • CommentTimeFeb 2nd 2019

    David is right, btw, about any category and any ff at all: your definition says it is an initial object in some full subcategory of X/𝒞X/\mathcal{C}, so as long as that subcategory contains the initial object of X/𝒞X/\mathcal{C} (namely Z=XZ=X and g=id Xg=id_X) — and it does — that is also the initial object in the subcategory. I think I was originally trying to solve the problem you actually had in mind of making a map that’s “only injective where ff is not”, and that’s what I thought would not exist. Perhaps what you want is a terminal object of the same category? But look at SetSet first; suppose f:XYf:X\to Y is the first projection 2×222\times 2 \to 2, where 2={0,1}2=\{0,1\}. What do you want gg to be? Since f(0,1)=f(0,0)f(0,1)=f(0,0) and f(1,1)=f(1,0)f(1,1)=f(1,0), you need gg to separate those pairs. But if you want gg to be noninjective “at points where ff is already injective” then presumably you want something like g(0,1)=g(1,1)g(0,1) = g(1,1) or g(0,1)=g(1,0)g(0,1) = g(1,0) — but you can’t have both of those, otherwise g(1,0)=g(1,1)g(1,0)=g(1,1) which isn’nt allowed, and there’s no universal way to pick one but not the other.

    • CommentRowNumber3.
    • CommentAuthorPieter
    • CommentTimeFeb 2nd 2019
    • (edited Feb 2nd 2019)

    Thanks Mike, good example. (I’m not a full time category theorist, but after some parsing I can get the first part of your post as well :-)

    Indeed, let’s look at Set first. If f:XYf: X \rightarrow Y is the first projection of 2×222 \times 2 \rightarrow 2, then (intuitively) I would like gg to become the second projection. That would at least be my idea of division within Set… Whenever ff is not an actual projection, it will be a bit tricky to tell what gg should be, but indeed for projections it should work out in any/most categories.

    So, what are we doing really then… I think gg should split the points that ff equates, but it can identify points that ff distinguishes. Furthermore, gg should identify “as many points as possible”, and that is where the difficulty starts.

    • CommentRowNumber4.
    • CommentAuthorPieter
    • CommentTimeFeb 2nd 2019

    Okay, then let’s look at whether terminal objects work…

    Second try: given f:XYf : X \rightarrow Y, and object ZZ is a remainder of ff if there exists a map g:XZg : X \rightarrow Z such that (f,g)(f,g) is jointly monic, and for any g:XZg' : X \rightarrow Z' with (f,g)(f,g') jointly monic there is a map h:ZZh : Z' \rightarrow Z such that hg=gh g' = g.

    Notice that I have reversed the direction of hh but also dropped the uniqueness requirement, because it will give trouble whenever gg' is non-surjective.

    This seems to work for the simple 2×22 \times 2 example. It is a standard result that the two projections form a jointly monic pair. Furthermore, any candidate ZZ' must at least contain two points in order to distinguish (0,0)(0,0) from (0,1)(0,1), otherwise (f,g)(f,g') cannot be jointly monic. Furthermore, the image of gg' will contain at most 44 points, and the remaining points an be mapped arbitrarily to 22. Simply enumerating the possibilities for images that contain 22,33 or 44 points quickly leads to the conclusion that indeed the second projection is a witness to show that 2×22 \times 2 divided by 22 gives 22.

    I’ve tried a simple example in my category of prefix orders as well, and it also seems to work there.

    Next, I guess I should prove that in general when ff is the first projection of a binary product, gg is the second projection. Or try a few more examples. And after that, we still have the question whether/when ZZ is unique…

    • CommentRowNumber5.
    • CommentAuthorPieter
    • CommentTimeFeb 2nd 2019

    And pondering the diagram a bit… what would the consequence be if we weaken the definition to:

    Third try: given f:XYf : X \rightarrow Y, and object ZZ is a remainder of ff if for every g:XZg : X \rightarrow Z' with (f,g)(f,g) jointly monic, there is an h:ZZh : Z' \rightarrow Z such that (f,hg)(f,hg) is jointly monic.

    Whenever the second try holds, the third try holds as well. But of course the third try has fewer properties in general. If the third try still gives a unique choice for ZZ however, it means that the definition becomes possible in more categories.

    • CommentRowNumber6.
    • CommentAuthorMike Shulman
    • CommentTimeFeb 2nd 2019

    My point about 2×22\times 2 is that given only a 4-element set and one of its projections to a 2-element set, there is no canonical, hence no universal, way to identify another map as “the second projection”. Maybe it would be clearer to consider the function f:{,,,}{0,1}f: \{\heartsuit,\spadesuit,\diamondsuit,\clubsuit\}\to \{0,1\} defined by f()=f()=0f(\heartsuit)=f(\clubsuit)=0 and f()=f()=1f(\spadesuit)=f(\diamondsuit)=1. What would you want gg to be in this case?

    • CommentRowNumber7.
    • CommentAuthorPieter
    • CommentTimeFeb 2nd 2019

    Theorem (using either definition version 2 or 3): If in our category of choice all pushouts exist and all epi’s have sections (the axiom of choice, I believe), then the natural projections of a binary product are each-others remainder.

    Proof: Let f:X×YXf : X \times Y \rightarrow X and g:X×YYg : X \times Y \rightarrow Y be natural projections of X×YX \times Y. It is a standard result that (f,g)(f,g) is jointly monic. Furthermore, let g:X×YZg' : X \times Y \rightarrow Z be such that (f,g)(f,g') is jointly monic. Then we can create the pushout gg' and gg, given by maps p:YPp : Y \rightarrow P and q:ZPq : Z \rightarrow P. It is a standard result that pp and qq are epimorphisms. Let p:PYp' : P \rightarrow Y be the section of pp, then we define h=pqh = p' q and find hg=pqg=ppg=gh g' = p' q g' = p' p g = g. So we may conclude that YY is a remainder of ff, witnessed by gg.

    If I didn’t make any mistakes, in Set the remainders (if they are indeed unique) therefore behave as I would like them to for the time being.

    • CommentRowNumber8.
    • CommentAuthorMike Shulman
    • CommentTimeFeb 2nd 2019

    Here’s an analogy that might be helpful: given a subspace of a vector space UVU\subseteq V, there is no canonical way to single out a complementary subspace WW such that UW=VU\oplus W = V. What you can do is consider the quotient space V/UV/U, which plays a similar role. Or if VV is equipped with an inner product, you can define the orthogonal subspace U U^\perp.

    • CommentRowNumber9.
    • CommentAuthorPieter
    • CommentTimeFeb 2nd 2019

    @Mike. Yes, I see. But I’m not directly concerned with the choice of gg exactly. I’m concerned with finding the object YY

    • CommentRowNumber10.
    • CommentAuthorMike Shulman
    • CommentTimeFeb 2nd 2019

    From a category-theoretic point of view, you shouldn’t expect to determine an object without the morphisms that structure it.

    • CommentRowNumber11.
    • CommentAuthorMike Shulman
    • CommentTimeFeb 2nd 2019

    You may be on to something with the non-uniqueness however; a weakly terminal object in some category could be what you want.

    • CommentRowNumber12.
    • CommentAuthorPieter
    • CommentTimeFeb 2nd 2019

    Thanks for the analogy.

    Division between objects would be a ’quotient object’. Division between maps would be a ’quotient map’. Division between an object and map would be what?

    In my use-case, I have a map from an object representing a system behavior to an object representing a component, and I would like to find a specification of the remaining components. I’m “sideways” interested in finding a map into this specification as well, but am also happy to allow multiple of such maps. So perhaps version 3 of my definition is closest to my intuition at the moment.

    • CommentRowNumber13.
    • CommentAuthorPieter
    • CommentTimeFeb 2nd 2019

    Hm. How do you quote in this forum?

    • CommentRowNumber14.
    • CommentAuthorPieter
    • CommentTimeFeb 2nd 2019

    Thanks for the remark that I should not expect to determine an object without the morphisms that structure it.

    It is “easy” to see that any two remainder are adjoint by definition. So perhaps that is the best I can hope for?

    • CommentRowNumber15.
    • CommentAuthorPieter
    • CommentTimeFeb 2nd 2019
    • (edited Feb 2nd 2019)

    I’ve been reading up on congruence to understand quotient spaces better, but they have the ’opposite’ effect of what I want to achieve, it seems.

    • CommentRowNumber16.
    • CommentAuthorDavidRoberts
    • CommentTimeFeb 3rd 2019

    What reasoning leads you to dub this a ’remainder’? What is your working example that you want to apply this concept to?

    • CommentRowNumber17.
    • CommentAuthorMike Shulman
    • CommentTimeFeb 3rd 2019

    Re: terminology, a “quotient object” is actually technically already a quotient of an object by a map; you can’t divide one object by another without a morphism to relate them. Usually a “quotient map” is the map into a quotient object that gives it its universal property.

    What do you mean by “adjoint”?

    You could try looking at pushout complements and span rewriting, which are another way to “delete part of an object and replace it with something else”.

    • CommentRowNumber18.
    • CommentAuthorUrs
    • CommentTimeFeb 3rd 2019

    How do you quote in this forum?

    Prefix by >, as in

      > How do you quote in this forum?
    
    • CommentRowNumber19.
    • CommentAuthorDavid_Corfield
    • CommentTimeFeb 3rd 2019

    If you want to find out how someone on the nForum does something – quote, link, etc. – you can just find an instance and click on ’Source’.

    • CommentRowNumber20.
    • CommentAuthorPieter
    • CommentTimeFeb 3rd 2019

    What reasoning leads you to dub this a ’remainder’? What is your working example that you want to apply this concept to?

    I still have some doubts on whether it should be called remainder. Actually ’fraction’ may be a better term.

    As I mentioned in the opening of my post, I have a model of behavior of an entire (software) system, and I have a model of one of its components. Categorically, the relation between an entire system and its components can be seen as a jointly monic family. But in my current situation I have only been given a part of that family, and I want to make a “best guess” as to what the “remainder” may be, or the “fraction” of what I’m missing.

    The example from Set suggested by Mike shows that pretty well. If you have been given only one projection out of a pair of canonical projections from a product, my intuition tells me that finding the remainder means finding the other projection. In case products exist in a category, you can rephrase my question as: f:XYf : X \rightarrow Y has been given, now construct ZZ and a monomorphism XY×ZX \rightarrow Y \times Z that agrees with ff. In other words, given XX and YY you are finding the smallest ZZ such that XY×ZX \subseteq Y \times Z.

    Does that make sense?

    • CommentRowNumber21.
    • CommentAuthorPieter
    • CommentTimeFeb 3rd 2019

    The ’Source’ button is usefull ;-)

    • CommentRowNumber22.
    • CommentAuthorPieter
    • CommentTimeFeb 3rd 2019

    You could try looking at pushout complements and span rewriting

    That would require me to know more than ’just’ the map f:XYf : X \rightarrow Y to start with.

    But the suggestion is helpful in the sense that, in my definition, I could require an epimorphism into the remainder/fraction (I’m starting to prefer the term fraction, thanks for questioning David), rather than just a map. Switching to weak final objects leads to non-uniqueness, but requiring epi restores some of that.

    • CommentRowNumber23.
    • CommentAuthorPieter
    • CommentTimeFeb 3rd 2019
    • (edited Feb 3rd 2019)

    In summary so far, working through the above, how about this:

    • Definition: given f:XYf : X \rightarrow Y, a map g:XFg : X \rightarrow F is a fraction of ff if (f,g)(f,g) is jointly monic and for any jointly monic pair (f,h)(f,h) there exists a kk such that kh=gk h = g.

    • Uniqueness theorem: if g:XFg : X \rightarrow F and g:XFg' : X \rightarrow F' are epic fractions of f:XYf : X \rightarrow Y, then FF and FF' are isomorphic.

      Proof: (I guess this is a standard result for weakly final epis, but I am a real newbe, so I need to do this for my own understanding.) Consider g:XFg : X \rightarrow F and g:XFg' : X \rightarrow F' to be epimorphic fractions of f:XYf : X \rightarrow Y. Then there exist kk and kk' such that kg=gk g = g' and kg=gk' g' = g. So 1g=g=kg=kkg1 g = g = k' g' = k' k g and because gg is epic we find kk=1k' k = 1. Similarly, kk=1k k' = 1. Q.E.D.

    • Basic intuition theorem: consider the natural projections f:X×YXf : X \times Y \rightarrow X and g:X×YYg : X \times Y \rightarrow Y of a product X×YX \times Y, then ff is an epic fraction of gg and gg is an epic fraction of ff.

      Proof: that projections are epic is standard, and that the theorem is symmetric is clear, so we only need to prove that gg is a fraction of ff. How to go about that is not so clear to me. Maybe it is not even true in general, in which case my definition might need more tweaking.

    The definition at least works for the 2×22 \times 2 example in Set, and also seems to work for my own use-case examples. Next, I think it is worthwhile to see what tweaking is necessary to get the basic intuition theorem to work out…

    • CommentRowNumber24.
    • CommentAuthorDavidRoberts
    • CommentTimeFeb 3rd 2019
    • (edited Feb 3rd 2019)

    So here’s an interesting test case: Take for f:XYf\colon X\to Y some surjective function. Special cases of this are projections X=Y×FYX = Y\times F \to Y, for some standard fibre FF. But how to proceed when all the fibres are not necessarily isomorphic? In a suitable Boolean lextensive category (not sure of the addition extra requirements) one can do things like decompose XX into a disjoint sum of the subobject on which ff is injective, and the rest.

    • CommentRowNumber25.
    • CommentAuthorPieter
    • CommentTimeFeb 3rd 2019

    I’m trying to follow, but I lack a lot of category theoretic ’basics’ I’m afraid.

    Special cases of this are projections X=Z×F→Y, for some standard fibre F.

    I needed to read-up on fiber for this, but it doesn’t give me enough info on what you mean by this sentence. Can you spell your construction out in smaller steps, please?

    • CommentRowNumber26.
    • CommentAuthorMike Shulman
    • CommentTimeFeb 3rd 2019

    David just means a fixed object FF, which then happens to be the fiber of the projection Y×FYY\times F\to Y.

    As an example of his question, consider f:{,,}{0,1}f:\{\heartsuit,\spadesuit,\clubsuit\}\to \{0,1\} where f()=f()=0f(\heartsuit)=f(\spadesuit)=0 and f()=1f(\clubsuit)=1. Here it doesn’t seem to me that any fraction exists, since both g:{,,}{0,1}g:\{\heartsuit,\spadesuit,\clubsuit\}\to \{0,1\} where g()=f()=0g(\heartsuit)=f(\clubsuit)=0 and g()=1g(\spadesuit)=1 and h:{,,}{0,1}h:\{\heartsuit,\spadesuit,\clubsuit\}\to \{0,1\} where h()=f()=0h(\clubsuit)=f(\spadesuit)=0 and h()=1h(\heartsuit)=1 are jointly monic with ff, and “maximally” so in that they don’t remain so after composing with any non-injective function out of their codomains; but neither factors through the other.

    • CommentRowNumber27.
    • CommentAuthorPieter
    • CommentTimeFeb 3rd 2019
    • (edited Feb 3rd 2019)

    Thank you! That is a very nice example to chew on. It actually works in my category of behaviors of components as well. But I do notice that, in your example, gg and hh simply treat \heartsuit and \spadesuit in a ’reverse’ fashion, undistinguishable by ff. So my feeling is that both should be considered equivalent in some way, perhaps by allowing an auto-isomorphism on {,,}\{ \heartsuit, \spadesuit, \clubsuit \}.

    I.e. fractions should disregard symmetries on XX. I wouldn’t have found that on my own :-)

    • CommentRowNumber28.
    • CommentAuthorDavidRoberts
    • CommentTimeFeb 3rd 2019

    Thanks, Mike. That was indeed a typo, should have had ZZ be YY instead, so I’ve edited.

    • CommentRowNumber29.
    • CommentAuthorMike Shulman
    • CommentTimeFeb 4th 2019

    Here’s another thought: surjective functions with domain XX are the same as equivalence relations on XX, and although your ff isn’t assumed surjective, it only matters up to its image, hence up to its kernel pair which is the equivalence relation it determines. On this side, I think that what you are looking for is, given an equivalence relation RR on XX (the kernel of ff), you want another equivalence relation SS on XX such that RS=Δ XR\cap S = \Delta_X, the diagonal relation, and which is maximal with this property.

    • CommentRowNumber30.
    • CommentAuthorPieter
    • CommentTimeFeb 4th 2019
    • (edited Feb 4th 2019)

    Yes, that might work too, I suppose. (According to kernel you actually mean kernel pair, right? The pullback of ff along itself.)

    After a nights sleep, I figured out how to adapt my own definition a bit as well, so now I have two definitions which both seem reasonable (for the time being).

    • Definition 1: Given a map f:XYf : X \rightarrow Y, an object FF is a fraction of ff if for every g:XZg : X \rightarrow Z with (f,g)(f,g) jointly monic, there exists an h:ZFh: Z \rightarrow F such that (f,hg)(f,hg) is jointly monic and hghg is an epimorphism.
    • Theorem 1: Fractions are unique up-to isomorphism.

      Proof: let FF and FF' both be fractions of ff. Observe that (f,1)(f,1) is jointly monic. Applying the definition of fraction gives us maps g:XFg : X \rightarrow F and g:XFg' : X \rightarrow F' such that (f,g1)(f,g1) and (f,g1)(f,g'1) are jointly monic, and g=g1g = g1 and g=g1g' = g'1 are epimorphisms. Applying the definition of fraction again gives us maps hh and hh' such that hg=ghg = g' and hg=gh'g' = g. From this we obtain 1g=g=hg=hhg1g = g = h'g' = h' h g, and because gg is epic, 1=hh1 = h' h. Similarly, 1=hh1 = h h'. So hh and hh' are isomorphisms between FF and FF'.

    • Conjecture: Given a natural projection f:X×YXf : X \times Y \rightarrow X, if ff has a fraction, then it is isomorphic to YY.

    • Conjecture: Given a natural projection f:X×YXf : X \times Y \rightarrow X, we find YY is a fraction of ff.

    And my first quick attempt to formalize Mike’s suggestion, while keeping it ’comparable’ to the first definition. (I’m not sure if I got the translation into arrows entirely right, please have a look).

    • Definition 2 : Given a map f:XYf : X \rightarrow Y. Let k,k:RXk,k' : R \rightarrow X be the kernel pair of ff (the pullback of ff over itself). An object FF is a fraction of ff if there exists an epimorphism g:XFg : X \rightarrow F for which the kernel pair h,h:SXh,h' : S \rightarrow X (the pullback of gg over itself) has the property that every m:XZm : X \rightarrow Z with hm=hmhm = h'm and km=kmkm = k'm is a monomorphism.

    • Conjecture: Fractions are unique up-to isomorphism.

    • Conjecture: Given a natural projection f:X×YXf : X \times Y \rightarrow X, if ff has a fraction, then it is isomorphic to YY.

    • Conjecture: Given a natural projection f:X×YXf : X \times Y \rightarrow X, we find YY is a fraction of ff.

    I’ll get back later to seeing whether I can prove any of the conjectures, or find conditions under which they can be proven.

    • CommentRowNumber31.
    • CommentAuthorMike Shulman
    • CommentTimeFeb 6th 2019

    Definition 2 : Given a map f:XYf : X \rightarrow Y. Let k,k:RXk,k' : R \rightarrow X be the kernel pair of ff (the pullback of ff over itself). An object FF is a fraction of ff if there exists an epimorphism g:XFg : X \rightarrow F for which the kernel pair h,h:SXh,h' : S \rightarrow X (the pullback of gg over itself) has the property that every m:XZm : X \rightarrow Z with hm=hmh m = h'm and km=kmk m = k'm is a monomorphism.

    Close! But I think the inclusions go the other direction: hm=hmh m = h' m means that the kernel pair of mm contains (h,h)(h,h'), not conversely. Also there should be some kind of maximality condition, e.g. that their union in the poset of equivalence relations is the full relation, i.e. they are complements in that poset. Finally, an object in category theory should be equipped with a morphism rather than just be such that a morphism exists (e.g. a cartesian product is equipped with projections AA×BBA\leftarrow A\times B \to B). So if we turn all the equivalence relations into epimorphisms, I would state the definition something like this:

    Definition 2: Given a map f:XYf : X \rightarrow Y, a fraction of ff is an epimorphism g:XFg:X\to F such that (1) if e:XZe:X\to Z is an epimorphism such that ff and gg both factor through it, then ee is an isomorphism; and (2) the pushout of ff and gg is constant (factors through the terminal object).

    However, with this definition as stated, your first conjecture

    Fractions are unique up to isomorphism.

    is false in complete generality. Consider any lattice PP as a thin category and let xPx\in P be an object that has more than one distinct complement, i.e. y,yy,y' with xy=xy=0x\wedge y = x\wedge y' = 0 and xy=xy=1x\vee y = x\vee y' = 1. Then since every morphism in a thin category is epi, 0y0\to y and 0y0\to y' are nonisomorphic fractions of 0x0\to x. This is also a counterexample to your second conjecture, since 0=x×y=x×y0 = x\times y = x\times y'.

    However, a more reasonable formulation would be to add conditions on the category and/or restrict to some well-behaved subclass of epimorphisms like strong, extremal, or regular ones. Of course it’s still false if you ask for the isomorphism to respect the morphisms from XX, but absent that condition I don’t yet know the answer (though there could still be an easy one, I haven’t thought about it very hard).

    Moreover, your third conjecture:

    Given a natural projection f:X×YXf : X \times Y \rightarrow X, we find YY is a fraction of ff.

    is almost true, in good cases. It’s not quite true even in SetSet because X×YYX\times Y \to Y may not be an epimorphism (consider X=X=\emptyset), but it is true in SetSet if both XX and YY are nonempty. More generally, I believe it is true in any regular category if instead of “epimorphism” we say “regular epimorphism” (or assume that all epis are regular, as in a pretopos) and assume that XX and YY are well-supported, i.e. X1X\to 1 and Y1Y\to 1 are regular epi. (The proof I have in mind uses the internal language, though, and I haven’t tried to compile it out in terms of arrows.)

    I feel like the structure of the lattice of equivalence relations (or quotients) of an object in a regular category must have been studied before, but I don’t know where to find it. Perhaps stackexchange might help.

    • CommentRowNumber32.
    • CommentAuthorTodd_Trimble
    • CommentTimeFeb 6th 2019

    Classically, the lattice of equivalence relations on a set forms a geometric lattice or a matroid lattice. I don’t think I’ve ever considered the situation for more general regular (or exact) categories.

    • CommentRowNumber33.
    • CommentAuthorPieter
    • CommentTimeFeb 7th 2019

    Definition 2: Given a map f:X→Y, a fraction of f is an epimorphism g:X→F such that (1) if e:X→Z is an epimorphism such that f and g both factor through it, then e is an isomorphism; and (2) the pushout of f and g is constant (factors through the terminal object).

    Thanks Mike, I already felt actually creating the kernel pairs was cumbersome. I’m still chewing on the ’constant’ part, which is a new trick for me.

    • CommentRowNumber34.
    • CommentAuthorMike Shulman
    • CommentTimeFeb 7th 2019

    My thinking was that if ff is also epi, then the pushout should be the terminal object, since that would correspond to the union of the kernel pairs of ff and gg in the lattice of equivalence relations being the full relation. If ff is not epi then whatever extra stuff is in its codomain will still be there in the pushout, but the map from XX to the pushout factors through the image of the image of ff, hence through the terminal object.

    • CommentRowNumber35.
    • CommentAuthorMike Shulman
    • CommentTimeFeb 7th 2019

    @Todd, thanks! Do you know if anything is known about the relation of “having isomorphic quotients” on that lattice?

    • CommentRowNumber36.
    • CommentAuthorTodd_Trimble
    • CommentTimeFeb 8th 2019

    Mike, I haven’t been following this thread, and so I may be misunderstanding or maybe I’m being dense, but: what do you mean? I consider two quotients q:XYq: X \to Y and q:XYq': X \to Y' to be isomorphic if there is an isomorphism YYY \to Y' making the obvious triangle commute. In that case, qq and qq' correspond to the same equivalence relation. So I don’t know what you’re asking.

    • CommentRowNumber37.
    • CommentAuthorMike Shulman
    • CommentTimeFeb 8th 2019

    I mean an isomorphism YYY\cong Y' not making the obvious triangle commute.

    • CommentRowNumber38.
    • CommentAuthorPieter
    • CommentTimeFeb 10th 2019

    Trying to relate your definition to mine, I discovered the following (which is probably already obvious to you).

    Theorem: in a category in which all products exist (f,g)(f,g) is jointly monic if and only if any map mm that factors through ff and gg is monic.

    That any epi that factors through (f,g)(f,g) is iso would then be true in any category where mono+epi implies iso.

    • CommentRowNumber39.
    • CommentAuthorMike Shulman
    • CommentTimeFeb 10th 2019

    in a category in which all products exist (f,g)(f,g) is jointly monic if and only if any map mm that factors through ff and gg is monic.

    That doesn’t sound right. The map to the terminal object always factors through ff and gg, but isn’t generally monic. Maybe I misunderstood what you mean?

    • CommentRowNumber40.
    • CommentAuthorPieter
    • CommentTimeFeb 11th 2019

    Ah, or maybe I misunderstood what you mean by “factors through”. I couldn’t find a formal definition… I’ll elaborate on what I found and make it self-contained, including the standard definitions. (Is there a way to put diagrams in posts?)

    • Definition: a map f:XYf : X \rightarrow Y is monic if for any two i,j:AXi,j : A \rightarrow X with fi=fjfi = fj we find i=ji = j.
    • Definition: a pair (f,g)(f,g) of maps f:XYf : X \rightarrow Y and g:XZg : X \rightarrow Z is jointly monic if for any two i,j:AXi,j : A \rightarrow X with fi=fjfi=fj and gi=gjgi=gj we find i=ji = j.
    • Definition: a product of YY and ZZ is an object Y×ZY \times Z with projections k:Y×ZYk : Y \times Z \rightarrow Y and l:Y×ZZl : Y \times Z \rightarrow Z such that for any pair f:XYf : X \rightarrow Y, g:XZg : X \rightarrow Z there is a unique map h:XY×Zh : X \rightarrow Y \times Z such that kh=fkh = f and lh=glh = g.

    • Theorem 1: given a pair (f,g)(f,g) of jointly monic maps f:XYf : X \rightarrow Y and g:XZg : X \rightarrow Z, let h:XBh : X \rightarrow B be such that there exist k:BXk : B \rightarrow X and l:BYl : B \rightarrow Y with f=khf = kh and g=lhg = lh, then hh is monic.

      Proof: assume two i,j:AXi,j : A \rightarrow X such that hi=hjhi = hj, then fi=khi=khj=fjfi = khi = khj = fj and gi=lhi=lhj=gjgi = lhi = lhj = gj, so by joint monicity i=ji = j. Therefore, hh is monic.

    • Theorem 2: assuming products exist, let (f,g)(f,g) be a pair of maps f:XYf : X \rightarrow Y and g:XZg : X \rightarrow Z. Furthermore, assume that for any h:XBh : X \rightarrow B with k:BXk : B \rightarrow X and l:BYl : B \rightarrow Y such that f=khf = kh and g=lhg = lh we find hh is monic. Then (f,g)(f,g) is jointly monic.

      Proof: Observe that in particular h:XY×Zh : X \rightarrow Y \times Z is assumed to be monic, with k:X×YXk : X \times Y \rightarrow X and l:X×YYl : X \times Y \rightarrow Y the natural projections from the product. Now, let i,j:AXi,j : A \rightarrow X be a pair of maps such that fi=fjfi = fj and gi=gjgi = gj. Then by definition of product there is a unique arrow u:AY×Zu : A \rightarrow Y \times Z such that ku=fiku = fi and lu=gilu = gi, as well as a unique arrow u:AY×Zu' : A \rightarrow Y \times Z such that ku=fjku' = fj and lu=gjlu' = gj. Because fi=fjfi = fj and gi=gjgi = gj we find u=uu = u', and because khi=fikhi = fi and lhi=gilhi = gi we find u=hiu = hi and similarly u=hju' = hj. Therefore, hi=hjhi = hj. We assumed hh to be monic, therefore i=ji = j, which concludes the proof that (f,g)(f,g) is jointly monic.

    • CommentRowNumber41.
    • CommentAuthorMike Shulman
    • CommentTimeFeb 11th 2019

    Ah, I see the confusion. When f=hkf = h k we say that ff factors through hh (since writing f=hkf = h k is “factoring” ff, analogously to 6=236 = 2\cdot 3), not that hh factors through ff.

    • CommentRowNumber42.
    • CommentAuthorPieter
    • CommentTimeFeb 11th 2019

    Thanks… But then, when f=hkf = hk, do you also say ff factors through kk? In that case, using the sentence “factors through” without an indication of left or right is ambiguous…

    Now I’ll reread the posts above to see if they make sense again/still to me ;-)

    The little theorem is what it is, of course. But I guess it is also pretty standard for people working with joint morphisms often. I guess so standard that there is no reference for it… Does something like that deserve a wiki-page or comment according to you? There is value in such ’trivia’, but there is also a big risk of a wiki become just a collection of such trivia then…

    • CommentRowNumber43.
    • CommentAuthorPieter
    • CommentTimeFeb 11th 2019

    Back to your definition:

    Definition 2: Given a map f:XYf: X \rightarrow Y, a fraction of f is an epimorphism g:XFg : X \rightarrow F such that (1) if e:XZe : X \rightarrow Z is an epimorphism such that ff and gg both factor through it, then ee is an isomorphism; and (2) the pushout of ff and gg is constant (factors through the terminal object).

    In a category where epi+mono implies iso, this is equivalent to saying

    • Definition 2b: Given a map f:XYf: X \rightarrow Y, a fraction of f is an epimorphism g:XFg : X \rightarrow F such that (1) if e:XZe : X \rightarrow Z is an epimorphism such that ff and gg both factor through it, then ee is a monomorphism; and (2) the pushout of ff and gg is constant (factors through the terminal object).

    Which in a category where products exist comes down to

    • Definition 2c: Given a map f:XYf: X \rightarrow Y, a fraction of f is an epimorphism g:XFg : X \rightarrow F such that (1) (f,g)(f,g) is a joint morphism; and (2) the pushout of ff and gg is constant (factors through the terminal object).

    That definition is closer to my goal of treating compositions as relations between objects, and under mild conditions coincides with your intuition according to my previous post. Nice.

    Now, I’ll start studying the factoring through a terminal object as a way to obtain isomorphism of fractions under reasonable conditions :-)

    • CommentRowNumber44.
    • CommentAuthorMike Shulman
    • CommentTimeFeb 11th 2019

    using the sentence “factors through” without an indication of left or right is ambiguous

    Technically, yes. Although that would be true regardless of which of ff or hh is said to “factor through” the other. But if ff and hh share a domain but not a codomain, or a codomain but not a domain, as is usually the case, then the ambiguity is resolved as only one choice is possible.

    Does something like that deserve a wiki-page or comment according to you?

    Yes, I would probably generalize it to a statement about one family of morphisms factoring through another jointly-monic family, and add it in a “Properties” section to jointly monic family. The special case when both families are single morphisms is already recorded at monomorphism#properties: if gfg f is a monomorphism, so is ff.

    • CommentRowNumber45.
    • CommentAuthorPieter
    • CommentTimeFeb 13th 2019

    I’ll give it a shot as soon as I have the time :-)

    • CommentRowNumber46.
    • CommentAuthorPieter
    • CommentTimeFeb 13th 2019
    • (edited Feb 13th 2019)

    Now, I’ll start studying the factoring through a terminal object as a way to obtain isomorphism of fractions under reasonable conditions :-)

    Firstly, if I’m not mistaken, using the existence of pushouts is not necessary, because the terminal object is supposed to be the pushout… so

    • Definition 2: a map g:XZg: X \rightarrow Z is a fraction of f:XYf : X \rightarrow Y if 1) (f,g)(f,g) is jointly monic, 2) gg is epic, and 3) for any h:YAh: Y \rightarrow A and k:ZAk : Z \rightarrow A with hf=kghf = kg, we find hfhf is constant (i.e. factors through the terminal object).

    Following your idea (I think) the extension of ff and gg into a commuting square represents the “union, closed under symmetry and transitivity” of the equivalences represented by the original maps ff and gg. That sounds okay to me. If this union is constant, i.e. factors through the terminal object, that implies that “all information is thrown away” by the new equivalence, i.e. everything is equated.

    That last part is close, but not the same I think, as my intuition that: whenever ff makes a distinction, then gg should try to avoid making this distinction.

    The tricky part is that in some categories, gg may not be able to avoid making distinctions. In my category of choice, a terminal object exists, but nonetheless I’m not sure that gg is free to avoid making distinctions (okay perhaps that just means the distinctions will show up in the terminal object then… true… but this is subtle). I’d have to think about quite examples for a while to make this more concrete though. Furthermore, I don’t like to have to use the terminal object as part of my definition, because I think that having a constant map implies that all information is thrown away, rather than that it is the same as saying all information is thrown away. In a sense, using the terminal object makes the definition stronger than I intend it to be.

    • CommentRowNumber47.
    • CommentAuthorPieter
    • CommentTimeFeb 13th 2019
    • (edited Feb 13th 2019)

    Some more thought…

    So given maps f:XYf : X \rightarrow Y and g:XZg : X \rightarrow Z the intuition is that whenever e=hf=kge = hf = kg, the map ee equates whatever is equated by ff or gg. If we want to state that ee equates ’everything’, we could state that as ee is constant, but this requires the existence of a terminal object. Alternatively, we could perhaps also state that X×XX \times X is the kernel of ee?

    • Definition 3: a map g:XZg : X \rightarrow Z is a fraction of f:XYf : X \rightarrow Y if 1) (f,g)(f,g) is jointly monic, 2) gg is epic, and 3) any map ee that factors through ff and gg has X×XX \times X as its kernel.

    Pity I still have to assume existence of the product X×XX \times X, but imho better than using a terminal object (is there a difference whenever both exist?). Also a pity that gg being epic does not simply follow from a “smallest solution” condition, and that I do not immediately see under which conditions we get uniqueness of fractions. I agree with you, however, that this may in general be unreasonable to assume, but should work out in reasonable conditions.

    • CommentRowNumber48.
    • CommentAuthorMike Shulman
    • CommentTimeFeb 14th 2019

    What do you have against terminal objects?

    • CommentRowNumber49.
    • CommentAuthorMike Shulman
    • CommentTimeFeb 14th 2019

    In general, X×XX\times X being the kernel of ee is the same as saying that for any two morphisms u,vu,v with codomain XX we have eu=eve u = e v, i.e. that ee is a constant morphism in the weak sense. If ee has an image, this is the same as saying that that image is subterminal, and I think it would be better for it to be terminal. But note that at constant morphism there is given a way to phrase the strong sort of “constancy” without assuming the existence of a terminal object, so if you really happen to be in a category without a terminal object (but with pullbacks and products? I can’t think of too many categories like that) then you could use that.

    • CommentRowNumber50.
    • CommentAuthorPieter
    • CommentTimeFeb 22nd 2019
    • (edited Feb 22nd 2019)

    What do you have against terminal objects?

    It’s personal ;-) I’d rather not be dependent on them, because I have the intuition that ’being constant’ has nothing to do with ’being terminal’. I didn’t look it up earlier, because I simply accepted your definition of factoring through the terminal object, but your reference to constant morphism helped a lot. I like the first definition much better than the second, and it also fits better when combining it with joint-monicity.

    Why do you feel that it would be better for it to be terminal? I understand this gives you more/better properties, but I only want those properties if they also follow intuitively from what I think a fraction should be. In other words, why ask for a strong definition if the weak definition is sufficient to capture what you want? To me that goes against Occam’s razor, so to speak.

    • CommentRowNumber51.
    • CommentAuthorMike Shulman
    • CommentTimeFeb 22nd 2019

    Well, in general I believe the second stronger definition of constant is better. However, it looks like in this case I may have been led astray by that general fact, because what we’re doing is rephrasing stuff about equivalence relations in terms of their quotients, and the quotient that corresponds to the full relation is the support of an object, which is subterminal and not necessarily terminal. So in this case, I think you’re probably right to use the weaker notion.