Quivers as the underlying structure of categories

Question

The structure of a small category is a quiver - every vertex of the quiver represents an object with its identity morphism, and the edges of the quiver represent the non trivial morphisms (I know you can define it such that the identity morphisms are edges too, but it's more elegant this way imo). In other words, there is a forgetful functor from the category of small categories to $\mathbf{Quiv}$. My question is, what is the image of this functor? Namely, given any quiver, can we determine if exists a category of this structure?

The answer to the question whether exists a free category with the structure of a given quiver is very simple: we can just look at the free category generated by the quiver, and see whether we had to add arrows or not. But when we talk about the structure of categories that are not free, there isn't a simple criterion like that. For example, this quiver is a structure of a category, but this is not (as explained here).

Answer 1

This is only a partial answer.

A quiver $Q$ is given by a pair of sets $E, V$ and a function $\langle s, t \rangle: E \to V \times V$. The image of the function is a subset $R \hookrightarrow V \times V$, i.e., a relation on $V$, with an epi $\pi: E \to R$ given by $\pi(e) = (s(e), t(e))$.

A sufficient condition for $Q$ to be the underlying quiver of a category (removing identities) is for $R$ to be transitive. To see this, choose a section $\sigma: R \to E$. Suppose given edges $f: u \to v$ and $g: v \to w$ in $E$. Since $(u, v) \in R$ and $(v, w) \in R$, transitivity yields $(u, w) \in R$; in view of this, define $gf = \sigma(u, w)$. Associativity is immediate, for all composable chains $t \to u \to v \to w$ of arrows in $Q$, since either bracketing leads to $\sigma(t, w)$. Then freely adjoin identities to get a category whose underlying quiver is $Q$.

Transitivity of $R$ is not a necessary condition for $Q$ to underlie a category. It's necessary that $a \leq b$ and $b \leq c$ in $R$ implies $a \leq c$ whenever $a \neq c$. The only times transitivity of $R$ could fail is when there are arrows $f: u \to v$ and $g: v \to u$ but no non-identity arrow $u \to u$ in the originating category. This would in turn force the condition $g f = 1_u$ for any two arrows $f: u \to v$ and $g: v \to u$, and it places further conditions on the sizes of hom-sets in the category; for example, $|\hom(x, u)| \leq |\hom(x, v)|$ for all vertices $x$ (since composition with any $v \to u$ retracts $\hom(x, v)$ onto $\hom(x, u)$). Similarly, $|\hom(u, x)| \leq |\hom(v, x)|$. It's not yet clear to me whether all these conditions suffice to guarantee that $Q$ underlies a category structure.

Answer 2

Let $Q(a,b)$ to be the set of arrows in the quiver with source $a$ and target $b$. Define

• both $a\succ b$ and $b\prec a$ to mean $Q(b,b)=\emptyset$ and $Q(a,b)\ne\emptyset\ne Q(b,a)$;
• $a\ncong b$ to mean $Q(a,a)=\emptyset=Q(b,b)$ and $Q(a,b)\ne\emptyset\ne Q(b,a)$, i.e. $a\prec b$ and $a\succ b$.

If the quiver consists of non-identity morphisms of a category (whose composition is denoted by juxtaposition), then $Q(b,b)=\emptyset$ implies any two morphisms $s\colon b\to a$ and $r\colon a\to b$ satisfy $rs=\DeclareMathOperator{\id}{id}\id_b$.

Consquently, the quiver consists of the non-identity morphisms of a category only if:

0. $b\ncong c$ implies $|Q(b,c)|=1=|Q(c,b)|$ because $\ncong$ is symmetric and $h=h\id_b=h(gf)=(hg)f=\id_cf=f$ for $f,h\in Q(b,c)$, $g\in Q(c,b)$.

1. $a\ne c$ and $Q(b,c)\ne\emptyset\ne Q(a,b)$ imply $Q(a,c)\ne\emptyset$ because $\id_c\ne gf\colon a\to c$ for $(g,f)\in Q(b,c)\times Q(a,b)$ unless $a=c$.

2. $b\prec c$ and $a\succ b$ imply either that $|Q(b,c)|\times|Q(a,b)|\le|Q(a,c)|$, i.e. that there exists an injection $Q(b,c)\times Q(a,b)\rightarrowtail Q(a,c)$, or that $a=c$ and $b\ncong c$.

Condition 2 is necessary because $r'(sr)=(r's)r=\id_br=r$ and $(sr)s'=s(rs')=s\id_b=s$ for $r'\in Q(c,b)$, $s\in Q(b,c)$, $r\in Q(a,b)$, $s'\in Q(b,a)$, while $sr=\id_c$ implies the contradictory $e=(sr)e(sr)=s(res)r=s\id_br=sr=\id_c$ for $e\in Q(c,c)$.

