Theory and Applications of Categories, Vol. 5, No. 11, 1999, pp. 266–280.

GENERALIZED CONGRUENCES — EPIMORPHISMS IN Cat

MAREK A. BEDNARCZYK ANDRZEJ M. BORZYSZKOWSKI WIESLAW PAWLOWSKI

Transmitted by Michael Barr

ABSTRACT. The paper generalizes the notion of a congruence on a category and pursues some of its applications. In particular, generalized congruences are used to provide a concrete construction of coequalizers in Cat. Extremal, regular and various other classes of epimorphic functors are characterized and inter-related.

1. Introduction

The results presented here hinge on a construction that leads to a generalization of the notion of a congruence on a category. According to the usual definition, (cf. e.g. [3, 6]), a congruence on a category is an equivalence relation on morphisms. However, it allows only morphisms from the same homset to be related. Such a notion is rather weak. Our programme here is to define generalized congruences so that they capture the essence of functor’s operation on its domain in the way homomorphisms are characterized by congruences in Algebra.

In section 3 this programme is initiated. We show that every functor induces a generalized congruence. Conversely, each generalized congruence is induced by an appropriately defined quotient functor. Then, the generalized congruence induced by the quotient functor coincides with the original generalized congruence.

Moving from congruences to generalized congruences bears a price — instead of equivalences on morphisms one has to consider partial equivalences on non-empty sequences of morphisms.

Generalized congruences which are fully determined by equivalences on morphisms are called regular. Thus, the congruences considered in the literature until now give rise to a subclass of regular congruences.

Section 4 contains the main result of the paper, the one which motivated our study. Namely, we show that coequalizers in Cat, the category of small categories, are exactly those extremal epimorphisms which induce regular congruences.

Partially supported by LoSSeD workpackage within the CRIT-2 project funded by ESPRIT and INCO programmes, and by the State Committee for Scientific Research grant 8 T11C 037 16.

Received by the editors 1998 October 16 and, in revised form, 1999 November 17.

Published on 1999 December 6.

1991 Mathematics Subject Classification: 18A05, 18A20, 18A30, 18A32, 18B99.

Key words and phrases: congruence, epimorphic functor, coequalizer, category of small categories.

\begin{matrix}c \\ ◯ \end{matrix} Marek A. Bednarczyk Andrzej M. Borzyszkowski Wieslaw Pawlowski 1999. Permission to copy for private use granted.

Extremal and regular epimorphisms are characterized in section 3 and section 4, respectively. In section 5 several other classes of epimorphisms in Cat are also studied and related to each other.

From another perspective, as a by-product, this paper offers an elementary characterization of colimits in Cat. The construction of coproducts in Cat is elementary. Hence, a concrete construction of coequalizers presented in section 4 does the job. Yet, despite the fact that cocompleteness of Cat is well-known, most authors do not provide a direct and elementary proof of the fact (cf. e.g. [1, 4, 6, 7]). The only place we have found where an elementary construction of co-equalizers in Cat is presented is [5]. There, a two stage construction is presented as a digression in the section on categories of fractions. In comparison, generalized congruences can be seen as a way of simplifying Borceux’s construction. Their extra potential, e.g., to characterize the regular epimorphisms, comes as an additional bonus.

Acknowledgments: Remarks of Michael Barr and Marcelo Fiore prompted our investigations. Only after this work was accomplished Gavin Wraith directed our attention to categories of fractions. Special thanks to Michael Barr and Andrzej Tarlecki for their comments and support throughout.

2. Preliminaries

We study Cat — the category of all small categories. Cat is the only non-small category considered in the paper. Hence, when we say “category” we mean “small category”. Categories in Cat are ranged over by A, B, etc., while functors are ranged over by F, G, and so on. All the functors appearing in the paper are morphisms of Cat, and hence are also small.

The sets of arrows and objects of a category A are denoted Mor_{A} and Ob_{A}, and ranged over by f, g, h, and a, b, c, respectively. The domain and codomain of an arrow f is denoted dom(f) and cod(f), respectively. Given arrows f and g such that cod(f) = dom(g), their composition is denoted diagrammatically as f; g. The same notation is used for composition of functors in Cat.

Let F : A → B be a functor.

Usually, the images of objects and morphisms of A in B via F, denoted F (A), do not form a subcategory of B, cf. example 3.8. There is always, however, the least subcategory of B which contains F (A). This subcategory, denoted Im F, is called the image of A in B via F. Clearly, Ob_{Im F} = F (Ob_{A}) while Mor_{Im F} consists of all compositions of morphisms from F (Mor_{A}) possible in B. A functor satisfying F (A) = B is called surjection.

It is easy to show that F is an epimorphism whenever its image spans its codomain, viz., Im F = B. As a consequence a corestriction |F | : A → Im F of F is an epimorphism. The corestriction is defined by |F |(a) ˆ= F (a) and |F |(f) ˆ= F (f).

