Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

July 24, 2010

Ternary Factorization Systems

Posted by Mike Shulman

We’ve been having a bit of discussion on the nForum about ternary and higher-ary factorization systems in categories and higher categories. A kk-ary factorization system is supposed to give a way of factoring any morphism into a composite of kk morphisms of specified types. Ordinary “factorization systems” are binary factorization systems, which factor every morphism into a binary composite; for instance, the factorization of a set function into a surjection followed by an inclusion.

The first place we noticed these higher-ary factorization systems is in the “Postnikov decomposition” of higher categories. The basic example is that any functor f:ABf\colon A\to B factors as Aim 2(f)im 1(f)B A \to im_2(f) \to im_1(f) \to B where im 1(f)Bim_1(f)\to B is full and faithful, im 2(f)im 1(f)im_2(f) \to im_1(f) is essentially surjective and faithful, and Aim 2(f)A\to im_2(f) is essentially surjective and full. Similarly, we expect a functor between nn-categories to have a natural (n+2)(n+2)-ary factorization. This is called the “layer-cake” view of cohomology as John described here (while I took notes, and somehow ended up with my name on the paper too). However, higher-ary factorization systems (and in particular, ternary ones) also turn up in some other surprising places. But surprisingly, they don’t ever seem to have been precisely defined by anyone, and there are lots of unanswered questions!

So how do we define a ternary or k-ary factorization system? An ordinary “binary” factorization system consists of two classes of maps (L,R)(L,R), such that LL is orthogonal to RR, and every morphism factors as an LL-map followed by an RR-map. The last condition is easy to generalize to a kk-ary factorization with kk classes of maps, but what is the right counterpart of orthogonality?

I think we get a very nice theory by looking at kk-ary factorizations in a different way. Consider the factorization of a functor described above. In fact, there are two ordinary (binary) factorization systems visible here as well, namely (ess.surj., full + faithful), and (ess.surj + full, faithful). Moreover, the ternary factorization can be obtained in two equivalent ways: we can either

  1. first factor ff as an essentially surjective functor followed by a full + faithful one, and then factor the essentially surjective functor into an ess.surj+full one followed by a faithful one; or
  2. first factor ff as an ess.surj+full functor followed by a faithful one, and then factor the faithful functor into an essentially surjective one followed by a full+faithful one.

This suggests the following definition: a ternary factorization system is a pair of ordinary (binary) factorization systems (L 1,R 1)(L_1,R_1) and (L 2,R 2)(L_2,R_2) such that L 1L 2L_1 \subseteq L_2 (and hence R 2R 1R_2 \subseteq R_1). The above situation generalizes as follows.

Theorem 1: Given a ternary factorization system as above, any morphism ff factors as AL 1im 2(f)L 2R 1im 1(f)R 2B A \overset{L_1}{\to} im_2(f) \overset{L_2 \cap R_1}{\to} im_1(f) \overset{R_2}{\to} B in an essentially unique way.

Proof: Consider the two ternary factorizations of ff obtained as above, by

  1. First factoring ff into an L 1L_1-map followed by an R 1R_1-map, then factoring the R 1R_1-part into an L 2L_2-map followed by an R 2R_2-map; and
  2. First factoring ff into an L 2L_2-map followed by an R 2R_2-map, then factoring the L 2L_2-part into an L 1L_1-map followed by an R 1R_1-map.

Note that both start with an L 1L_1 map and end with an R 2R_2 map. By a straightforward exercise in orthogonality, we can get comparison maps in both directions between these two factorizations which make them isomorphic. Therefore, since the first produces a middle map which is in L 2L_2 and the second produces a middle map which is in R 1R_1, this middle map must in fact be in L 2R 1L_2\cap R_1. Finally, any other such ternary factorization of ff induces an (L 1,R 1)(L_1,R_1) and (L 2,R 2)(L_2,R_2) factorization by composing pairwise, and uniqueness of these two implies uniqueness of the ternary factorization.

Toby has proposed a natural generalization of this to kk-ary factorization systems.

(Note that another way to define ordinary binary factorization systems is by uniqueness rather than orthogonality. This is the approach taken at Joyal’s catlab. Does this generalize to the k-ary case?)

The motivating example of factoring a functor is actually a factorization system on a 2-category, which means that orthogonality and uniqueness only hold up to isomorphism. However, once we write the definition in the above form, we can see that there are also lots of ternary factorization systems on 1-categories: we get one from any pair of ordinary factorization systems, one included in the other.

For instance, in the category of topological spaces, let L 1=L_1= quotient maps, R 1=R_1= injective continuous maps, L 2=L_2= surjective continuous functions, and R 2=R_2= subspace embeddings. Here L 2R 1=L_2\cap R_1= bijective continuous maps, and the resulting ternary factorization factors a continuous map by imposing the coarsest and the finest compatible topologies on its set-theoretic image.

As another example, some people use the word image to refer to an (epi, regular mono) factorization and coimage to refer to a (regular epi, mono) factorization. It is well-known in this context there is a map from the coimage to the image, which is in fact another instance of ternary factorization. In this case L 2R 1L_2\cap R_1 is the class of monic epics, sometimes called bimorphisms. (The example of Top is a special case of this one.)

