Ternary Factorization Systems

July 24, 2010

Posted by Mike Shulman

$MathML-enabled post (click for more details).$

We’ve been having a bit of discussion on the nForum about ternary and higher-ary factorization systems in categories and higher categories. A $k$ -ary factorization system is supposed to give a way of factoring any morphism into a composite of $k$ 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 : A \to B$ factors as

A \to {im}_{2} (f) \to {im}_{1} (f) \to B

where ${im}_{1} (f) \to B$ is full and faithful, ${im}_{2} (f) \to {im}_{1} (f)$ is essentially surjective and faithful, and $A \to {im}_{2} (f)$ is essentially surjective and full. Similarly, we expect a functor between $n$ -categories to have a natural $(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!

$MathML-enabled post (click for more details).$

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)$ , such that $L$ is orthogonal to $R$ , and every morphism factors as an $L$ -map followed by an $R$ -map. The last condition is easy to generalize to a $k$ -ary factorization with $k$ classes of maps, but what is the right counterpart of orthogonality?

I think we get a very nice theory by looking at $k$ -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

first factor $f$ 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
first factor $f$ 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})$ and $(L_{2}, R_{2})$ such that $L_{1} \subseteq L_{2}$ (and hence $R_{2} \subseteq R_{1}$ ). The above situation generalizes as follows.

Theorem 1: Given a ternary factorization system as above, any morphism $f$ factors as

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 $f$ obtained as above, by

First factoring $f$ into an $L_{1}$ -map followed by an $R_{1}$ -map, then factoring the $R_{1}$ -part into an $L_{2}$ -map followed by an $R_{2}$ -map; and
First factoring $f$ into an $L_{2}$ -map followed by an $R_{2}$ -map, then factoring the $L_{2}$ -part into an $L_{1}$ -map followed by an $R_{1}$ -map.

Note that both start with an $L_{1}$ map and end with an $R_{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_{2}$ and the second produces a middle map which is in $R_{1}$ , this middle map must in fact be in $L_{2} \cap R_{1}$ . Finally, any other such ternary factorization of $f$ induces an $(L_{1}, R_{1})$ and $(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 $k$ -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} =$ quotient maps, $R_{1} =$ injective continuous maps, $L_{2} =$ surjective continuous functions, and $R_{2} =$ subspace embeddings. Here $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_{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_{1}$ , $R_{1}$ , $L_{2}$ , $R_{2}$ , and $L_{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_{2} \cap R_{1})$ -part is an isomorphism, or equivalently those that can be factored as an $L_{1}$ -map followed by an $R_{2}$ -map. Thus, let’s call this class $R_{2} L_{1}$ .

It’s not hard to see that this gives the right answer in $Cat$ : 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_{2} \cap R_{2} L_{1}$ and $R_{2} = R_{1} \cap R_{2} L_{1}$ .

Proof: In both cases $\subseteq$ is obvious. Conversely, if $f \in L_{2} \cap R_{2} L_{1}$ , say $f = m e$ for $m \in R_{2}$ and $e \in L_{1}$ , then orthogonality in the square

\begin{matrix} a & \overset{e}{\to} & c \\ ^{f} ↓ & ↓^{m} \\ b & \underset{id}{\to} & b \end{matrix}

exhibits $f$ as a retract of $e$ in $Arr (C)$ , whence $f \in L_{1}$ since $L_{1}$ is closed under retracts.

Can this also be generalized to $k$ -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})$ and $(L_{2}, R_{2})$ with $L_{1} \subseteq L_{2}$ .