Not all epimorphisms, however, span their codomains. For example, consider an embedding of a category with two objects and one non-identity arrow f between them, into the same category augmented with a formal inverse of f. This idea generalizes to a well-known example of the injection of the additive monoid of natural numbers ℕ (qua category) into the additive monoid ℤ of integers, (cf. e.g. [4]).

3. Functors versus generalized congruences

This section starts with the notion of a generalized congruence induced by a functor. Then, we introduce the notion of a generalized congruence in an axiomatic manner. Generalized congruences give rise to quotient categories and quotient functors. The latter induce the original, underlying congruence, thus closing the circle.

3.1. Generalized congruences induced by functors. According to the standard definition, (cf. e.g. [3, 6], or [4, 7]—for a slightly different but equivalent formulation), a congruence on a category A is an equivalence relation ∼ on Mor_{A} which satisfies the following two conditions:

• f ∼ f′ implies dom(f) = dom(f′) and cod(f) = cod(f′), and

• f ∼ f′ and g ∼ g′ and cod(f) = dom(g) implies f; g ∼ f′; g′.

For our programme to characterize functors by means of congruences to work it is necessary that congruences capture the functor’s ability to identify objects. Since this is forbidden by the first condition above, the notion of congruence must be refined.

Let A be a category, and let Mor_{A}^{+}, ranged over by ϕ, ψ, χ, etc., be the set of all non-empty finite sequences of morphisms of A.

3.2. Definition. Let F : A → B be a functor. The generalized congruence induced by F on A, denoted ≃_{F}, is an equivalence relation on objects of A, and a partial equivalence relation on non-empty sequences of morphisms of A defined as follows.

a ≃_{F} a′ iff F (a) = F (a′)
ϕ ≃_{F} ψ iff F (ϕ) = F (ψ), i.e., F (ϕ) and F (ψ) are both defined and equal

where F (f_{1} … f_{n}) ˆ= F (f_{1}); …;F (f_{n}), provided the latter composition is defined in B.

The following characterization of the domain of ≃_{F} is immediate. Let ϕ ˆ= (f_{1} … f_{n}), n ≥ 1. Then the following holds.

ϕ ≃_{F} ϕ iff cod(f_{i}) ≃_{F} dom(f_{i+1}), for i = 1, …, n − 1.  (1)

Now, the commutativity of diagrams has a simple characterization in terms of induced generalized congruences.

3.3. Theorem. Let F : A → B and G : A → C be two functors in Cat.

If there exists J : B → C such that F; J = G then ≃_{F} ⊆ ≃_{G}. Moreover, if J is a monomorphism, then ≃_{F} = ≃_{G}.

On the other hand, if ≃_{F} ⊆ ≃_{G} and Im F = B, then there exists a unique J making the diagram commute. Moreover, J is a monomorphism iff ≃_{F} = ≃_{G}.

\xymatrix{A \ar[rr]^{F} \ar[dr]_{G} &  & B \ar@{.>}[dl]^{J} \\  & C}

Proof. Assume J : B → C with F; J = G and let ϕ, ψ ∈ Mor_{A}^{+}. Then

ϕ ≃_{F} ψ iff F (ϕ) = F (ψ) implies (F; J)(ϕ) = (F; J)(ψ) iff ϕ ≃_{G} ψ

The implication above can be reversed if J is a monomorphism. The same works for objects.

To prove the second part, define J(F (a)) ˆ= G(a) for a ∈ Ob_{A} and J(F (ϕ)) ˆ= G(ϕ) for ϕ ∈ Mor_{A}^{+} such that ϕ ≃_{F} ϕ. We claim the correctness of this definition. For, let F (a) = F (a′), i.e. a ≃_{F} a′. Then also G(a) = G(a′). In the same manner, if F (ϕ) = F (ψ) then G(ϕ) = G(ψ). Now, J is well-defined for all objects and morphisms of B because Im F = B. Clearly, the definition of J is the only one which could make the diagram commute.

If J is a monomorphism then, by the first part of the theorem, the generalized congruences involved are equal. For the converse implication it is enough to show that J is injective on morphisms. From Im F = B it follows that each morphism of B is of the form F (ϕ), for some ϕ ∈ Mor_{A}^{+}. So, assume J(F (ϕ)) = J(F (ψ)) where ϕ, ψ ∈ Mor_{A}^{+}. Because G = F; J, we have ϕ ≃_{G} ψ, and hence ϕ ≃_{F} ψ by assumption. That is, F (ϕ) = F (ψ), as required.

We have already mentioned that F is an epimorphism whenever Im F = B. In fact, a stronger property holds.

3.4. Theorem. Let F : A → B in Cat. Then, Im F = B iff F is an extremal epimorphism.

Proof. Suppose Im F = B. We show a stronger property then required. Suppose F; G = H; M, M being a monomorphisms. From theorem 3.3 it follows that ≃_{H;M} = ≃_{H} and ≃_{F} ⊆ ≃_{F;G}. Thus, ≃_{F} ⊆ ≃_{H}. Now, by theorem 3.3 again, there exists a unique J such that F; J = H. We have F; G = H; M = F; J; M. We know already that F is an epimorphism, so G = J; M. Thus, we have shown that F is a strong epimorphism. Hence, it is extremal.

