Copresheaves by generating systems

In order to work with a variety of categories, it is necessary that we should be able to describe categories by morphic generating systems. As we construct larger and larger categories, it gets less and less practical to work with all morphisms exhaustively. By limiting ourselves to a generating set, we can greatly improve the practicality of a number of categorical constructions.

Definition. let $C$ be a category with objects $Ob(C)$ and morphisms $Arrows(C)$. Then a set $G$ is called its morphic generating set provided that $cl_C(g) = Arrows(C)$ where $cl$ is the closure function on $Arrows(C)$.

This definition does not require that a given morphic generating set be minimal. Therefore, we may as well say that every category is morphically generated by its entire set of objects by default. A consequence of this definition is that every category has a morphically generated subquiver (for example in the Locus computer algebra system this is the quiver that is displayed in the copresheaf viewer).

Definition. let $C$ be a category with morphic generating set $G$ then the morphically generated subquiver of $C$ with respect to $G$ is the subobject of $Quiv(C)$ in the topos of quivers generated by $Ob(C)$ and $G$.

In order to make the morphic generating set useful in most constructions it is necessary that we should have some kind of factorisation that can be used to describe all morphisms of $C$ in terms of $G$. For example, in the case of simplicial sets each morphism in $\Delta$ is described by its canonical factorisation into face and degeneracy maps.

Definition. let $C$ be a category generated by a morphic generating set $G$. Then a canonical factorisation is a function $f: Arrows(C) \to Seq(G)$ that takes morphisms in $C$ to sequences of elements of $G$.

There are different approaches to doing category theory. Certainly, in the topos theory branch which I am primarily concerned with, the fundamental objects are copresheaves $F: C \to Sets$. The great utility of morphic generating systems, as we shall see, is that we can use them to define copresheaves $F: C \to Sets$.

Theorem 1. let $F : C \to Sets$ be a copresheaf. Let $F'$ be the mapping which is only defined on $Ob(C)$ and $G$ then $F'$ completely determines $F$.

Proof. let $o \in Ob(C)$ then $F'(o) = F(o)$ so we can use $F'$ to determine the effect of $F$ on objects. On the other hand, suppose that $m \in Arrows(C)$. Then $m$ need not be in $G$, so we must produce a factorisation (such as the canonical factorisation or any other factorisation). Let us suppose that $g_1g_2g_3 = m$ is a valid factorisation of $m$. Then by the definition of a functor $F(m) = F(g_1)F(g_2)F(g_3)$. The functions $F$ and $F'$ coincide on $G$ so this can be replaced by $F(m) = F'(g_1)F'(g_2)F'(g_3)$. Therefore, $F'$ fully determines $F$. $\square$

From now on we can consider a copresheaf as entirely determined by the morphic generating set of a category $C$. Consider the theory of finitely presented lattices. Then in that case, such lattices are defined by object generating sets with systems of relations. These object generating systems of lattices are useful in defining logical varieties, but they are not so useful when defining categories. That is why we have to place special emphasis on morphic generating systems.

Here are some of the contexts that morphic generating systems emerge in:

• Hereditary discrete partial orders: let $P$ be a hereditary discrete partial order, then the covering relation $Cov(P)$ of $P$ is a morphic generating set of $P$.
• Finitely presented monoids: a monoid $M$ with a set of generators $G$ is also a category with one object and a morphic generating set $G$.
• Finitely presented groups: a finitely presented group $G$ is also a finitely presented monoid with both elements and their inverses as generators.
• Finitely presented categories: finally there are a number of cases wherein categories themselves are given by a presentation over a finite generating set $G$.

Certainly, the case of hereditary discrete partial orders means that copresheaves over any finite partial order can be defined by just their covering relation. This greatly simplifies the presentation of copresheaves over finite orders, such as sheaves over finite topologies. Finitely presented monoids are also an infinite source of examples of categories with generating sets, such as the bicyclic monoid. In the case of finitely presented groups, examples abound.

Finally, in the theory of categories proper we have countless instances where in it makes sense to limit ourselves only to a relevant set of generators. For example, when considering diamond copresheaves. Such diamond copresheaves occur from any morphism of functions, but if we constructed them without limiting ourselves to a generating set then we would always have a redundant composite morphism. The use of generating systems is a great simplification.

Consider the topos theory of categories. A category can be considered to be a copresheaf constructed from three sets: a set of composable pairs of morphisms called paths, a set of morphisms, and a set of objects and four functions: a composition function, a source function, a target function, and an identity morphism function. The composition function goes from composable paths to edges, the source and target functions go from edges to vertices, and the identity function takes a vertex and associates an edge to it. This is represented in the diagram below: Whilst this is the data of a category, its actual representation as a copresheaf requires that we also define all the other composite functions: the composition source, the composition target, the source identity, the target identity, the composition source identity, the composition target identity, and the identities of each object. The full index category looks like this: By restricting ourselves to a generating system, we get a much cleaner presentation of categories as copresheaves. This demonstrates the utility of morphic generating systems in presheaf topos theory.