However, this is precisely the sort of WFS data which underlies a model category, where $L_{1} =$ acyclic cofibrations, $L_{2} =$ cofibrations, $R_{1} =$ fibrations, and $R_{2} =$ acyclic fibrations. What are the two other classes of maps in this case? Well, $L_{2} \cap R_{1} =$ maps that are both cofibrations and fibrations; that doesn’t seem very interesting. But $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_{2} L_{1}$ as the maps whose $L_{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

$MathML-enabled post (click for more details).$

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

The important thing about that is that it works even when $k$ is infinite. The generalisation to $k > 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 $α$ is Mike's $k + 1$ , and while Mike's $k$ -ary factorisation system has $k - 1$ (hence $α - 2$ ) binary factorisation systems, my $α$ -stage factorisation system has $α$ (hence $k + 1$ ) binary factorisation systems. In this case, my two extra factorisation systems are trivial ones of the form $(all, iso)$ and $(iso, all)$ . (In general, these appear whenever $α$ is bounded as a poset.)

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

Re: Ternary factorization systems

$MathML-enabled post (click for more details).$

Actually, I think that my definition is not complete. Surely there is a missing condition when $α = ω + ω^{op}$ , for example? However, I think that it should be correct whenever $α$ is either an ordinal or the opposite of an ordinal, along with some other situations such as $α = ω^{op} + ω$ (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

$MathML-enabled post (click for more details).$

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, triv - fib)$ binary system of model categories and $(triv - cof, fib)$ -sytem each by a ternary system leads to some structure on a 2-category that can present $(∞, 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

$MathML-enabled post (click for more details).$

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 $sSet$ , for simplicity, then the basic left factorization is

\partial Δ^{1} ↪ Δ^{1} \overset{≃}{\to} Δ^{0} .

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

X ∐ X ↪ X \cdot Δ^{1} \overset{≃}{\to} X

which defines left homotopies between 1-morphisms

\begin{matrix} X \\ ↓ & ↘ \\ X \cdot Δ^{1} & \to & Y \\ ↑ & ↗ \\ X \end{matrix} .

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

\partial Δ^{1} \to Δ^{1} \to Δ^{0}

now equivalently as

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

where $G^{n}$ is the $n$ -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^{0} ∐ G^{0} ↪ \partial G^{2} ↪ G^{2} \overset{≃}{\to} G^{1} .

X \cdot G^{1} \to Y

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

\begin{matrix} X \cdot G^{1} \\ ↓ & ↘ \\ X \cdot G^{2} & \to & Y \\ ↑ & ↗ \\ X \cdot G^{1} \end{matrix} .

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

\begin{matrix} X \cdot G^{1} \\ ↗ ↗ & ↓ & ↘ \\ X & X \cdot G^{2} & \to & Y \\ ↘ ↘ & ↑ & ↗ \\ X \cdot G^{1} \end{matrix} .

Some kind of argument like this might motivate ternary factorization systems for “model 2-categories”. And then $(k + 1)$ -ary ones for “model $k$ -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

$MathML-enabled post (click for more details).$

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

$MathML-enabled post (click for more details).$

Miles Gould and I came across $k$ -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 $Cat$ — bijective on objects/full and faithful — is really a factorization system on the category $Gph$ of directed graphs, lifted to $Cat$ . There’s an easy theorem:

Theorem Let $(E, M)$ be a factorization system on a category $C$ . Let $T$ be a monad on $C$ , and write $U : C^{T} \to C$ for the forgetful functor. Define $\bar{E} = {f in C^{T} : U f \in E}, \bar{M} = {f in C^{T} : U f \in M} .$ Suppose that $T$ preserves $E$ -arrows. Then $(\bar{E}, \bar{M})$ is a factorization system on $C^{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 $T$ be the free category monad on $Gph$ . Take the BOFF factorization system on $Gph$ . The image under $T$ of a bijective-on-objects map of graphs is again bijective on objects, so there is an induced factorization system on ${Gph}^{T} = Cat$ — namely, BOFF.

Now, there is a similar BOFF-like $(n + 1)$ -ary factorization system on the category $n - Gph$ of $n$ -graphs ( $n$ -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 $n$ -category monad $T$ on $n - Gph$ to give the $(n + 1)$ -factorization system on $n - 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

$MathML-enabled post (click for more details).$

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 $k$ -ary factorization system is just $k - 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 $k$ -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

$MathML-enabled post (click for more details).$

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 $k$ -fold factorization system should therefore be defined as a $k$ -fold distributive law. This means a sequence of $k$ monads on the same object of the bicategory of spans — that is, a sequence of $k$ categories with the same object-set — together with a distributive law of the $i$ th over the $j$ th whenever $i < j$ , all subject to a Yang–Baxter equation for each $i < j < k$ .

The definition is, of course, set up so that the usual facts about distributive laws extend to the $k$ -fold setting. In particular, a $k$ -fold distributive law tells you how to glue together those $k$ categories (monads in Span) to obtain a single category (monad in Span). This is the category on which the $k$ -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

$MathML-enabled post (click for more details).$

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

$MathML-enabled post (click for more details).$

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

$MathML-enabled post (click for more details).$

Or perhaps a better answer is this: 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). I was just suggesting that it might be a reasonable definition of $k$ -ary factorization system.

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

Re: Ternary Factorization Systems

$MathML-enabled post (click for more details).$

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)$ and $(L_{2}, R_{2}) = (BA, C)$ (or maybe with some left/right the other way round?) and we’ll get $L_{1} \subseteq L_{2}$ and $R_{2} \subseteq 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_{2} \cap 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}, \dots, 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_{k} T_{k - 1} \dots T_{2})$