Returning to the theory, so far we can see that a ternary factorization system determines five classes of maps: L 1L_1, R 1R_1, L 2L_2, R 2R_2, and L 2R 1L_2\cap R_1. In the original motivating example, these are respectively the ess.surj.+full, faithful, ess.surj., full+faithful, and ess.surj+faithful functors. However, there’s a sixth class of functors that’s conspicuously missing from this list: full functors. In fact, any ternary factorization system canonically determines a sixth class: the class of morphisms whose (L 2R 1)(L_2\cap R_1)-part is an isomorphism, or equivalently those that can be factored as an L 1L_1-map followed by an R 2R_2-map. Thus, let’s call this class R 2L 1R_2 L_1.

It’s not hard to see that this gives the right answer in CatCat: a functor is full iff it can be factored as an ess.surj.+full functor followed by a full+faithful one. In the topological example, these are the continuous maps for which the quotient and subspace topologies on their set-theoretic images coincide. In the image/coimage situation, this class of maps are sometimes called strict morphisms (I have no idea why). We can also generalize the fact that a full+faithful functor is the same as one which is both full and faithful:

Theorem 2: In a ternary factorization system, L 1=L 2R 2L 1L_1 = L_2 \cap R_2L_1 and R 2=R 1R 2L 1R_2 = R_1 \cap R_2L_1.

Proof: In both cases \subseteq is obvious. Conversely, if fL 2R 2L 1f \in L_2 \cap R_2 L_1, say f=mef = m e for mR 2m\in R_2 and eL 1e\in L_1, then orthogonality in the square a e c f m b id b\array{a & \overset{e}{\to} & c\\ ^f \downarrow && \downarrow ^m\\ b & \underset{id}{\to} & b} exhibits ff as a retract of ee in Arr(C)Arr(C), whence fL 1f\in L_1 since L 1L_1 is closed under retracts.

Can this also be generalized to kk-ary factorization systems? I don’t know.

Let me end with an observation that I find quite suggestive, although I admit I have no idea what it is trying to suggest. The ordinary notion of (binary) factorization system can be generalized in a different direction to a weak factorization system, so it’s natural to think about pairs of WFS (L 1,R 1)(L_1,R_1) and (L 2,R 2)(L_2,R_2) with L 1L 2L_1\subseteq L_2.

However, this is precisely the sort of WFS data which underlies a model category, where L 1=L_1= acyclic cofibrations, L 2=L_2= cofibrations, R 1=R_1= fibrations, and R 2=R_2= acyclic fibrations. What are the two other classes of maps in this case? Well, L 2R 1=L_2 \cap R_1 = maps that are both cofibrations and fibrations; that doesn’t seem very interesting. But R 2L 1=R_2 L_1 = maps that can be factored as an acyclic cofibration followed by an acyclic fibration, and those are precisely the weak equivalences – the fifth class of maps in a model category.

Of course, Theorem 1 doesn’t hold in the WFS case, where factorizations are never unique, so it doesn’t really make sense to call this a “ternary weak factorization system”. Neither does the characterization of R 2L 1R_2 L_1 as the maps whose L 2R 1L_2\cap R_1-part is an isomorphism. However, Theorem 2 does still hold — a map is an acyclic cofibration iff it is both a cofibration and a weak equivalence.

Is there something deep going on here? Is it good for anything? I don’t know. But it reminds me of the theory of algebraic weak factorization systems structures, and the difficulty in finding a corresponding notion of “algebraic model category.” An inclusion between two WFS (or a map, in the algebraic case) determines a model structure if and only if the class of weak equivalences, defined as the maps that factor as an acyclic cofibration followed by an acyclic fibration, has the 2-out-of-3 property. But in practice, starting from that definition the 2-out-of-3 property is usually quite difficult to verify. Could the perspective of ternary factorization systems be helpful?

Posted at July 24, 2010 8:59 AM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2245

28 Comments & 0 Trackbacks

Re: Ternary factorization systems

Maybe one place nForum doesn’t function as well as the Café is in linking discussions to older discussions. E.g., from the post we get sent here, but that doesn’t lead us back to an earlier discussion.

Maybe there’s little there, but you never know.

Posted by: David Corfield on July 28, 2010 5:36 PM | Permalink | Reply to this

Re: Ternary factorization systems

In fact there isn’t even a link through to this discussion which temporally overlaps the first one.

Posted by: David Corfield on July 28, 2010 5:45 PM | Permalink | Reply to this

Re: Ternary factorization systems

Toby has proposed a natural generalization of this to kk-ary factorization systems.

The important thing about that is that it works even when kk is infinite. The generalisation to k>3k \gt 3 but finite is due to Mike earlier in the thread.

If anybody is having trouble reconciling my infinitary version and Mike's finitary version, here is what you should notice: my α\alpha is Mike's k+1k + 1, and while Mike's kk-ary factorisation system has k1k - 1 (hence α2\alpha - 2) binary factorisation systems, my α\alpha-stage factorisation system has α\alpha (hence k+1k + 1) binary factorisation systems. In this case, my two extra factorisation systems are trivial ones of the form (all,iso)(\text{all},\text{iso}) and (iso,all)(\text{iso},\text{all}). (In general, these appear whenever α\alpha is bounded as a poset.)

Posted by: Toby Bartels on July 28, 2010 7:23 PM | Permalink | Reply to this

Re: Ternary factorization systems

Actually, I think that my definition is not complete. Surely there is a missing condition when α=ω+ω op\alpha = \omega + \omega^{\op}, for example? However, I think that it should be correct whenever α\alpha is either an ordinal or the opposite of an ordinal, along with some other situations such as α=ω op+ω\alpha = \omega^{\op} + \omega (which is the ordinal type of the integers).

I will think about it some more.

In the meantime, everybody who doesn't care about infinitary factorisation systems should still talk about Mike's idea for finitary factorisation systems, which we certainly know how to define, or at least we think that we do.

