Enrichment - Category theory

Welcome to the Functional Programming Zulip Chat Archive. You can join the chat here.

Asad Saeeduddin

When we say a category C is enriched in the category of categories, we mean that each hom of C has the structure of a category (instead of the typical structure of a set). Is there some way to express in terms of enrichment the idea of a category C with objects that have the structure of categories instead?

Ohad Kammar

What do you mean by 'the structure of an object'?
Each object is a category, or the collection of objects is a category?
Is fibration/indexed category what you are thinking of?

Asad Saeeduddin

@Ohad Kammar I'm thinking about free categories induced by multidigraphs. In various situations it's useful to collapse subgraphs of a digraph into a single vertex. For example, digraphs can have cycles, but you can collapse cyclic subgraphs (i.e. SCCs) into single vertices to get an acyclic digraph. A more "real world" example is partitioning a state machine by an equivalence relation on states. This gives us a state machine where states are opaque sub-state machines, and transitions correspond to cut-sets in the original graph.

E.g. the state of an application might consist of what page you're on, as well as the state of some form on each page. We might like to model the state of each form using an individual state machine, and have a separate state machine that relates transitions between pages. The state set/type would contain all the information about the entire application, but we would simply partition it by discarding some distinguishing information (e.g. the state of the form) to obtain the state that the page transition state machine operates on.

I'm thinking about this concept of partitioning a state machine in terms of the free category of its state diagram. If I just wrote out the entire system as a single complex state machine, I could model it as the free category of a particular directed graph: its state diagram. The state diagram would account for all transitions between pages, as well as all internal transitions between the states of every form. It's less clear to me what categorical notion partitioning this graph/free category would correspond to. The objects here would be the sub-state machines probably (since we're modeling state machines as categories, we have that the objects have the structure of categories), and the morphisms would correspond to ??? Functors?

Asad Saeeduddin

I don't really know what fibrations or indexed categories are, sorry. Haven't got around to reading about those yet.

Ohad Kammar

To me it sounds like you're looking for quotients.

Ohad Kammar

For your first example, if you consider the category of directed graphs and their homomorphisms, I think the graph of SCC is a kind of coend

Ohad Kammar

I don't know what state diagrams are, so I don't know what the second example is