On the other hand, assume that F : A → B is an extremal epimorphism. Consider the factorization of F into a corestriction |F | : A → Im F followed by an inclusion of Im F into B. Since F is extremal, it follows that the inclusion is surjective. Thus, Im F = B follows.

3.5. Generalized congruences. The definition of a generalized congruence induced by a functor suggests how to define a generalized congruence in an axiomatic way. First, let us extend the domain and codomain operations to non-empty sequences of morphisms as follows.

dom(f_{1} … f_{n}) ˆ= dom(f_{1}) cod(f_{1} … f_{n}) ˆ= cod(f_{n})

3.6. Definition. A generalized congruence on a category A is an equivalence relation ≃ on Ob_{A} and a partial equivalence relation ≃ on Mor_{A}^{+} satisfying the following conditions.

1. ϕχ ≃ ψ implies cod(ϕ) ≃ dom(χ),

2. ϕ ≃ ψ implies dom(ϕ) ≃ dom(ψ) and cod(ϕ) ≃ cod(ψ),

3. a ≃ b implies id_{a} ≃ id_{b},

4. ϕ ≃ ψ and χ ≃ ξ and cod(ϕ) ≃ dom(χ) implies ϕχ ≃ ψξ,

5. cod(f) = dom(g) implies fg ≃ (f; g).

Henceforth, non-empty sequences of morphisms ϕ and χ that satisfy condition cod(ϕ) ≃ dom(χ) are called ≃-composable. Sequences f_{1} … f_{n} ∈ Mor_{A}^{+}, where n ≥ 1, and such that cod(f_{i}) ≃ dom(f_{i+1}), for i = 1, …, n−1 are called ≃-paths. Obviously, two ≃-composable ≃-paths can be concatenated to form a new ≃-path. From condition 3.6(5) it follows that fid_{b} ≃ f, for f : a ↦ b. So, f ≃ f follows by symmetry and transitivity of ≃. Together with condition 3.6(4) it ensures that every ≃-path ϕ is in the domain of ≃, i.e. ϕ ≃ ϕ. Condition 3.6(1) is responsible for the converse implication, hence ϕ ≃ ϕ iff ϕ is a ≃-path. Thus ≃ restricted to the set of ≃-paths is an equivalence.

Due to condition 3.6(2), one of the pairs in condition 3.6(4) is ≃-composable iff the other pair is ≃-composable too. The converse to condition 3.6(3) holds by condition 3.6(2). The converse to condition 3.6(1) was already discussed above.

Symbols denoting congruences are overloaded by convention already used for functors.

The following result was to be expected.

3.7. Proposition. The generalized congruence induced by a functor is a generalized congruence.

Proof. Elementary verification.

Its converse, saying that every generalized congruence is induced by a functor, is the topic of the next section, cf. proposition 3.10.

Let us close this section with an example which shows how the ability to compare paths rather than single morphisms allows to distinguish different functors.

3.8. Example. Consider two categories and functors F and G between them depicted below. For simplicity sake, only non-identity morphisms are shown.

[figure: •; f; h; •; •; g; G; F; •; •; G(h); F (h)=F (f);F (g); F (f); G(f); •; F (g); G(g); •]

In the category on the left-hand side there are no non-trivial compositions. In the righthand side category there is one. The object parts of F and G are equal, and both identify the “middle” objects only. Both functors do not identify any morphisms from the domain, apart from the identity on the objects glued together. Hence, the generalized congruences induced by F and G coincide on single morphisms. The difference becomes apparent only at the level of paths. There, it becomes possible to say that (via F) morphisms f and g become composable with their composition identified (via F) with h, formally, fg ≃_{F} h. Considering functor G, f and g do become composable, but no identification of that sort takes place.

G is an extremal epimorphism, by theorem 3.4. F is not an epimorphism. Since ≃_{G} ⊂ ≃_{F}, it follows from theorem 3.3 that F uniquely factors through G, but not vice versa.

3.9. Quotients. Here we show that every generalized congruence is induced by a functor.

A quotient of a small category A with respect to a generalized congruence ≃ on A, denoted A/≃, is a category that consists of equivalence classes of objects and ≃-paths. Formally,

Objects. Ob_{A/≃} ˆ= {[a] | a ∈ Ob_{A} }

Morphism. Mor_{A/≃} ˆ= {[ϕ] | ϕ ∈ Mor_{A}^{+}, ϕ ≃ ϕ}

Operations. Defined on representatives, with concatenation of paths as a composition.

– id_{[a]} = [id_{a}].

– dom([ϕ]) = [dom(ϕ)] and cod([ϕ]) = [cod(ϕ)].

– [ϕ]; [ψ] = [ϕψ] whenever cod([ϕ]) = dom([ψ]).

A quotient functor of a generalized congruence ≃, Q_{≃} : A → A/≃, maps objects and morphisms to their ≃-equivalence classes, formally,

Quotient functor. Q_{≃}(a) ˆ= [a] and Q_{≃}(f) ˆ= [f].