3. $b\prec c$ implies either that $|Q(a,b)|\le|Q(a,c)|$, i.e. that there exists an injection $Q(a,b)\rightarrowtail Q(a,c)$, or that $a=c$ and $b\ncong c$.

Condition 3 is necessary because $r(sf)=(rs)f=f$ for $f\in Q(a,b)$, $s\in Q(b,c)$, $r\in Q(c,b)$, while $sf=\id_c$ implies the contradictory $e=(sf)e(sf)=s(fes)f=s\id_bf=sf=\id_c$ for $e\in Q(c,c)$.

4. $b\prec c$ implies either that $|Q(b,d)|\le|Q(c,d)|$, i.e. that there exists an injection $Q(b,d)\rightarrowtail Q(c,d)$, or $c=d$ and $b\ncong c$.

Condition 4 is necessary because $(gr)s=g(rs)=g$ for $s\in Q(b,c)$, $r\in Q(c,b)$, $g\in Q(c,d)$ while $gr=\id_c$ implies the contradictory $e=(gr)e(gr)=g(reg)r=g\id_br=gr=\id_c$ for $e\in Q(c,c)$.

Conversely, if these conditions are satisfied, a category whose non-identity morphisms are the quiver may be constructed as follows.

---

Condition 0 shows that $a\ncong b$ only if there are unique arrows $i_{a,b}\colon a\to b$ and $i_{b,a}\colon b\to a$. Call such arrows canonical isomorphisms.

Condition 1 guarantees that $a\ne c$, $a\ncong b$ and $b\ncong c$ imply $a\ncong c$, i.e. the symmetric reflexive relation $\cong$ given by $a\cong a$ if $a=a$ and $a\cong b$ if $a\ncong b$ is an equivalence relation.

Conditions 0 and 1 then imply the canonical isomorphisms of the quiver are the non-identity morphisms of the (unique) category encoding the equivalence relation $\cong$, i.e. given by $i_{b,c}\circ i_{a,b}=i_{a,c}$ if $a\ne c$ and $i_{b,a}\circ i_{a,b}=\id_a$.

For the sake of convenience, let $i_{a,a}=\id_a$ be the identity morphism of the category.

Pick a representative $a_0\in[a]$ for each equivalence class $[a]$ of $\cong$.

The bijections of conditions 3 and 4 imply that for every $(a,b)$ without $a\ncong b$, there exists a bijection $Q(a_0,b_0)\cong Q(a,b_0)\cong Q(a,b)$.