Posted by: Toby Bartels on July 28, 2010 7:41 PM | Permalink | Reply to this

Re: Ternary factorization systems

Concerning ternary factorization and model categories:

might it be useful to think of this with “model 2-categories” in mind?

maybe replacing both the (cof,trivfib)(cof,triv-fib) binary system of model categories and (trivcof,fib)(triv-cof,fib)-sytem each by a ternary system leads to some structure on a 2-category that can present (,2)(\infty,2)-categories?

(I have no real clue, just a guess, given that ternary factorization systems want to live in 2-categories, not 1-categories.)

Posted by: Urs Schreiber on July 28, 2010 10:26 PM | Permalink | Reply to this

Re: Ternary factorization systems

Let me see, maybe I am thinking something like this:

in a model category, the factorization system serves to encode homotopies between 1-morphisms.

If I assume the model cat is tensored over sSetsSet, for simplicity, then the basic left factorization is

Δ 1Δ 1Δ 0. \partial \Delta^1 \hookrightarrow \Delta^1 \stackrel{\simeq}{\to} \Delta^0 \,.

Tensored with a (cofibrant) object XX this gives the factorization of the codiagonal

XXXΔ 1X X \coprod X \hookrightarrow X \cdot \Delta^1 \stackrel{\simeq}{\to} X

which defines left homotopies between 1-morphisms

X XΔ 1 Y X. \array{ X & \\ \downarrow & \searrow \\ X \cdot \Delta^1 &\to& Y \\ \uparrow & \nearrow \\ X } \,.

Okay, now in a “model 2-category”, we might want to encode in an analogous way homotopies between 2-morphisms.

I’ll switch to globular thinking for this and think of

Δ 1Δ 1Δ 0 \partial \Delta^1 \to \Delta^1 \to \Delta^0

now equivalently as

G 1G 1G 0, \partial G^1 \to G^1 \to G^0 \,,

where G nG^n is the nn-globe. Then it looks like what we want in order to encode the homotopy 2-category of a would-be model 2-category is the ternary factorization

G 0G 0G 2G 2G 1. G^0 \coprod G^0 \hookrightarrow \partial G^2 \hookrightarrow G^2 \stackrel{\simeq}{\to} G^1 \,.

So

XG 1Y X \cdot G^1 \to Y

would model a 2-cell between two 1-morphisms XYX \to Y, as before, but now not necessarily invertible. Then

XG 1 XG 2 Y XG 1. \array{ X \cdot G^1 & \\ \downarrow & \searrow \\ X \cdot G^2 &\to& Y \\ \uparrow & \nearrow \\ X \cdot G^1 } \,.

would model an invertible 3-cell between two parallel possibly directed 2-cells, whose common source and target 1-morphisms would be given by

XG 1 X XG 2 Y XG 1. \array{ &&X \cdot G^1 & \\ & \nearrow \nearrow &\downarrow & \searrow \\ X && X \cdot G^2 &\to& Y \\ &\searrow \searrow & \uparrow & \nearrow \\ &&X \cdot G^1 } \,.

Some kind of argument like this might motivate ternary factorization systems for “model 2-categories”. And then (k+1)(k+1)-ary ones for “model kk-categories”, possibly.

(I’ll let you decide whether it is wise of me to post at this time of night…)

Posted by: Urs Schreiber on July 29, 2010 12:34 AM | Permalink | Reply to this

Re: Ternary factorization systems

Hmm, interesting idea. I’m a little skeptical because ordinary model categories already encode higher homotopies using only two weak factorization systems, but it’s conceivable something along these lines might exist.

Posted by: Mike Shulman on July 31, 2010 4:49 AM | Permalink | Reply to this

Re: Ternary factorization systems

Miles Gould and I came across kk-ary factorization systems during the course of his PhD investigations, though I’m not sure that they actually made it into his thesis.

We had a leading example similar to yours, together with a variant, which I’ll now explain. (Maybe you’ve also discussed this at the nLab/Forum.)

The standard ‘BOFF’ factorization system on CatCatbijective on objects/full and faithful — is really a factorization system on the category GphGph of directed graphs, lifted to CatCat. There’s an easy theorem:

Theorem  Let (E,M)(E, M) be a factorization system on a category CC. Let TT be a monad on CC, and write U:C TCU: C^T \to C for the forgetful functor. Define E¯={finC T:UfE},M¯={finC T:UfM}. \overline{E} = \{ f in C^T: U f \in E \}, \quad \overline{M} = \{ f in C^T: U f \in M \}. Suppose that TT preserves EE-arrows. Then (E¯,M¯)(\overline{E}, \overline{M}) is a factorization system on C TC^T.

(You can find a proof as Lemma 3.0.7 of Miles’s thesis, though it’s not due to him, as he notes.)

For example, let TT be the free category monad on GphGph. Take the BOFF factorization system on GphGph. The image under TT of a bijective-on-objects map of graphs is again bijective on objects, so there is an induced factorization system on Gph T=CatGph^T = Cat — namely, BOFF.

Now, there is a similar BOFF-like (n+1)(n + 1)-ary factorization system on the category n-Gphn\text{-}Gph of nn-graphs (nn-globular sets). This is the ‘variant’ I mentioned. One might hope for an analogue of the theorem above, which would apply to the free strict nn-category monad TT on n-Gphn\text{-}Gph to give the (n+1)(n + 1)-factorization system on n-Catn\text{-}Cat.

I don’t think Miles and I thought very hard about what that analogous theorem should be. Perhaps someone else knows?

