# Practical Foundations of Mathematics

## 5.7  Factorisation Systems

Lattice theory could handle quotients (or the congruences defining them) and subalgebras separately, but things became difficult when both were needed at the same time. Several standard results with non-standardised names like ``second isomorphism theorem'' were formulated that link subgroups to normal subgroups and subrings to ideals. Some of these hold for general algebras, whilst others need the congruence lattices to be modular (Exercise  3.24).

It was Emmy Noether who shifted the emphasis from subalgebras and congruences to homomorphisms. Including both in the same structure shows us the universal property that distinguishes and re-unites them. The result also explains the existential quantifier, so often obscured by lattice-theoretic methods, as we shall see in Sections 5.8 and 9.3.

DEFINITION 5.7.1 We say that two maps e:X® A and m:B® Q in S are orthogonal and write  e^m if, for any two maps f and z such that the square commutes, there is a unique morphism p:A® B making the two triangles commute:

omitted diagram environment

For any classes of maps E,M Ì S, we write (as in Proposition 3.8.14)

omitted eqnarray* environment

If E = \orthl M and M = \orthr E, we call them a prefactorisation system.

For technical reasons it is also useful to say that `` e^m with respect to z'' if the fill-in property above holds for all f but just this particular z.

DEFINITION 5.7.2 A factorisation system [FK72] on a category S is a pair of classes of morphisms (E,M) of S such that

(a)
the classes E and M each contain all isomorphisms , and are closed under composition on either side with isomorphisms (we shall find that they are non-full replete subcategories),

(b)
every morphism f:X® Q of S can be expressed as f = e;m with e Î E and m Î M, and

(c)
e^m for every e Î E and m Î M.

If the pullback of any composite e;m against any map u:G® Q exists, and the parts lie in E and M respectively, then we call (E,M) a stable factorisation system, cf stable coproducts in Section  5.5.

omitted diagram environment

In Set, image factorisation is stable: this is necessary in Lemma 5.8.6 to make relational composition associative, and in Theorem 9.3.11 for the existential quantifier to be invariant under substitution. The only pullback- stability properties that factorisation systems in general have are Lemmas  5.7.6(f) and 5.7.10. Although the image factorisation is the most familiar and accounts for the notation, there are other important examples in topology, categorical logic and domain theory. Exercise 9.5 describes one that is related to virtual objects (Remark 5.3.2) .

Image factorisation   First we shall look at the motivating examples, so let S be a category that has kernel pairs and their coequalisers.

LEMMA 5.7.3 If e is regular epi and m mono then e^m. Conversely, if m satisfies e^m for every regular epi e then m is mono.

PROOF: Given a coequaliser and a mono in a commutative square as shown, the composites K\rightrightarrows X® B\hookrightarrow Q are equal; hence so are those K® B and by the universal property there is a unique fill-in.

omitted diagram environment

Conversely, apply orthogonality to the square with id:X® B; the diagonal fill-in shows that e is invertible. []

So with M and E the classes of monos (inclusions) and regular epis (quotients or surjections), we have \orthr E = M in any category which has kernels and quotients.

LEMMA 5.7.4 If the class of regular epis is closed under composition, then together with the class of monos it forms a factorisation system.

omitted diagram environment

PROOF: To factorise f:X® Y, let q:X\twoheadrightarrow Q be the coequaliser of the kernel pair K\rightrightarrows X of f; by Lemma  5.6.6(b) this is also the kernel pair of q. We must show that Q\hookrightarrow Y, so form its kernel pair L\rightrightarrows Q and let P be the coequaliser. The kernel pair of the composite X\twoheadrightarrow Q\twoheadrightarrow P is sandwiched (as a subobject of XxX) between those of X® Y and X® Q, which are both K. By hypothesis X\twoheadrightarrow Q\twoheadrightarrow P is regular epi, so it is the quotient of its kernel pair K\rightrightarrows X. But X\twoheadrightarrow Q was already the quotient of this pair, so L º Q º P. By Proposition 5.2.2(a), X\twoheadrightarrow Q\hookrightarrow Y. []

We would like to say that whenever the relevant finite limits and colimits exist, so does the image factorisation into regular epis and monos, and also dually the co-image factorisation into epis and regular monos. Unfortunately this is not so in general, but it is when the class of regular epis is closed under pullback (Proposition  5.8.3). In any case we call \orthl M-maps covers.

EXAMPLES 5.7.6

(a)
In a preorder all morphisms are both epi and mono, but only the isomorphisms are regular. (Example 5.7.9 nevertheless gives a non-trivial prefactorisation system in a poset.)

(b)
If, as in Set by Corollary  5.2.7, all monos are regular, then the dual of this lemma shows that epis and monos form a factorisation system. From Lemma 5.7.6(a) it follows that all epis are regular.

(c)
A homomorphism of algebras for a single-sorted finitary algebraic theory L is regular epi in the category Mod (L) iff it is surjective on its carriers, and mono iff it is injective (Exercise 5.38). These classes form a factorisation system.

(d)
In CMon regular monos do not compose. Consider the submonoids U = 3,5 and V = 3,5,7 of N; the inclusions U\hookrightarrow V and V\hookrightarrow N are regular monos but their composite is not, because if f,g:N\rightrightarrows Q agree at 3 and 5 then (as 2+5 = 2+3+2 = 5+2) they do at 7 too.