3.10. Proposition. A/≃ is a category and Q_{≃} : A → A/≃ is a functor such that ≃_{Q_{≃}} = ≃.

Proof. It is easy to show that the operations in A/≃ are well-defined.

Now, dom(id_{[a]}) = dom([id_{a}]) = [dom(id_{a})] = [a] in A/≃, and similarly cod(id_{[a]}) = [a]. Somewhat more involved argument is required to show that [id_{a}] is the identity on

[a]. Given f : a′ ↦ b′ and a ≃ a′ it follows that id_{a}f ≃ id_{a′}f ≃ id_{a′}; f = f. Hence, by induction on the length of ≃-path ϕ it follows that id_{a}ϕ ≃ ϕ whenever dom(ϕ) ≃ a. Thus, id_{[a]}; [ϕ] = [id_{a}]; [ϕ] = [id_{a}ϕ] = [ϕ] whenever [a] = dom([ϕ]).

It is easy to verify that the other conditions of a small category are satisfied by A/≃ as well.

By construction, Q_{≃} maps id_{a} to [id_{a}], as required. Also, fg ≃ f; g when f and g are composable in A. So, [f; g] = [fg] = [f]; [g]. Thus, Q_{≃} is a functor. And by construction again, the generalized congruence induced by Q_{≃} equals ≃.

From theorem 3.4 it follows that each quotient functor is in fact an extremal epimorphism since the image of A via Q/≃ equals A/≃. The following corollary of theorem 3.3 relates functors with quotient functors defined on the common category.

3.11. Corollary. Let F : A → B be a functor, and let ≃ be a generalized congruence on A such that ≃ ⊆ ≃_{F}. Then there exists a unique J : A/≃ → B such that the diagram below commutes. Moreover, J is a monomorphism iff ≃ = ≃_{F}.

\xymatrix{A \ar[rr]^{Q_{≃}} \ar[dr]_{F} &  & A/≃ \ar@{.>}[dl]^{J} \\  & B}

3.12. Regular congruences. A relation R on A is a pair R = (R_{o}, R_{m}) with R_{o} ⊆ Ob_{A} and R_{m} ⊆ Mor_{A}^{+}. Generalized congruences are examples of relations on a category. Ordered by componentwise inclusion they form a complete lattice with componentwise intersections as meets. The total relation which identifies all objects and all non-empty sequences of morphisms in A is a generalized congruence.

Thus, for an arbitrary relation R there is a least generalized congruence containing R. It is called the principal congruence generated by R.

The following example shows that the principal congruence generated by an equivalence on objects and an equivalence on single morphisms only may result in new morphisms being related.

3.13. Example. Consider a relation R defined on the category depicted on the left hand side of figure 1. Equivalent morphisms are joined by dotted lines. Two objects are equivalent iff they are both either domains or codomains of two equivalent morphisms. Then, the principal congruence generated by R forces morphisms f and g to be related.

[figure: •; f; •; •; •; •; •; •; g; •; •; •; •; •; F; •; •; •; •]

Figure 1: A principal congruence can be non-trivial

This generalized congruence is induced by the functor which ‘glues’ equivalent morphisms together to form the category depicted on the right hand side of figure 1.

Often, important examples of generalized congruences are principal congruences generated by a relation on single morphisms only. A canonical example is a restriction of a generalized congruence ≃ to singleton sequences of morphisms . The restriction, denoted by |≃|, is defined formally by a |≃| a′ iff a ≃ a′, and f |≃| f′ iff f ≃ f′. The principal congruence generated by |≃| is, obviously, contained in ≃, it is called the regular part of ≃ and denoted ≃^{r}.

Generalized congruences equal to their regular parts deserve a formal definition.

3.14. Definition. A generalized congruence is called regular if it is equal to its regular part.

In terms of example 3.8, generalized congruence ≃_{G} is regular while ≃_{F} is not — its regular part equals ≃_{G}, in symbols, ≃^{r}_{F} = ≃_{G} = ≃^{r}_{G} while ≃_{F} ≠ ≃_{G}.

A principal congruence generated by a relation, the morphism part of which is defined on singletons only, is regular.

3.15. Proposition. Let R = (R_{o}, R_{m}) be a relation on a category A such that R_{m} ⊂ Mor_{A} × Mor_{A}. Then the principal congruence generated by R is regular.

Proof. Let ≃ be the principal congruence generated by R. Then, from the assumption it follows R ⊆ |≃|. Thus, ≃ ⊆ ≃^{r} since the operation of taking a principal congruence is monotone. Hence, ≃ = ≃^{r}, as required.

The following result gives a sufficient condition for regularity.

3.16. Proposition. Let the object part of a generalized congruence ≃ on A be the identity. Then ≃ is regular. Moreover, the morphism part of |≃| is a classical congruence.

Proof. Assume that the object part of ≃ is the identity relation. Then, the equivalence class of a morphism f : a ↦ b is contained in Mor_{A}(a, b) and two morphisms, f and g, are ≃-composable iff they are composable in the usual way. So, fg ≃ fg iff fg ≃^{r} f; g. It follows now by induction on the length of a ≃-path f_{1} … f_{n} that f_{1} … f_{n} ≃^{r} f_{1}; …; f_{n}.