Assuming conditions 3 and 4 hold, pick such bijections and define $f\mapsto i_{b,b'}\circ f$ and $f\mapsto f\circ i_{a',a}$ to be the composites $Q(a,b)\cong Q(a_0,b_0)\cong Q(a,b )$ and $Q(a,b)\cong Q(a_0,b_0)\cong Q(a',b)$, respectively.

The resulting composition with canonical isomorphisms is associative: $(i_{b,b'}\circ f)\circ i_{a',a}=i_{b,b'}\circ(f\circ i_{a',a})$, $(f\circ i_{a',a})\circ i_{a'',a'}=f\circ(i_{a',a}\circ i_{a'',a'}$, $i_{b',b''}\circ(i_{b,b'}\circ f)=(i_{b',b''}\circ i_{b,b'})\circ f$.

In particular, setting $i_{a_0,a_0}=\id_{a_0}$, every arrow of the quiver $a\to b$ that is not a canonical isomorphism, i.e. without $a\ncong b$, is of the form $i_{b,b_0}\circ f\circ i_{a,a_0}$ for a unique arrow $f\colon a_0\to b_0$ with source and target representatives of equivalence classes of $\cong$.

Moroever, if the arrows $a_0\to b_0$ with source and target representatives of equivalence classes of $\cong$ form the quiver of non-identity morphisms of a category, then defining $(i_{c,c_0}\circ g\circ i_{b,b_0})\circ(i_{b_0,b}\circ f\circ i_{a,a_0})=i_{c,c_0}\circ (g\circ f)\circ i_{a,a_0}$ yields a category structure whose non-identity morphisms form the the whole quiver.

---

Restricting to arrows between representatives of equivalence classes of $\cong$ results in a quiver with no canonical isomorphisms.

If $b\prec c$ (without $b\ncong c$), call arrows $s\colon b\to c$ canonical sections and arrows $r\colon c\to b$ canonical retractions since we must define

• $r\circ s=\id_a$ for $(r,s)\in Q(b,a)\times Q(a,b)$ with $a\prec b$.

Lack of canonical isomorphisms implies

• $b\prec c$ contradicts $a\prec b$ and $c\prec d$, i.e. pairs $(r,r')$ of canonical retractions and pairs $(s,s')$ of canonical sections are never composable.

Moreover, the lack of canonical isomorphisms simplies the conditions necessary for a quiver to consist of the non-identity morphisms of a category to

1. $a\ne c$ and $Q(b,c)\ne\emptyset\ne Q(a,b)$ imply $Q(a,c)\ne\emptyset$
2. $a\succ b\prec c$ imply there exists an injection $Q(b,c)\times Q(a,b)\rightarrowtail Q(a,c)$, denoted $(s,f)\mapsto sf$.
3. $b\prec c$ implies there is an injection $Q(a,b)\rightarrowtail Q(a,c)$ (e.g. the composition $(s,f)\mapsto s\circ f$)
4. $a\succ b$ implies there is an injection $Q(b,c)\rightarrowtail Q(a,c)$ (e.g. the composition $(f,r)\mapsto f\circ r$)

Condition 1 in the absence of canonical isomorphisms implies

• $a\prec b\succ c$ imply $a=c$ and hence $r\circ s=\id_a$ for $(r,s)\in Q(b,c)\times Q(a,b)$.

Use the injections from condition 2 to define

• $s\circ r=sr$ for $(s,r)\in Q(b,c)\times Q(a,b)$ when $a\succ b\prec c$.

yields a subquiver with arrows that are either a canonical section $s$, a canonical retraction $r$, or a composite $sr$ thereof. Call such arrows structural.

Since $a\succ b\prec c$ and $a\succ b'\prec c$ imply $b=b'$ by condition 1 in the absence of canonical isomorphisms, it follows that $s_1r_1=s_2r_2$ implies $s_1=s_2$ and $r_1=r_2$ for all canonical sections $s_1,s_2$ and canonical retractions $r_1,r_2$.

It follows that structural arrows are the non-identity morphisms of a category isomorphic to that freely generatated by the canonical sections and retractions subject to the relation $r\circ s=\id$ for any composable canonical retraction $r$ and canonical section $s$.

Explicitly, for canonical section $s$ and canonical retraction $r$, $s'\circ rs=s$ for canonical section $s'$ and $rs\circ r'=r$ for canonical retraction $r'$.

---

Extending the categorical structure to include non-structural arrows (i.e. arrows in the quiver that are not structural) can be done as follows, using conditions 3 and 4:

$:g\in Q(b,c)$ if there is no $d$ such that $c\succ d$, $g:\in Q(b,c)$ if there is no $a$ such that $a\prec b$, and $:g:$ if both.

• For each quadruple $a\succ b,c\prec d$, pick an injection $Q(b,c)\rightarrowtail Q(a,d)$ denoted by $f\mapsto .f.$

Since $a\succ b,c\prec d$ and $a\succ b',c'\prec d$ imply $b=b'$ and $c=d$, it follows that $.f.=.g.$ implies $f=g$ for any pair of arrows whose sources and targets (not a priori the same) have no arrows to themselves.

• For each triple $b,c\prec d$ with $Q(b,b)=\emptyset$, pick an injection $Q(b,c)\rightarrowtail Q(b,d)$ denoted by $f\mapsto .f$ and define $s\circ f=.f$ for $(s,f)\in Q(c,d)\times Q(b,c)$

Since $c\prec d$ and $c'\prec d$ imply $c=c'$, it follows that $.f=.g$ implies $f=g$ for any pair of arrows $f$ and $g$ whose targets (not a priori the same) have no arrows to themselves.

• For each triple $a\succ b, c$ with $Q(c,c)=\emptyset$, pick an injection $Q(b,c)\rightarrowtail Q(a,c)$ denoted by $g\mapsto g.$ and define $g\circ r=g.$ for $(g,r)\in Q(b,c)\times Q(a,b)$

Since $a\succ b$ and $a\succ b'$ imply $b=b'$, it follows that $f.=g.$ implies $f=g$ for any pair of arrows $f$ and $g$ whose sources (not a priori the same) have arrows to themselves.

• For each triple $a,c\prec d$ with $Q(a,a)\ne\emptyset$ but without $a\succ c$, pick an injection $Q(a,c)\rightarrowtail Q(a,d)$ denoted $f\mapsto .f$ satisfying $g.\mapsto .g.$ and define $s\circ f=.f$ for $(s,f)\in Q(c,d)\times Q(a,c)$

Since $a\succ b$ and $a\succ b'$ imply $b=b'$, it follows that $.f=.g$ implies $f=g$ for any pair of arrows $f$ and $g$ whose targets (not a priori the same) have arrows to themselves.

• For each triple $a\succ b, d$ with $Q(d,d)\ne\emptyset$ but without $b\prec d$, pick an injection $Q(b,d)\rightarrowtail Q(a,d)$ denoted $g\mapsto g.$ satisfying $.f\mapsto .f.$ and define $g\circ r=g.$ for $(g,r)\in Q(b,d)\times Q(a,b)$.

Since $a\succ b$ and $a\succ b'$ imply $b=b'$, it follows that $f.=g.$ implies $f=g$ for any pair of arrows $f$ and $g$ whose targets (not a priori the same) have arrows to themselves.

The non-structural arrows have well-defined forms $f$, $.f$, $f.$, and $.f.$.

Moreover, defining

• $r\circ .f=f$ is necessary and sufficient for $r\circ(s\circ f)=(r\circ s)\circ f$;
• $g.\circ s=g$ is necessary and sufficient for $(g\circ r)\circ s=g\circ(r\circ s)$.

Let $:f$ and $f:$ represent non-structural arrows not of the form $.f$ or $f.$, respectively, and $:f:$ represent non-structural arrows that are of neither form. Note that $.f$ implies $:f$ and $f.$ implies $f:$.

Then defining

• $g\circ .f=(g\circ s)\circ:f$ is necessary and sufficient for $g\circ(s\circ f)=(g\circ s)\circ f$
• $g.\circ f=g:\circ(r\circ f)$ is necessary and sufficient for $(g\circ r)\circ f)=g\circ(r\circ f)$

These definitions are consistent since they give $g.\circ.f=g:\circ(r\circ.f)=g:\circ:f$ and $g.\circ.f=(g.\circ s)\circ:f=g:\circ:f$.

Finally, pick $k_{b,c}\in Q(b,c)$ whenever $Q(a,b)\ne\emptyset$ with the properties that $.k_{b,c}=k_{a,c}$, $k_{b,c}.=k_{b,d}$, and $k_{b,c}k_{a,b}=k_{a,c}$ if $a\succ b\prec c$ to be the remaining composites

• $g:\circ:f=k$
• $r\circ:f=k$
• $g:\circ s=k$

Note that $a\prec c$ and $Q(b,c)\ne\emptyset\ne Q(a,b)$ together with condition 1 imply $a\prec b$. Consequently

• $g\circ f$ is neither a canonical section nor a canonical retraction
• $r\circ:f=:k$ or a canonical retraction $k$, but not a canonical section
• $g:\circ s=k:$ or a canonical section $k$ but not a canonical retraction

Note also that the only cases where composites with $k$ do not give $k$ are

• $r\circ k_{a,b}=\id=k_{b,a}\circ s$, $s\circ k_{b,a}=sk_{b,a}$, and $k_{a,b}\circ r=k_{a,b}r$

---

The associativity equation $(h\circ g)\circ f=h\circ(g\circ f)$ holds by definition for the cases where $g$ is a canonical section or retraction and $h$ and $f$ are not of the form $sr$.

Because the category with non-identity morphisms the structural arrows is freely generated by canonical sections and retractions subject to the condition $r\circ s=\id$, the cases where one of $h$, $g$, or $f$ are of the form $sr$ follows from the cases where it is a canoncial section or a canonical retraction.

Moreover, by considering the opposite quiver, $h\circ(g\circ f)=(h\circ g)\circ f$ for $(h,g,f)$ a particular distribution of sections and retractions follows by duality from the case of the distribution reverse and sections and retractions exchanged.

The remaining cases where $h$ and $f$ are canonical sections or canonical retractions are

• $s\circ(f.\circ s')=s\circ f=.f=.f.\circ s'=(s\circ f.)\circ s'$
• $s\circ(f:\circ s')=s\circ:k=.k=k=.f:\circ s'=(s\circ f)\circ s'$
• $(r'\circ f)\circ r=r'\circ(f\circ r)$ by duality
• $s\circ(f\circ r)=s\circ f.=.f.=.f\circ r=(s\circ f)\circ r$
• $r\circ(.f.\circ s)=r\circ.f=f=f.\circ s=(r\circ.f.)\circ s$
• $r\circ(.f:\circ s)=r\circ.k=k=f\circ s=(r\circ .f:)\circ s$
• $r\circ(:f:\circ s)=r\circ k_{a,c}$, which equals $k_{a,d}$ or $\id$ depending on whether $k_{a,c}$ is a canonical section or not, and in either case equals $k_{b,c}\circ s=(r\circ:f:)\circ s$

The remaining cases where $h$ is a canonical section or a canonical retraction are

• $s\circ(g:\circ:f)=s\circ:k=.k=k=.g:\circ:f=(s\circ g:)\circ:f$
• $s\circ(g\circ.f)=s\circ((g\circ s')\circ:f)=(s\circ(g\circ s'))\circ:f=((s\circ g)\circ s')\circ f=(s\circ g)\circ.f$
• $s\circ(g.\circ f)=s\circ(g\circ(r\circ f))=(s\circ g)\circ(r\circ f)=((s\circ g)\circ r)\circ f=(s\circ(g\circ r))\circ f=(s\circ g.)\circ f$ (because $r\circ f=:k$ or a retraction reduces to previous associativity)
• $r\circ(g:\circ:f)=r\circ k=k=k\circ f=(r\circ g)\circ f$ (because $r\circ k$ is a retraction or $:k$)
• $r\circ(g.\circ.f)=r\circ k=k=k\circ f=(r\circ g)\circ f$
• $r\circ(g.\circ f)=r\circ(g:\circ(r'\circ f))=(r\circ g)\circ(r'\circ f)=((r\circ g)\circ r')\circ f=(r\circ g.)\circ f$ (because $r\circ f=:k$ or a canonical retraction)
• $r\circ(g\circ.f)=r\circ((g\circ s)\circ:f)=(r\circ(g\circ s))\circ f=((r\circ g)\circ s)\circ f=(r\circ g)\circ.f$ (because $r\circ g=k:$ or a canonical section)

The remaining cases where $f$ is a canonical section or a retraction follow by duality.

The cases where none of $h,g,f$ are structural are

• $h:\circ(:g:\circ:f)=h\circ k=k=k\circ f=(h:\circ:g:)\circ:f$

• $h.\circ(.g:\circ:f)=h.\circ k=k=k\circ.f=(h.\circ.g:)\circ:f$

• $h:\circ(:g:\circ.f)=h\circ k=k=k\circ.f=(h:\circ:g.)\circ.f$

• $h.\circ(.g.\circ.f)=h.\circ k=k=k\circ.f=(h.\circ.g.)\circ.f$

• $h\circ(g.\circ f)=h\circ(g:\circ(r\circ f))=(h\circ g)\circ(r\circ f)=((h\circ g)\circ r)\circ f=(h\circ(g\circ r))\circ f=(h\circ g.)\circ f$ (because $r\circ f=:k$ or a retraction)

• $h\circ(.g\circ f)=(h\circ .g)\circ f$ follows by duality

• $h\circ(g\circ .f)=h\circ((g\circ s)\circ:f)=(h\circ(g\circ s))\circ f=((h\circ g)\circ s)\circ f=(h\circ g)\circ.f$ (because $g\circ s=k:$ or a section)

• $h.\circ(g\circ f)=(h.\circ g)\circ f$ follows by duality