A Structural Analysis of Limits and Colimits in Monographs

Table of Links

Abstract and 1 Introduction

2 Basic Definitions and Notations

2.1 Sets

2.2 Sequences

2.3 Signatures and Algebras and 2.4 Categories

3 Monographs and their Morphisms

4 Limits and Colimits

5 Drawing Monographs

6 Graph Structures and Typed Monographs

7 Submonographs and Partial Morphisms

8 Algebraic Transformations of Monographs

9 Attributed Typed Monographs

10 Conclusion and References

4 Limits and Colimits

The colimits of monographs follow the standard constructions of colimits in Sets and Graphs.

Theorem 4.4. The categories of Definition 3.5 are finitely co-complete.

We next investigate the limits in categories of monographs. Products of monographs are more difficult to build than products of graphs. This is due to the fact that edges of identical length may be adjacent to edges of different lengths.

We therefore see that E (A x B) is only a subset of EA x EB.

Lemma 4.6. Every pair of parallel morphisms f, g : A → B has an equalizer (E, e) eq such that E is finite whenever A is finite.

Corollary 4.7. The monomorphisms in Monogr are the injective morphisms.

A well-known consequence of Lemmas 4.5 and 4.6 is that all non-empty finite diagrams in Monogr have limits. Since a limit of O-monographs (resp. standard monographs) is an O-monograph (resp. standard), this holds for all categories of Definition 3.5. In particular they all have pullbacks.

We shall now investigate the limits of the empty diagram in these categories, i.e., their possible terminal objects.

Definition 4.8. For any set of ordinals O, let

Lemma 4.11. Monogr, SMonogr and FMonogr have no terminal object.

Since terminal objects are limits of empty diagrams obviously these categories are not finitely complete.

Theorem 4.12. O-SMonogr is finitely complete for every set of ordinals O. The categories Monogr, SMonogr and FMonogr are not finitely complete.

Proof. By Lemmas 4.5, 4.6, 4.9 and 4.11.

The category Graphs is also known to be adhesive, a property of pushouts and pullbacks that has important consequences on algebraic transformations (see [8]) and that we shall therefore investigate.

Definition 4.13 (van Kampen squares, adhesive categories). A pushout square (A, B, C, D) is a van Kampen square if for any commutative cube

A category has pushouts along monomorphisms if all sources (A, f, g) have pushouts whenever f or g is a monomorphism.

A category is adhesive if it has pullbacks, pushouts along monomorphisms and all such pushouts are van Kampen squares.

As in the proof that Graphs is adhesive, we will use the fact that the category Sets is adhesive.

Lemma 4.14. E reflects isomorphisms.

A side consequence is that Monogr is balanced, i.e., if f is both a monomorphism and an epimorphism, then by Corollaries 4.3 and 4.7 f is bijective, hence is an isomorphism. More important is that we can use [7, Theorem 24.7], i.e., that a faithful and isomorphism reflecting functor from a category that has some limits or colimits and preserves them, also reflects them.

Lemma 4.15. E preserves and reflects finite colimits.

Proof. It is easy to see from the proofs of Lemmas 4.1 and 4.2 that E preserves both coproducts and coequalizers, so that E preserves all finite co-limits and hence also reflects them.

This is particularly true for pushouts. The situation for pullbacks is more complicated since E does not preserve products.

Lemma 4.16. E preserves and reflects pullbacks.

Theorem 4.17. The categories of Definition 3.5 are adhesive.

Proof. The existence of pullbacks and pushouts is already established. In any of these categories a commutative cube built on a pushout along a monomorphism as bottom face and with pullbacks as back faces, has an underlying cube in Sets that has the same properties by Corollary 4.7, Lemmas 4.15 and 4.16. Since Sets is an adhesive category (see [8]) the underlying bottom face is a van Kampen square, hence such is the bottom face of the initial cube by Lemmas 4.15 and 4.16.