Now, let g_{1} … g_{m} ≃ f_{1} … f_{n}. Firstly, it follows that g_{1}; …; g_{m} |≃| f_{1}; …; f_{n}. Secondly,

g_{1} … g_{m} ≃^{r} g_{1}; …; g_{m} ≃^{r} f_{1}; …; f_{n} ≃^{r} f_{1} … f_{n}

This shows that ≃ = ≃^{r}, i.e. ≃ is regular.

Finally, consider the morphism part of |≃|. Let f |≃| g and f′ |≃| g′ where f and f′ are composable. Then, f; f′ ≃ ff′ ≃ gg′ ≃ g; g′, so f; f′ |≃| g; g′ follows.

From the above it follows that each generalized congruence ≃ on A with a trivial object part is uniquely determined by a congruence in the textbook sense. The converse also holds. Given a classical congruence ∼, take it as a morphism part of a relation with the identity as an object part. Then the principal congruence ≃ generated by the relation fulfills a ≃ a′ iff a = a′ and f_{1} … f_{m} ≃ g_{1} … g_{n} iff both f ˆ= f_{1}; …;f_{m} and g ˆ= g_{1}; …;g_{n} are defined and f ∼ g. It is immediate that |≃| = ∼.

Thus, definition 3.6 conservatively extends the original textbook definition of a congruence.

4. Coequalizers and regular epimorphisms

Here, we start by showing that coequalizers in Cat can be constructed as quotient functors. Then we go on to show that the regular epimorphisms in Cat are those functors which induce regular generalized congruences.

The construction of coequalizers in a category is a step towards showing its cocompleteness. In case of Cat the remaining step, i.e. the construction of coproducts, is elementary. We believe that the explicit construction of coequalizers is also of independent interest.

Consider F, G : A → B. Let _{F} =_{G} be a relation on B defined by F (a) _{F} =_{G} G(a) and F (f) _{F} =_{G} G(f) on objects and morphisms, respectively.

4.1. Proposition. Let F, G : A → B in Cat. Define ≃ to be the principal congruence on B generated by _{F} =_{G}. Then the quotient functor Q_{≃} : B → B/≃ is the coequalizer of F and G.

Proof. Firstly, note that a functor H on B coequalizes F and G iff_{F} =_{G} is contained in the generalized congruence induced by H. In particular, Q_{≃} coequalizes F and G. Since ≃ is, by definition, the least such generalized congruence, the result follows by corollary 3.11.

A regular epimorphism is a morphism which is a coequalizer of a pair of morphisms. It is easy to show that every regular epimorphism is an epimorphism. In fact, every regular epimorphism is a strong epimorphism. In many categories the reverse is also true, but not in Cat. The corestriction |F | : A → Im F of a functor considered in example 3.8 is a surjection, and hence a strong epimorphism (theorem 3.4). We will show, that it is not regular.

The definition of a generalized congruence ≃ on a category refers to the notion of a ≃-path. We have seen that in some cases paths were necessary to express the nontrivial amalgamations performed by a functor. Sometimes, however, paths are introduced “passively”, and a generalized congruence is completely determined by its restriction |≃| to singleton paths. In anticipation of the results presented here, the latter were termed regular generalized congruences in section 3. Indeed, the regular congruences are those induced by regular epimorphisms in Cat. This is the content of theorem 4.3, the main result of this section.

We can specialize the notion of a kernel pair of an epimorphism, i.e. the pullback with itself, (cf. e.g. [7]), to Cat. Let F : B → C be a functor. Its kernel pair is a category A and a pair of morphisms π_{1}, π_{2} : A → B defined as follows.

Ob_{A} = {(a, b) | a, b ∈ Ob_{B}, a ≃_{F} b}
Mor_{A} = {(f, g) | f, g ∈ Mor_{B}, f ≃_{F} g }

Categorical operations in A are defined coordinatewise, e.g., id_{(a,b)} = (id_{a}, id_{b}). Functors π_{1} and π_{2} are projections to the first and the second coordinate, respectively.

In terms of generalized congruences, we notice that _{π_{1}}=_{π_{2}} is equal to |≃_{F} |. Hence the principal congruence generated by _{π_{1}}=_{π_{2}} is equal to the regular part of ≃_{F}.

4.2. Lemma. A functor in Cat is a coequalizer of its kernel pair if it is an extremal epimorphism and its induced generalized congruence is regular.

Proof. Let F : B → C be an extremal epimorphism inducing a regular generalized congruence ≃_{F}. Consider the coequalizer of the kernel pair of F. By construction, this is the quotient functor of the regular part of ≃_{F}. But in this case ≃^{r}_{F} = ≃_{F}. By construction, π_{1}; F = π_{2}; F, hence there exists a mediating functor J : B/≃_{F} → C, such that the following diagram commutes.