Posted by: Tom Leinster on July 29, 2010 10:56 AM | Permalink | Reply to this

Re: Ternary factorization systems

Interesting, thanks!

The bo-ff factorization system is the “1-categorical” version of the bicategorical eso-ff factorization system that I was thinking more about, but they are of course closely related.

One might hope for an analogue of the theorem above… I don’t think Miles and I thought very hard about what that analogous theorem should be.

If a kk-ary factorization system is just k1k-1 nested binary factorization systems, as I proposed, then it seems that the easy theorem you mentioned for binary factorization systems ought to directly imply an analogous theorem for kk-ary ones. Am I missing something?

Posted by: Mike Shulman on July 31, 2010 4:54 AM | Permalink | Reply to this

Re: Ternary Factorization Systems

It might be useful to invoke Eugenia Cheng’s work on iterated distributive laws, which John discussed in This Week’s Finds 257.

A monad in the bicategory of spans is exactly a category. Bob Rosebrugh and Richard Wood showed some time ago that a distributive law between such monads is exactly a strict factorization system. By ‘strict’ I mean that every map factorizes uniquely as a map from the left class followed by a map from the right class. (Of course this is much too restrictive for most situations, but let’s go with it.)

A strict kk-fold factorization system should therefore be defined as a kk-fold distributive law. This means a sequence of kk monads on the same object of the bicategory of spans — that is, a sequence of kk categories with the same object-set — together with a distributive law of the iith over the jjth whenever i<ji &lt; j, all subject to a Yang–Baxter equation for each i<j<ki &lt; j &lt; k.

The definition is, of course, set up so that the usual facts about distributive laws extend to the kk-fold setting. In particular, a kk-fold distributive law tells you how to glue together those kk categories (monads in Span) to obtain a single category (monad in Span). This is the category on which the kk-fold factorization system is defined.

What remains, then, is to move from the strict to the not-so-strict setting. Lack and Street’s ‘Formal theory of monads 2’ may be some help here.

Posted by: Tom Leinster on July 30, 2010 6:26 PM | Permalink | Reply to this

Re: Ternary Factorization Systems

The Rosebrugh–Wood paper is ‘Distributive laws and factorization’, JPAA 175. It’s here. Looks pretty nifty, too.

I’ve only skimmed the paper, but it seems they also characterise non-strict/orthogonal factorisation systems by way of (what look like some kind of) pseudo-distributive laws.

Posted by: Finn Lawler on July 30, 2010 7:36 PM | Permalink | Reply to this

Re: Ternary Factorization Systems

That’s a neat idea. I must admit it’s not immediately obvious to me how to extract a ternary factorization of a map from a 3-fold distributive law, but you sound fairly confident that they’ll turn out to be the same; have you worked it out?

Rosebrugh and Wood do give a generalization to non-strict factorizations, but it’s not entirely satisfying to me as presented. But it might be the best one can do, or maybe I’m just not looking at it in the right way.

Posted by: Mike Shulman on July 31, 2010 5:40 AM | Permalink | Reply to this

Re: Ternary Factorization Systems

I think a nicer way of doing it is indicated in Section 4 of Steve Lack’s “Composing PROPs”: strict distributive laws, but between profunctors between groupoids, rather than betweens spans between sets.

Posted by: Richard Garner on July 31, 2010 9:30 AM | Permalink | Reply to this

Re: Ternary Factorization Systems

Mike wrote:

you sound fairly confident that they’ll turn out to be the same; have you worked it out?

My confident demeanour might be inappropriate. I haven’t even begun to work it out.

Posted by: Tom Leinster on July 31, 2010 10:46 AM | Permalink | Reply to this

Re: Ternary Factorization Systems

Or perhaps a better answer is this: I wasn’t claiming that this way of defining kk-ary factorization system was, in the case k=3k = 3, equivalent to the definition of ternary factorization system that you gave (or rather, the strict version of it). I was just suggesting that it might be a reasonable definition of kk-ary factorization system.

Posted by: Tom Leinster on July 31, 2010 1:42 PM | Permalink | Reply to this

Re: Ternary Factorization Systems

Tom wrote:

“I wasn’t claiming that this way of defining k-ary factorization system was, in the case k=3, equivalent to the definition of ternary factorization system that you gave (or rather, the strict version of it).”

It sounds plausible to me. Suppose we have a 3-fold distributive law of monads A, B, C, so distributive laws A over B, B over C, A over C, satisfying Yang-Baxter. We certainly have induced monads BA, CB and CA.

We also get distributive laws A over CB and BA over C, both inducing the same monad CBA.

Now if we do this for monads in Span, it looks to me like a strict version of the ternary factorisation system Mike gave above, since we already know that each distributive law gives a strict binary factorisation system.

So we put (L 1,R 1)=(A,CB)(L_1,R_1) = (A,CB) and (L 2,R 2)=(BA,C)(L_2,R_2) = (BA,C) (or maybe with some left/right the other way round?) and we’ll get L 1L 2L_1&#8838;L_2 and R 2R 1R_2&#8838;R_1 as desired.

The composite monad CBA is formed in Span as a big pullback (three spans wide); the fact that it has the structure of a monad means that we have a category, each of whose morphisms can be uniquely expressed as one in C followed by one in B followed by one in A (or maybe the other order, depending on our conventions). This matches Mike’s Theorem 1 as L 2R 1L_2 &#8745; R_1 is B.

