---
tag: FN6P3CTPTS
kind: definition
name: Free category
msc: [18A10, 18A40]
defines: THRHFW3SMP
uses: [0KFYGSHHF5, 085CH3CYMX, A2DE66937D, 28NQ0KRHD3, CV013KHVJG]
sources:
  - url: https://en.wikipedia.org/wiki/Free_category
---

## Definition

Let $G$ be a [[directed graph|0KFYGSHHF5]], allowed to have loops and several edges between two vertices.
Each edge $e$ of $G$ has a source vertex $s(e)$ and a target vertex $t(e)$.
A *path* from $x$ to $y$ of length $n \ge 1$ is a sequence $(e_1, \dots, e_n)$ of edges with $s(e_1) = x$, $t(e_n) = y$ and $t(e_i) = s(e_{i+1})$ for $1 \le i < n$.
Vertices and edges may repeat, as in a directed [[walk|085CH3CYMX]].
For each vertex $x$ there is also an empty path of length $0$ from $x$ to $x$.
The *free category* $F(G)$ on $G$ is the [[category|A2DE66937D]] whose objects are the vertices of $G$.
Its morphisms $x \to y$ are the paths from $x$ to $y$.
Composition is concatenation of paths, and the identities are the empty paths.

## Remarks

Concatenation is associative and the empty paths are units for it, so $F(G)$ is a category.
It has the universal property of a free object: for every category $\mathcal{C}$, each graph morphism from $G$ to the underlying graph of $\mathcal{C}$ extends to exactly one [[functor|28NQ0KRHD3]] $F(G) \to \mathcal{C}$.

Example: let $G$ have one vertex and one loop $a$.
The paths are $a^n = (a, \dots, a)$ with $n \ge 0$ letters, and $a^m \circ a^n = a^{m + n}$, so $F(G)$ is the one-object category of the monoid $(\N, +)$, the [[free monoid|CV013KHVJG]] on one generator.

Non-example: the category with one object and morphisms $\Z/2\Z$ is generated by one loop $a$, but it satisfies $a \circ a = \id$.
In the free category on one loop, $a \circ a$ has length $2$ and the identity has length $0$, so they differ.
So the category of $\Z/2\Z$ is not free on that graph.