$(T_{2} T_{1}, T_{k} T_{k - 1} \dots T_{3})$

$⋮$

$(T_{k - 1} \dots T_{1}, T_{k})$ .

These all induce the same composite monad $T_{k} T_{k - 1} \dots T_{1}$ . If we do it in Span this gives us a category with all morphisms expressed as a string of $k$ composable morphisms, one in each subclass $T_{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

$MathML-enabled post (click for more details).$

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

$MathML-enabled post (click for more details).$

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

$MathML-enabled post (click for more details).$

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

$MathML-enabled post (click for more details).$

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 $C$ consists of three subcategories, $C_{1}$ , $C_{2}$ , $C_{3}$ each containing all the isomorphisms, such that every arrow factors uniquely (up to unique comparison isos) into $f_{1} f_{2} f_{3}$ with $f_{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)$ in the base $C$ ) is a functor $p : X \to C$ such that every arrow in $A$ has an opcartesian lift, and every arrow in $B$ has a cartesian lift.

It follows that the restriction of $p$ to $A$ is an opfibration, and that the restriction of $p$ to $B$ is a fibration. Let $E$ denote the opcartesian arrows for the first restriction, and let $M$ denote the cartesian arrows for the second restriction. Now it is not difficult to prove: $(E, V, M)$ is a ternary factorisation system. (Here $V$ denotes the category of vertical arrows for $p$ .) Conversely, given a ternary factorisation system $X = (E, V, M)$ and a functor to some category $C = (A, B)$ such that the restriction to $L = (E, V)$ is an opfibration over $A$ , and the restriction to $R = (V, M)$ is a fibration over $B$ , 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 $Δ$ . The fat Delta (introduced in my paper Weak identity arrows in higher categories) is a version of $Δ$ where the degeneracy maps are only ‘up to homotopy’ in some sense. More precisely, if you visualise the objects of $Δ$ 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 $Δ$ 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 $Δ$ contracts the links. The fat Delta has a canonical ternary factorisation system lying over the the epi-mono factorisation system in $Δ$ . The middle class of arrows in the fat Delta are then the maps that lie over the identity maps in $Δ$ , 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 $Δ$ . 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)$ , provided these conditions hold: the pullback of $B$ -arrows along $A$ -arrows are again in $B$ , and the pushout of $A$ -arrows along $B$ -arrows are again in $A$ . 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 $Δ$ whose objects are the epis in $Δ$ , and whose arrows are the monos in $Arr (Δ)$ .)

Re synthetic factorisation systems

As Tom mentions, strict factorisation systems is the same thing as distributive laws on monads in $Span$ . 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 $S$ ) are the same thing as distributive laws between monads in $Span$ based on the set $S$ (which we called commutation laws on monoids in the category of discrete endo-distributors over $S$ ).