The version to give factorisation into k morphisms would then come from starting with what I called a “distributive series of k monads” T 1,,T kT_1, \ldots, T_k. There would be loads of factorisation systems floating around (on subcategories of the one you want), but the ones you’d use to define a k-ary strict factorisation system analogously to the above would be the following n-1 of them I suppose:

(T 1,T kT k1T 2)(T_1, T_k T_{k-1} \cdots T_2)

(T 2T 1,T kT k1T 3)(T_2 T_1,T_k T_{k-1} \cdots T_3)

\vdots

(T k1T 1,T k)(T_{k-1} \cdots T_1, T_k).

These all induce the same composite monad T kT k1T 1T_k T_{k-1} \cdots T_1. If we do it in Span this gives us a category with all morphisms expressed as a string of kk composable morphisms, one in each subclass T iT_i.

This is the longest and most mathematical comment I’ve ever made, so please don’t all tell me I’m stupid all at once.

Posted by: Eugenia Cheng on August 1, 2010 2:21 PM | Permalink | Reply to this

Re: Ternary Factorization Systems

That sounds reasonable! It would be great if someone could work out the details and write them down.

Posted by: Mike Shulman on August 2, 2010 6:14 AM | Permalink | Reply to this

Re: Ternary Factorization Systems

An arXiv posting today from Gabriella Böhm says that weak and non-strict factorization systems can be characterized using Street’s “weak distributive laws,” which satisfy the same multiplication axioms as ordinary distributive laws, but a weaker unit condition.

Posted by: Mike Shulman on September 6, 2010 4:40 PM | Permalink | Reply to this

Re: Ternary Factorization Systems

Double factorisation systems are defined in:

A. Pultr, W. Tholen
Free Quillen Factorization Systems
Georgian Math. J.9 (2002), No. 4, 807-820

Posted by: Richard Garner on July 31, 2010 1:22 AM | Permalink | Reply to this

Re: Ternary Factorization Systems

Beautiful! That has everything I wanted and more, at least in the case of ternary factorizations. Someone should write about it at the nLab.

It’s especially intriguing that the natural generalization of the construction of the free binary factorization system actually produces not just an arbitrary ternary factorization system, but one where the “weak equivalences” also satisfy the 2-out-of-3 property. I presume that you’ve thought about whether any of that theory can be generalized to algebraic weak factorization systems?

Posted by: Mike Shulman on July 31, 2010 5:36 AM | Permalink | Reply to this

Re: Ternary Factorization Systems

No, I haven’t really given it any thought actually—it’s a while since I looked at that paper…

Posted by: Richard Garner on July 31, 2010 9:33 AM | Permalink | Reply to this

Re: Ternary Factorization Systems

Re ternary factorisation systems

I studied ternary factorisation systems (and factorisation systems as commutation laws) with Joyal in 2003, but no publication ever came out of it.

Here is some input to the discussion, notably a notion of ambifibration, and some remarks on the importance of flatness when passing from strict to non-strict notions of factorisation system.

A naive ternary factorisation system on a category CC consists of three subcategories, C 1C_1, C 2C_2, C 3C_3 each containing all the isomorphisms, such that every arrow factors uniquely (up to unique comparison isos) into f 1f 2f 3f_1 f_2 f_3 with f iC if_i \in C_i.

Proposition: Such a naive factorisation system is functorial (in the sense of Korostenski-Tholen) iff it is split (in the sense described by Mike in the original post).

This result provides some justification that this notion is a reasonable notion of ternary factorisation system.

The motivation for studying ternary factorisation systems was our notion of ambifibration, which I think may be of interest to this thread. A (Grothendieck) fibration is an example of a factorisation system, namely (vertical,cartesian), and this factorisation system lies over the trivial factorisation system in the base (id,all). Similarly, an opfibration is a factorisation system (opcartesian,vertical) lying over the trivial factorisation (all,id). By definition, an ambifibration (relative to a factorisation system (A,B)(A,B) in the base CC) is a functor p:XCp: X \to C such that every arrow in AA has an opcartesian lift, and every arrow in BB has a cartesian lift.

It follows that the restriction of pp to AA is an opfibration, and that the restriction of pp to BB is a fibration. Let EE denote the opcartesian arrows for the first restriction, and let MM denote the cartesian arrows for the second restriction. Now it is not difficult to prove: (E,V,M)(E,V,M) is a ternary factorisation system. (Here VV denotes the category of vertical arrows for pp.) Conversely, given a ternary factorisation system X=(E,V,M)X = (E,V,M) and a functor to some category C=(A,B)C = (A,B) such that the restriction to L=(E,V)L = (E,V) is an opfibration over AA, and the restriction to R=(V,M)R = (V,M) is a fibration over BB, then the whole thing is an ambifibration.

I believe many of the ternary factorisation systems mentioned in this thread are in fact ambifibrations lying over some binary factorisation system.

(The reason for introducing the notion of ambifibration was that the ‘fat Delta’ is an ambifibration over Δ\Delta. The fat Delta (introduced in my paper Weak identity arrows in higher categories) is a version of Δ\Delta where the degeneracy maps are only ‘up to homotopy’ in some sense. More precisely, if you visualise the objects of Δ\Delta as columns of dots (and functions as noncrossing strings), then fat Delta has as objects columns of dots where adjacent dots may or may not have a linking line. The morphisms are noncrossing strings that are injective on dots. This means that instead of the basic degeneracy map in Δ\Delta that merges two dots into one dot, there is in the fat Delta only the up-to-homotopy version where two non-linked dots map to two linked dots. The projection to Δ\Delta contracts the links. The fat Delta has a canonical ternary factorisation system lying over the the epi-mono factorisation system in Δ\Delta. The middle class of arrows in the fat Delta are then the maps that lie over the identity maps in Δ\Delta, so they are the ‘equivalences’. Often the middle class in the ternary factorisation system coming from an ambifibration has the flavour of equivalence, and in particular it will always satisfy 3-for-2. The Gabriel-Zisman localisation of the fat Delta along those vertical map gives back Delta again. Toen conjectured that also the Dwyer-Kan localisation of the fat Delta with respect to the vertical maps is equivalent to Δ\Delta. This would provide some strong evidence for the correctness of the fat Delta as a combinatorial building block for a theory of higher categories with only weak identity arrows, which was my motivation for introducing it.)

