The free category on a “set of arrows”, hence on a directed graph, is the (strict) category whose:
morphisms are the tuples of composable edges, hence the morphisms freely generated from these (directed) edges.
These morphisms may also be thought of as the “paths” traced out in the directed graph by traversing stepwise along its edges, whence free categories are also called path categories.
More formally, there is a forgetful functor $U_{Cat}$ from the 1-category $Cat^{strct}_{smll}$ of small strict categories (and functors between them) to that of directed graphs (assigning the underlying graph of morphisms, i.e. forgetting the composition-operation); and the free category construction is its left adjoint free construction $F_{Cat}$:
Often this is considered in composition with the “localization” functor that constructs the free groupoid on a given category:
(which relates to the Milnor construction, see Goerss & Jardine (2009), V.7)
a quiver representation is equivalently a functor on the free category of the given quiver
Some introductions to category theory have a discussion of free categories, for instance:
Michael Barr, Charles Wells, §2.6.16 in: Category theory for computing science, Prentice-Hall International Series in Computer Science (1995); reprinted in: Reprints in Theory and Applications of Categories 22 (2012) 1-538 [pdf, tac:tr22]
Saunders MacLane, Section II.7 (pp. 48) in: Categories for the Working Mathematician, Springer (1998) [doi:10.1007/978-1-4757-4721-8]
On path categories of context-free grammars:
Dana Latch, The connection between the fundamental groupoid and a unification algorithm for syntactil algebras (extended abstract) , Cah. Top. Géom. Diff. Cat. XXXII (1991). (link)
Bob Walters, The free category with products on a multigraph , JPAA 62 (1989). (link)
Bob Walters, A note on context-free languages , JPAA 62 (1989). (link)
Since the perspective on categories as ‘graphs with operations’ is closely related to their ‘logico-deductive’ side, it figures prominently in the work of Jim Lambek and Phil Scott (cf. the references at free topos).
Last revised on April 28, 2023 at 15:04:35. See the history of this page for a list of all contributions to it.