(With this viewpoint one can capture many examples that don’t a priori look like factorisation systems: for example, if given an $S$ -category and two subcategories $A$ and $B$ such that pullbacks of $B$ -arrows along $A$ -arrows exists and are again in $B$ , then this amounts to having a commutation law between $A$ and $B^{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 $A \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)$ is a non-strict factorisation system, meaning that the intersection $J : = A \cap B$ is bigger than $S$ but smaller than the groupoid of all isos, then $A$ and $B$ become $J$ -algebras (in the sense of algebra, i.e. they receive a monoid map from $J$ ), and then we can consider the tensor product of $J$ -algebras: it is just the coequaliser of the two maps $A \otimes J \otimes B \vec{\to} A \otimes B,$ just like in algebra. The structure of a factorisation system amounts to a commutation law $B \otimes_{J} A \to A \otimes_{J} B$ , and hence a monoid structure on the latter object, i.e. a category. Provided each $J \to A$ and $J \to B$ are flat, this category will be the original one. (Flatness is implied if just $J \to A$ and $J \to B$ are monomorphisms of monoids.) If $J$ 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 $J$ , and the three categories are flat over $J$ .

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 $W$ of all isomorphisms, but the two classes of functors are not flat over $W$ , as $W$ 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 $1 \leftarrow 2 \to 1,$ with the nontrivial involution of $2$ . This corresponds precisely to the first counter-example to naive coherence for symmetric monoidal categories, namely $a \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

$MathML-enabled post (click for more details).$

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 $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”?

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

Re: Ternary Factorization Systems

$MathML-enabled post (click for more details).$

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 $C$ . It has two honest subcategories: the category $L$ of functors whose lowershriek part is invertible, and the category $R$ of functors whose pullback part is invertible. The intersection $W$ is the category of isomorphisms. Every arrow factors as an $L$ -map followed by an $R$ -map, but only up to a non-unique iso. So this is not a factorisation system. Now consider $L$ and $R$ as monoids and try to construct a commutation law (distributive law) $R \otimes L \to L \otimes R$ . This is not possible, but we can form the tensor product over $W$ and construct a commutation law $R \otimes_{W} L \to L \otimes_{W} R$ . This commutation law makes $L \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 $L$ and $R$ as subcategories, and does not coincide with the original $C$ . 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 $L$ , $W$ , and $R$ 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 $J \to A \otimes_{J} B$ should be mono. This is a consequence of flatness and the requirement that $J \to A$ and $J \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 $A \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

$MathML-enabled post (click for more details).$

Thanks, that makes some more sense. This strict model of Span that you have in mind… I guess its morphisms are functors $F : S / x \to S / y$ such that there exists some span $x \overset{f}{\leftarrow} z \overset{g}{\to} y$ and a natural isomorphism $F ≅ 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 $f$ or $g$ being invertible as a property of the functor $F$ , giving the classes $L$ and $R$ .

Then if $W = L \cap R$ , it’ll be the class of functors induced by a span of isomorphisms. Maybe that’s what you meant by “ $W$ is the category of isomorphisms,” but when I first read that it sounded like you were saying $W$ was the isomorphisms in your 1-category $C$ , which I don’t think is the case; the morphisms of $W$ 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

$MathML-enabled post (click for more details).$

This strict model of Span that you have in mind… I guess its morphisms are functors $F : S / x \to S / y$ such that there exists some span $x \overset{f}{\leftarrow} z \overset{g}{\to} y$ and a natural isomorphism $F ≃ g_{!} f^{⋆}$ , 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 $f$ or $g$ being invertible as a property of the functor $F$ , giving the classes $L$ and $R$ .

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 = L \cap R$ , it’ll be the class of functors induced by a span of isomorphisms. Maybe that’s what you meant by “ $W$ is the category of isomorphisms,” but when I first read that it sounded like you were saying $W$ was the isomorphisms in your 1-category $C$ , which I don’t think is the case; the morphisms of $W$ 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 $J$ 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)$ (which could be strict or saturated or anything in between), put $W : = L \cap R$ . Then there is induced a commutation law $R \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 $W \to L$ and $W \to R$ with the same object set, a commutation law $R \otimes_{W} L \to L \otimes_{W} R$ induces a factorisation system on the category $C : = L \otimes_{W} R$ provided

(i) $W$ is a groupoid

(ii) the structure maps $W \to L$ and $W \to R$ are monos, and

(iii) the actions $L \otimes W \to L$ and $W \otimes R \to R$ are jointly free (i.e. the two maps $L \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}^{op}$ and $Set$ to form a category of spans. Naturally, we choose as gluing locus $W$ the groupoid of sets and bijections, which injects into both ${Set}^{op}$ and $Set$ . We construct a commutation law $Set \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} \otimes_{W} Set$ : it is the category of spans modulo isomorphism (in the bicategorical sense). However, since the action of $W$ on the right on ${Set}^{op}$ and on the left on $Set$ are not free actions, we do not get a factorisation system on Span/~. Indeed, although every span factors as a ${Set}^{op}$ -map (a span whose right-foot leg is an identity arrow) followed by a $Set$ -map (a span whose left-foot leg is an identity), this factorisation is not unique: a counter example is $1 \leftarrow 2 \to 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

$MathML-enabled post (click for more details).$

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

$MathML-enabled post (click for more details).$

Regarding strict models of $Span$ : 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 $Mod$ of small categories, bimodules and bimodule maps is equivalent to the strict 2-category $Mod'$ of presheaf categories, cocontinuous functors and natural transformations. The object $C$ of $Mod$ corresponds to the object ${Set}^{C}$ of $Mod'$ .

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

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

The n-Category Café

Skip to the Main Content

July 24, 2010