Just as there is a canonical way of getting a factorisation system in the category of arrows of any category (cf. Korostenski-Tholen), there is a canonical way of getting an ambifibration over a factorisation system (A,B)(A,B), provided these conditions hold: the pullback of BB-arrows along AA-arrows are again in BB, and the pushout of AA-arrows along BB-arrows are again in AA. Under these conditions, the category of arrows is an ambifibration. (The fat Delta is a variation of this construction: it can be described as the subcategory of the category of arrows of Δ\Delta whose objects are the epis in Δ\Delta, and whose arrows are the monos in Arr(Δ)Arr(\Delta).)

Re synthetic factorisation systems

As Tom mentions, strict factorisation systems is the same thing as distributive laws on monads in SpanSpan. Here are some further remarks about that, also dating from discussions with Joyal in 2003 (we were unaware of the Rosebrugh-Wood paper).

Strict factorisation systems (on categories with object set SS) are the same thing as distributive laws between monads in SpanSpan based on the set SS (which we called commutation laws on monoids in the category of discrete endo-distributors over SS).

(With this viewpoint one can capture many examples that don’t a priori look like factorisation systems: for example, if given an SS-category and two subcategories AA and BB such that pullbacks of BB-arrows along AA-arrows exists and are again in BB, then this amounts to having a commutation law between AA and B opB^{op}.)

A strict factorisation system can always be saturated to a ortogonal factorisation system, simply by adding all the isomorphisms to each class. However, strict factorisation systems sometimes contain much more information. For example, the semidirect product of two groups is a nontrivial strict factorisation system, but its saturation is just the chaotic factorisation system!

Furthermore, there are intermediate notions, where the groupoid ABA \cap B lies in between id and iso. For example, Grothendieck fibrations are such: the intersection is the class of vertical isomorphisms.

All this can be captured in the setting of commutation laws. If (A,B)(A,B) is a non-strict factorisation system, meaning that the intersection J:=ABJ := A \cap B is bigger than SS but smaller than the groupoid of all isos, then AA and BB become JJ-algebras (in the sense of algebra, i.e. they receive a monoid map from JJ), and then we can consider the tensor product of JJ-algebras: it is just the coequaliser of the two maps AJBAB, A \otimes J \otimes B \stackrel{\to}{\to} A \otimes B, just like in algebra. The structure of a factorisation system amounts to a commutation law B JAA JBB \otimes_J A \to A \otimes_J B, and hence a monoid structure on the latter object, i.e. a category. Provided each JAJ \to A and JBJ \to B are flat, this category will be the original one. (Flatness is implied if just JAJ \to A and JBJ \to B are monomorphisms of monoids.) If JJ is the groupoid of all isos, then the tensor product says precisely that we can move isos from the left-hand factor over to the right-hand factor, just as we are used to do in a orthogonal factorisation system.

A ternary factorisation is indeed the same thing as three categories with the same set of objects, two commutation laws satisfying the Yang-Baxter identity — provided the pairwise intersections coincide at some groupoid JJ, and the three categories are flat over JJ.

Coming back to binary factorisation systems: without the flatness condition, as you can guess, some sort of derived tensor product should be used instead, requiring some higher-categorical setting. An important example of non-flatness is provided by the category of spans. Every span factors as one where the second leg is invertible followed by one where the first leg is invertible. The intersection is the class WW of all isomorphisms, but the two classes of functors are not flat over WW, as WW acts non-freely on the first class on the right, as well as non-freely on second class on the left.

This fact lies at the heart of the coherence problems for symmetric monoidal categories. Namely, certain spans do admit unique factorisation, and they are precisely the relations. (But the span composite of two relations is not in general a relation.) When selecting coherence diagrams for symmetric monoidal categories, not all diagrams that could commute just for their shape should actually be required to commute. Laplaza first identified those that should (or those that should not), and it was later clarified by Fiore, Hu, and Kriz. The diagrams required to commute are those that correspond to relations, while those corresponding to non-relation spans, i.e. those for which the factorisation is not unique, cannot be required to commute. In other words, the non-flatness accounts for the coherence problems.

