nLab free category




The free category on a “set of arrows”, hence on a directed graph, is the (strict) category whose:

More formally, there is a forgetful functor U CatU_{Cat} from the 1-category Cat smll strct 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 CatF_{Cat}:

Cat smll strctU CatF CatDiGrph Cat^{strct}_{smll} \underoverset {\underset{U_{Cat}}{\longrightarrow}} {\overset{F_{Cat}}{\longleftarrow}} {\;\;\bot\;\;\;} DiGrph

Often this is considered in composition with the “localization” functor that constructs the free groupoid on a given category:

Grpd smll strctU GrpdF GrpdCat smll strctU CatF CatDiGrph Grpd^{strct}_{smll} \underoverset {\underset{U_{Grpd}}{\longrightarrow}} {\overset{F_{Grpd}}{\longleftarrow}} {\;\;\bot\;\;\;} Cat^{strct}_{smll} \underoverset {\underset{U_{Cat}}{\longrightarrow}} {\overset{F_{Cat}}{\longleftarrow}} {\;\;\bot\;\;\;} DiGrph

(which relates to the Milnor construction, see Goerss & Jardine (2009), V.7)


Some introductions to category theory have a discussion of free categories, for instance:

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.