\xymatrix{A \ar[r]^{π_{1}} \ar[r]_{π_{2}} & B \ar[rr]^{Q_{≃_{F}}} \ar[dr]_{F} &  & B/≃_{F} \ar@{.>}[dl]^{J} \\  &  & C}

By corollary 3.11, J is a monomorphism, and since F is extremal, J must be an isomorphism. Thus, F is a coequalizer of π_{1} and π_{2} too.

Now, a characterization of regular epimorphisms in Cat is straightforward.

4.3. Theorem. A functor in Cat is a regular epimorphism iff it is an extremal epimorphism and its induced generalized congruence is regular.

Proof. Without loss of generality, we can assume that a regular epimorphism is a quotient functor of the principal congruence generated by a relation defined on single morphisms only. Such generalized congruences are regular by proposition 3.15. Of course, a regular epimorphism is extremal. The converse follows from lemma 4.2.

Now it is clear that |F | of example 3.8 is not regular. The other epimorphism considered there, called G, is regular, although it is not a surjection.

Yet another example, see [2, sec. 7], demonstrates that regular epimorphisms are not closed under composition.

4.4. Example. Consider category A with two objects and one non-identity morphism ℓ between them. Let ℕ be the additive monoid of natural numbers qua category. Then a functor F : A → ℕ is completely determined by letting, say, F (ℓ) = 1. Let B be the multiplicative submonoid {0, 1} of ℤ qua category, and let G : ℕ → B be defined by G(0) ˆ= 1, G(n) ˆ= 0, n ≥ 1.

Now, it can be readily seen that both functors are regular epimorphisms. Their composition F; G : A → B is an extremal epimorphism, even a surjection, but it is not regular since there is a non-trivial identification: ℓℓ ≃_{F;G} ℓ.

The above example is an instance of a general construction.

4.5. Proposition. Every extremal epimorphism in Cat factors as a composition of two regular epimorphisms.

Proof. Let F : A → B be an extremal epimorphism and let ≃ = ≃^{r}_{F} be the regular part of the congruence induced by F. Then Q_{≃} : A → A/≃ is regular, by theorem 4.3.

Now, F factors through Q_{≃} by theorem 3.3. The mediating functor J : A/≃ → B induces a regular congruence by proposition 3.16. With the help of theorem 3.4 it is easy to verify that J is extremal whenever F is extremal. Thus, by theorem 4.3, J is a regular epimorphism.

5. The hierarchy of epimorphisms

This final section collects our present knowledge on the relationship between classes of epimorphisms in Cat.

We have already given characterizations of the classes of extremal epimorphisms and regular epimorphisms. The former are exactly those functors whose images span their codomains. The latter are exactly those which induce regular congruences. We have also discussed examples of epimorphisms which are not extremal, and extremal but non-regular epimorphisms. The discussion of strong and strict epimorphisms was omitted as these classes in Cat are equal to the classes of extremal and regular epimorphisms, respectively.

The above are the main results of the paper. In the remaining part some other classes of epimorphisms are studied. We end by presenting a general picture of inclusions between classes of epimorphisms studied here.

There exist regular, non-surjective epimorphisms in Cat. On the other hand, split epimorphisms are surjective. So, there is a gap between the classes of split epimorphisms and regular epimorphisms. Because there are also non-regular, surjective epimorphisms, the correspondence between classes of regular, surjective and split epimorphisms is more intricate.

A functor F : A → B is said to reflect composition iff the following holds:

For all f, g ∈ Mor_{A} such that F (f); F (g) is defined in B there exist f′, g′ ∈ Mor_{A} such that F (f) = F (f′), F (g) = F (g′) and f′; g′ is defined in A.

Obviously, a split epimorphism reflects composition. Less obvious is the following property.

5.1. Proposition. An extremal epimorphism reflecting composition is surjective and regular.

Proof. Let F : A → B reflects composition. First, let us show that F is surjective. By theorem 3.4 every morphism g in B is a composition of images of morphisms from A via F, g = F (f_{1}); …; F (f_{n}). If F reflects composition then the composition F (f); F (f′) in B of two images of morphisms under F is an image of a single morphism from A. Thus, by induction on n, g is an image, which proves that F is surjective.

To prove the regularity of F suppose ϕ ≃_{F} ψ, ϕ, ψ ∈ Mor_{A}^{+}. We have to show that ϕ ≃^{r}_{F} ψ. Recall that ≃^{r}_{F} stands for the regular part of ≃_{F}, i.e. the part generated by the relation on single morphisms only. F is surjective, hence we can choose f, g ∈ Mor_{A} such that F (f) = F (ϕ) and F (g) = F (ψ). Then, by definition, f ≃^{r}_{F} g. It is sufficient now to show that f ≃^{r}_{F} ϕ and g ≃^{r}_{F} ψ. Without loss of generality, it is sufficient to prove the first relation only.