(I read what I just wrote, and realise it is not very clear. To see the relationship, one needs first to notice that the category of finite sets and isomorphism classes of finite spans is the Lawvere theory for commutative monoids. To categorify this results, one runs into the problem that some objects, the spans that are not relations, have non-trivial automorphisms (or equivalently, non-unique factorisations). The easiest example is the span 121, 1 \leftarrow 2 \rightarrow 1, with the nontrivial involution of 22. This corresponds precisely to the first counter-example to naive coherence for symmetric monoidal categories, namely aaa \otimes a, which has the involution different from the identity. Only rigid spans (i.e. relations) should be used when ‘selecting Laplaza sets’ in the terminology of Fiore-Hu-Kriz.

The span explanation is due to Brun, Carlson, and Dundas, but I don’t think it has actually been proved that this explanation agrees with what Fiore-Hu-Kriz do, so take all this with a grain of salt!

If one just kills the auts, one gets only the degenerate symmetric monoidal categories (i.e. those equivalent to commutative monoids in Cat), as shown by Gould.

The result that spans form the Lawvere theory for commutative monoids has an interesting generalisation, attributed to Tambara (cf. [Gambino-Kock]). Namely, the category of finite sets and isomorphism classes of finite polynomial functors is the Lawvere theory for commutative semirings.

So now I succeeded in digressing into polynomial functors again, so I guess it is time to stop.

Cheers, Joachim.

Posted by: Joachim Kock on August 1, 2010 4:53 PM | Permalink | Reply to this

Re: Ternary Factorization Systems

Wow, very neat! This should all be written down somewhere, even (or especially) if not published.

I’m a little confused about flatness and the example of spans. First, I assume you mean the bicategory of spans, so that we’re talking about a bicategorical factorization system? Second, you said that JAJ\to A and JBJ\to B are flat if they are monomorphisms, which seems to me like it should always be the case if we define JJ to consist of “the isomorphisms” =AB= A\cap B, since then both J, A, and B are just subcategories on the ambient category. And it seems like this is what you’re doing in the case of spans—so how do things end up non-flat? Is it because you said “monomorphisms of monoids” rather than “monomorphisms of categories”?

Posted by: Mike Shulman on August 2, 2010 6:29 AM | Permalink | Reply to this

Re: Ternary Factorization Systems

Hi Mike,

thank you for your attentive reading — once again. There is indeed some nonsense in what I write :-(

I’m a little confused about flatness and the example of spans. First, I assume you mean the bicategory of spans, so that we’re talking about a bicategorical factorization system?

No, I was in fact speaking about plain 1-categories, but of course the reason it is an example of something that goes wrong is that it is a wrong 1-categorical viewpoint on something that is really 2-categorical! I should have explained this better. The bicategory of spans has a strict model: it is the category whose objects are slices of Set, and whose arrows are the ‘linear polynomial functors’, i.e. composites of pullbacks and lowershrieks (left adjoints to pullback). (I call it Span again). Consider the underlying 1-category of this 2-category and call it CC. It has two honest subcategories: the category LL of functors whose lowershriek part is invertible, and the category RR of functors whose pullback part is invertible. The intersection WW is the category of isomorphisms. Every arrow factors as an LL-map followed by an RR-map, but only up to a non-unique iso. So this is not a factorisation system. Now consider LL and RR as monoids and try to construct a commutation law (distributive law) RLLRR \otimes L \to L \otimes R. This is not possible, but we can form the tensor product over WW and construct a commutation law R WLL WRR \otimes_W L \to L \otimes_W R. This commutation law makes L WRL \otimes_W R into a monoid again, i.e. a category with the same objects. However, because of the lack of flatness, this category involves a lot of collapse, does not contain LL and RR as subcategories, and does not coincide with the original CC. In fact it is instead the category of isoclasses of spans, i.e. the category obtained from the 2-category of spans and isomorphisms of spans by collapsing all the 2-cells. In conclusion, we did get a category with a factorisation system, but the uniqueness in the factorisation was obtained by a collapse of the isos, and this new category does not contain any of the original LL, WW, and RR as subcategories. The derived tensor product that ought to be used should instead produce the 2-category of spans and invertible 2-cells of spans, and the result should be the bicategorical factorisation system you mention.

(Seeing now more clearly how unnatural all this looks, I think I would like to reformulate my statement ‘lack of flatness is at the heart of coherence problems’ to ‘existence of non-rigid spans is at the heart of coherence problems’. (It just so happens that the non-rigid spans are those that have non-unique factorisation.))

Second, you said that J \to A and J \to B are flat if they are monomorphisms, which seems to me like it should always be the case if we define J to consist of “the isomorphisms” = A \cap B, since then both J, A, and B are just subcategories on the ambient category. And it seems like this is what you’re doing in the case of spans—so how do things end up non-flat? Is it because you said “monomorphisms of monoids” rather than “monomorphisms of categories”?

I am sorry about that: it seems in fact to be nonsense what I wrote :-( What I possibly had in mind is that the map JA JBJ \to A \otimes_J B should be mono. This is a consequence of flatness and the requirement that JAJ \to A and JBJ \to B be monos (and as you point out, when we start with everything inside a category and take intersections, this is automatic). In fact the crucial thing seems to be that the two maps AJBABA \otimes J \otimes B \to A \otimes B are mono, at least jointly, to ensure that the quotient is nice and does not swallow too much.

Posted by: Joachim Kock on August 2, 2010 6:45 PM | Permalink | Reply to this

Re: Ternary Factorization Systems

Thanks, that makes some more sense. This strict model of Span that you have in mind… I guess its morphisms are functors F:S/xS/yF\colon S/x \to S/y such that there exists some span xfzgyx\overset{f}{\leftarrow} z \overset{g}{\to} y and a natural isomorphism Fg !f *F\cong g_! f^*, but the span and natural isomorphism are not part of the data? Now I guess one can show that a span is uniquely determined, up to isomorphism, by the linear polynomial functor it induces, so it makes sense to talk about ff or gg being invertible as a property of the functor FF, giving the classes LL and RR.

Then if W=LRW=L\cap R, it’ll be the class of functors induced by a span of isomorphisms. Maybe that’s what you meant by “WW is the category of isomorphisms,” but when I first read that it sounded like you were saying WW was the isomorphisms in your 1-category CC, which I don’t think is the case; the morphisms of WW should be the equivalences in Span, but they needn’t be isomorphisms in this strict model of Span.

existence of non-rigid spans is at the heart of coherence problems

Well, okay, as long as we can agree that coherence problems have many hearts. (-: I think there are other equally illuminating ways to describe coherence problems.

Posted by: Mike Shulman on August 3, 2010 6:03 AM | Permalink | Reply to this

Re: Ternary Factorization Systems

This strict model of Span that you have in mind… I guess its morphisms are functors F:S/xS/yF:S/x \to S/y such that there exists some span xfzgyx \stackrel f \leftarrow z \stackrel g \to y and a natural isomorphism Fg !f F \simeq g_! f^{\star}, but the span and natural isomorphism are not part of the data?

That’s right, cf. [Gambino-Kock] for the general case of polynomial functors.

Now I guess one can show that a span is uniquely determined, up to isomorphism, by the linear polynomial functor it induces, so it makes sense to talk about ff or gg being invertible as a property of the functor FF, giving the classes LL and RR.

Yes, again. Of course it would be clearer to give an intrinsic characterisation of each class. The left-hand class is easy, they are just the right adjoints. I am not completely sure about the right-hand class but perhaps something like local equivalences, i.e. functors all of whose slices are equivalences.

Then if W=LRW=L \cap R, it’ll be the class of functors induced by a span of isomorphisms. Maybe that’s what you meant by “WW is the category of isomorphisms,” but when I first read that it sounded like you were saying WW was the isomorphisms in your 1-category CC, which I don’t think is the case; the morphisms of WW should be the equivalences in Span, but they needn’t be isomorphisms in this strict model of Span.

Dang, you’re right! Actually this kills my example, because in everything I wrote it is assumed that JJ is a groupoid. Right, so the pullback along an isomorphism is not necessarily an isomorphism! Fair enough, and no problem, for all practical purposes. But quite a stroke to this perverse example I was describing without understanding it properly.

Thanks again, Mike!

So here is a

New attempt at saying something meaningful

Given a a factorisation system C=(L,R)C = (L,R) (which could be strict or saturated or anything in between), put W:=LRW := L \cap R. Then there is induced a commutation law R WLL WRR \otimes_W L \to L \otimes_W R.

The terminology ‘synthetic factorisation system’ is supposed to denote the opposite process: to construct a category (equipped with a factorisation system) out of two abstract categories (not a priori subcategories of any common bigger category):

So, conversely, given categories WLW \to L and WRW\to R with the same object set, a commutation law R WLL WRR \otimes_W L \to L \otimes_W R induces a factorisation system on the category C:=L WRC := L \otimes_W R provided

(i) WW is a groupoid

(ii) the structure maps WLW \to L and WRW \to R are monos, and

(iii) the actions LWLL \otimes W \to L and WRRW \otimes R \to R are jointly free (i.e. the two maps LWRLRL \otimes W \otimes R \to L \otimes R are jointly mono).

Example illustrating the need of the last condition: Suppose we want to glue together Set opSet^{op} and SetSet to form a category of spans. Naturally, we choose as gluing locus WW the groupoid of sets and bijections, which injects into both Set opSet^{op} and SetSet. We construct a commutation law Set WSet opSet op WSetSet \otimes_W Set^{op} \to Set^{op} \otimes_W Set by pullback. This is well-defined since the tensor product over W allows us to move the comparison maps between different pullback candidates from one side to the other. Hence we get a category structure on Set op WSetSet^{op} \otimes_W Set: it is the category of spans modulo isomorphism (in the bicategorical sense). However, since the action of WW on the right on Set op\Set^{op} and on the left on SetSet are not free actions, we do not get a factorisation system on Span/~. Indeed, although every span factors as a Set opSet^{op}-map (a span whose right-foot leg is an identity arrow) followed by a SetSet-map (a span whose left-foot leg is an identity), this factorisation is not unique: a counter example is 1211 \leftarrow 2 \rightarrow 1.

Am I getting hotter or cooler?

Cheers, Joachim.

Posted by: Joachim Kock on August 3, 2010 1:43 PM | Permalink | Reply to this

Re: Ternary Factorization Systems

I think this makes sense to me now! And of course, the need to go up a categorical level here when you have a non-free action is exactly what you would expect if you’re used to thinking about, say, homotopy quotients by group actions. Thanks for your perseverance in making this work; now I think it’s a nice example.

Posted by: Mike Shulman on August 4, 2010 2:07 AM | Permalink | Reply to this

Re: Ternary Factorization Systems

Regarding strict models of SpanSpan: this is an instance of Lack’s coherence theorem. We all know that every weak 2-category is equivalent to a strict one. Lack’s coherence theorem states that every naturally-arising weak 2-category is equivalent to a naturally-arising strict one.

Of course this is a joke… and I seem to remember that when Steve first told me about it, I racked my brains for exceptions and found some. But it’s interesting how true it is.

For example, the weak 2-category ModMod of small categories, bimodules and bimodule maps is equivalent to the strict 2-category ModMod' of presheaf categories, cocontinuous functors and natural transformations. The object C\mathbf{C} of ModMod corresponds to the object Set CSet^\mathbf{C} of ModMod'.

Since a bimodule between discrete categories is the same thing as a span between sets, this equivalence restricts to an equivalence between SpanSpan and the strict 2-category SpanSpan' of slices of SetSet, cocontinuous functors and natural transformations.

Posted by: Tom Leinster on August 3, 2010 10:22 PM | Permalink | Reply to this

Post a New Comment