(e)
Although any field homomorphism is mono (Example  5.1.5(f)), it is regular iff it is a separable extension. There are non-trivial epis, namely totally inseparable extensions, such as K = F(p)[x]\hookrightarrow K[pÖ{x} ] ( cf Example 3.8.15(j), and see [Coh77, Theorem 6.4.4]).

(f)
In Sp, continuous functions are epi or mono according as they are surjective or injective on points, but are regular iff the topologies are the quotient or subspace ones. Both factorisations arise.

(g)
Let E be the class of full functors which are bijective on objects, and M the class of faithful functors.

(h)

Instead of allowing all subsets to be in M, we may restrict to those that are closed in some sense (Section 3.7).

(i)
In Sp, let M be the inclusions of closed sets in the topological sense. Then E is composed of the continuous functions with dense image.

(j)
In Pos, let M be the inclusions of lower sets and E be the class of cofinal maps (Proposition  3.2.10).

Properties of factorisation systems   Proposition 5.2.2 showed that the class of regular monos has weaker cancellation properties than that of all monos. Although the diagonal map p is determined in both cases by just one triangle, even this property is not typical. The other closure conditions satisfied by epis and monos do hold for arbitrary factorisation systems, but to show this we must study orthogonality more closely.

LEMMA 5.7.7

(a)
M Ì \orthr EÛ E Ì \orthl M, ie E® \orthr E and M® \orthl M form a Galois connection (Definition 3.6.1(b)) between classes of morphisms.

(b)
If i is invertible then e^i for any  e Î E, so \orthr E contains all of the isomorphisms, as does \orthl M (they are replete, Definition 4.4.8(d)).

(c)
If i^i then i is invertible, so MÇ\orthl M and EÇ\orthr E contain only isomorphisms.

(d)
If e^\m1 and e^\m2 then e^(\m2;\m1), so \orthr E is closed under composition, and likewise \orthl M.

(e)
If e^\ and e^(m ;\) then e^m, cf Proposition  5.2.2(h).

(f)
If e^m, and

\ = u*m is a pullback of m against any map u, then e ^\, cf Remark 5.2.3.

(g)
The ^ relation is preserved and reflected by full and faithful functors.

Similarly \orthl M is a subcategory closed under pushouts. 1 (#1)

omitted diagram environment

PROOF: The relation e^m defines a Galois connection by Proposition 3.8.14; most of the rest is shown in the diagrams.

(a)
If e;p = f and p;\m2;\m1 = z then p;\m2 = \Polly1 and p = \Polly2 since the mediators (p, \Polly1, \Polly2) are required to be unique.

(b)
Any fill-in for the left-hand trapezium serves for the rectangle ( p), but z and p;m both serve as the fill-in for the right-hand trapezium.

(c)
The fill-in for the rectangle gives one for the upper square by pullback and conversely by composition. []

PROPOSITION 5.7.8 Any factorisation system is also a prefactorisation system, so its two classes are closed under the above properties.

PROOF: It only remains to show that \orthr E Ì M. Using the factorisation property, suppose that (e;m) Î \orthr E with e Î E and m Î M. Then in particular e^(e;m) and e^m, so e^e is invertible using Lemmas 5.7.6(e) and (c). By repleteness, (e;m) Î M. Similarly \orthl M Ì E. []

Finding factorisations   Given an arbitrary prefactorisation system (E,M), we can now try to factorise S-morphisms f:X® Y as f = e;m with e Î E = \orthl M and m Î M = \orthr E. Any M- or E- morphism we can find that factors appropriately into f will contribute to this.

LEMMA 5.7.9 M is closed under wide pullbacks (Example  7.3.2(h)), ie arbitrary intersections in the case of monos. That is, for any wide pullback diagram in \orthr E , if the limit exists in S then its limiting cone lies in M, as does the mediator for any cone of M-maps. []

Similar results hold for wide pushouts in E. We have to impose algebraic and size conditions to ensure that the limit for M and colimit for E exist, but they may still fail to meet in the middle.

EXAMPLE 5.7.10 Here is a prefactorisation system in a poset.

omitted diagram environment

The classes E and M consist of the marked arrows, together with all of the identities and a single composite. The wide pullback of the M-maps into any object exists, as does the wide pushout of the E -maps out, but the unmarked broken arrow does not factorise. []

The problem is that the map cannot be in E because there are distant M-maps to which it is not orthogonal, but parallel translation using pullback which might bring it into M is not available.

LEMMA 5.7.11 Suppose that the pullback of any M-map against any S-map exists (and so is in M). Then to show e Î \orthl M it suffices to test orthogonality with respect to z = id, ie

if e = f;m with m Î M then \$! pp;m = idÙe ;p = f.

If all M-maps are mono then this condition makes m invertible.

PROOF: Similar to Lemma 5.7.6(f) with z = id. []

We need a solution-set condition such as that for the General Adjoint Functor Theorem 7.3.12 to show that any prefactorisation system with sufficient pullbacks is a factorisation system (Exercise  7.34), so we shall end this section with a special case.

PROPOSITION 5.7.12 Let S be a category such that there is a functor Sub:Sop® CSLat. Explicitly, S is well powered (Remark 5.2.5) and has arbitrary intersections of subobjects and inverse images, ie pullbacks of them along S-maps. For example S may be Set, Sp or any category of algebras. Then any prefactorisation system (E,M) which is such that all M-maps are mono is a factorisation system.

PROOF: The factorisation of f:X® Q is e;m where m:A\hookrightarrow Q is the intersection of the M-subobjects B\hookrightarrow Q through which f factors (using Theorem 3.6.9). Then e Î E by Lemma 5.7.10. []