The proof goes by induction on the length of ϕ. If ϕ is a single morphism we are done. Suppose ϕ = hχ. Then F (h); F (χ) exists in B. F is a surjection, hence F (χ) ∈ Mor_{B} is an image of a single morphism. We use the assumption to find h′, h′′ ∈ Mor_{A} such that F (h′) = F (h), F (h′′) = F (χ) and h′; h′′ defined in A. Now, F (h′; h′′) = F (h′); F (h′′) = F (h); F (χ) = F (ϕ) = F (f). We have h′ ≃^{r}_{F} h by definition, and h′′ ≃^{r}_{F} χ by inductive hypothesis. Thus, f ≃_{F} hχ ≃^{r}_{F} h′h′′ ≃^{r}_{F} h′; h′′, and so f ≃^{r}_{F} h′; h′′ again by definition. It follows now that f ≃^{r}_{F} h′; h′′ ≃^{r}_{F} h′h′′ ≃^{r}_{F} ϕ, hence the claim holds.

Given a property P of morphisms one often considers its universal version: F is universally P provided every pullback of F belongs to P. For example, if P denotes the class of all epimorphisms, universally P coincides with the notion of stable morphism (cf. e.g. [2]). Both, being surjective and reflecting composition are easily seen to be universal properties.

Regularity itself is not a universal property. To see this consider the regular G from example 3.8. Then the result of pulling back G along an embedding of the category with two objects and one non-identity morphism ℓ used in the example 4.4 is not even

[figure: •; f; •; •; •; h; •; •; •; •; g; •; F; •; •; •; •; J; •; h′; f′; •; g′; •]

Figure 2: Surjective and regular epimorphism need not reflect composition

an epimorphism. The embedding to take is the one that maps ℓ to the composition G(f); G(g).

In fact, in the same manner one can prove a less obvious part of the following statement.

5.2. Proposition. A functor is a stable morphism in Cat iff it is surjective.

Proof. Surjectivity is a universal property, hence every surjective epimorphism is a stable morphism.

Suppose a functor F : A → B is not surjective. If it is not an epimorphism, it is not a stable morphism. If it is an epimorphism, there must exist a morphisms f in B which is not an image under F but whose source and target are images of A-objects. Then pullback F along an inclusion of the single morphism subcategory f of B into B. The result is an embedding of a discrete category into a non-discrete one, i.e., not an epimorphism. Hence, F is not a stable morphism.

We end this section by discussing again the example 3.13. In view of proposition 5.1, reflecting composition (plus extremality) implies universal regularity. The functor F depicted on figure 1 does reflect composition. But it does not satisfy a stronger property of reflecting compositions of three morphisms. In fact, there is a whole hierarchy of extremal epimorphisms reflecting the composition of n morphisms. Even the intersection of the classes in that hierarchy properly includes the class of split epimorphisms.

A minor modification of example 3.13 presented in figure 2 shows that the converse to proposition 5.1 does not hold. In this example, F (f); F (g) = F (h) holds, but this composition cannot be reflected in the source category, since the appropriate triangle has been deliberately left out. Moreover, F is not even a universally regular. To see this consider the embedding of the missing triangle. The pullback of the two functors is isomorphic to a copy of f, g, h in the left hand side category being put together to form a triangle f′, g′, h′ in the right side category. It is not a regular epimorphism — while ⟨f, f′⟩ ⟨g, g′⟩ ≃_{π_{2}} ⟨h, h′⟩, the similar relation with ≃^{r}_{π_{2}} does not hold.

One can see that F is still both surjective and a regular epimorphism, in particular

fg ≃^{r}_{F} h.

Again, the trick of embedding the missing triangle can be used in a more general setting to prove, together with the previous remarks, the following result.

5.3. Proposition. A functor is a universally regular epimorphism iff it is extremal and reflects composition.

Proof. An extremal epimorphism reflecting composition is surjective and regular, cf. proposition 5.1. Surjections are extremal epimorphisms. Both, surjectivity and reflecting composition are universal properties. Hence, an extremal epimorphism which reflects composition is universally regular.

Suppose that a functor F : A → B is not an extremal and reflecting composition epimorphism. If F is not surjective it follows from proposition 5.2 that it is not even stable, let alone universally regular. So, assume F is surjective but does not reflect composition. Then, one can find a commuting triangle in B which is not reflected in A. The pullback of F along an embedding of the ,,triangle” subcategory into B is a nonregular epimorphism. Hence, in neither case is F a universally regular epimorphism.

It is immediate that an extremal bimorphism is an isomorphism. We have already seen enough examples of non-iso extremal epimorphisms. Two examples of a non-iso bimorphism have already been briefly discussed in section 2.

Factorization of any functor F : A → B in Cat into its corestriction followed by an inclusion, viz.,

\xymatrix{A \ar[r]^{|F |} & Im F \ar@{^{(}->}[r]^{J} & B}

narrows the problem of characterizing epimorphisms to the problem of characterizing epimorphic inclusions. Indeed, F is an epimorphism iff J is. Hence, an epimorphism is either extremal, or a composition of an extremal epimorphism followed by a non-trivial bimorphism.

Characterization of bimorphisms and epimorphisms is still missing.

Figure 3 summarizes our knowledge about proper inclusions between classes of epimorphisms in Cat. Proper inclusions between the classes are drawn as arrows. isomorphisms

[figure]

split

extremal & reflecting composition = universally regular

surjective & regular

[figure]

surjective = stable = universally extremal

regular

[figure]

bimorphisms

[figure]

extremal

epimorphisms

Figure 3: Classes of epimorphisms in Cat.

References

[1] J. Adámek. Matematicské Struktury a Kategorie. Matematycký Seminar 17, SNTL, 1982.

[2] J. Adámek, H. Herrlich and G.E. Strecker. Abstract and Concrete Categories. Pure and Applied Mathematics series, John Wiley & Sons, Inc., 1990.

[3] M. Barr and C. Wells. Toposes, Triples and Theories. A Series of Comprehensive Studies in Mathematics vol. 278, Springer-Verlag, 1985.

[4] M. Barr and C. Wells. Category Theory for Computing Science. Prentice Hall International, 1990.

[5] F. Borceux. Handbook of Categorical Algebra 1, Basic Category Theory. Encyclopedia of Mathematics and its Applications, vol. 50, Cambridge University Press, 1994.

[6] H. Herrlich and G.E. Strecker. Category Theory. Second edition, Heldermann Verlag, Berlin 1979.

[7] S. MacLane. Categories for the Working Mathematician. Graduate Texts in Mathematics vol. 5, Springer-Verlag, 1971.

Institute of Computer Science, Polish Academy of Sciences, Gdańsk Branch Abrahama 18, 81-825 Sopot, Poland

Email: {M.Bednarczyk, A.Borzyszkowski, W.Pawlowski}@ipipan.gda.pl

This article may be accessed via WWW at http://www.tac.mta.ca/tac/ or by anony-

mous ftp at ftp://ftp.tac.mta.ca/pub/tac/html/volumes/1999/n11/n11.{dvi,ps}

THEORY AND APPLICATIONS OF CATEGORIES (ISSN 1201-561X) will disseminate articles that significantly advance the study of categorical algebra or methods, or that make significant new contributions to mathematical science using categorical methods. The scope of the journal includes: all areas of pure category theory, including higher dimensional categories; applications of category theory to algebra, geometry and topology and other areas of mathematics; applications of category theory to computer science, physics and other mathematical sciences; contributions to scientific knowledge that make use of categorical methods.

Articles appearing in the journal have been carefully and critically refereed under the responsibility of members of the Editorial Board. Only papers judged to be both significant and excellent are accepted for publication.

The method of distribution of the journal is via the Internet tools WWW/ftp. The journal is archived electronically and in printed paper format.

Subscription information. Individual subscribers receive (by e-mail) abstracts of articles as they are published. Full text of published articles is available in .dvi and Postscript format. Details will be e-mailed to new subscribers and are available by WWW/ftp. To subscribe, send e-mail to tac@mta.ca including a full name and postal address. For institutional subscription, send enquiries to the Managing Editor, Robert Rosebrugh, rrosebrugh@mta.ca.

Information for authors. The typesetting language of the journal is TEX, and L^{A}TEX is the preferred flavour. TEX source of articles for publication should be submitted by e-mail directly to an appropriate Editor. They are listed below. Please obtain detailed information on submission format and style files from the journal’s WWW server at URL http://www.tac.mta.ca/tac/ or by anonymous ftp from ftp.tac.mta.ca in the directory pub/tac/info. You may also write to tac@mta.ca to receive details by e-mail.

Editorial board.

John Baez, University of California, Riverside: baez@math.ucr.edu Michael Barr, McGill University: barr@barrs.org Lawrence Breen, Université de Paris 13: breen@math.univ-paris13.fr Ronald Brown, University of North Wales: r.brown@bangor.ac.uk Jean-Luc Brylinski, Pennsylvania State University: jlb@math.psu.edu Aurelio Carboni, Università dell Insubria: carboni@fis.unico.it P. T. Johnstone, University of Cambridge: ptj@pmms.cam.ac.uk G. Max Kelly, University of Sydney: maxk@maths.usyd.edu.au Anders Kock, University of Aarhus: kock@imf.au.dk F. William Lawvere, State University of New York at Buffalo: wlawvere@acsu.buffalo.edu Jean-Louis Loday, Université de Strasbourg: loday@math.u-strasbg.fr Ieke Moerdijk, University of Utrecht: moerdijk@math.ruu.nl Susan Niefield, Union College: niefiels@union.edu Robert Paré, Dalhousie University: pare@mscs.dal.ca Andrew Pitts, University of Cambridge: ap@cl.cam.ac.uk Robert Rosebrugh, Mount Allison University: rrosebrugh@mta.ca Jiri Rosicky, Masaryk University: rosicky@math.muni.cz James Stasheff, University of North Carolina: jds@charlie.math.unc.edu Ross Street, Macquarie University: street@math.mq.edu.au Walter Tholen, York University: tholen@mathstat.yorku.ca Myles Tierney, Rutgers University: tierney@math.rutgers.edu Robert F. C. Walters, University of Sydney: walters b@maths.usyd.edu.au R. J. Wood, Dalhousie University: rjwood@mscs.dal.ca