Topos of quivers

I take the point of view that topos theory is the best foundation for algebra. This is based upon the point of view that the most important aspects of the theory of functions, like input/output analysis are understood by the topos of functions. The topoi of sets and functions are enough to interpret classical algebraic structures.

Another topos that can be used as the foundation of other algebraic structures, like categories, is the topos of quivers. These are defined by set-valued functors over the category with two objects $E$ and $V$ and parallel edges $s$ and $t$ between them: As can be seen from this diagram, $X$ is neither a preorder nor a monoid. Indeed, $X$ can be considered to be the simplest category that is neither of these two simpler cases. Thus, $Quiv$ can be considered to be the first example of a topos that isn't produced by a preorder or a monoid.

This diagram explains the topos of quivers. The subobject classifier can be understood with a few more diagrams, which I have prepared for you next. After discussing the basic aspects of quivers, we will move on to discussing functors of quivers.

Subobject classifier

Every set-valued functor topos $Sets^C$ is associated with a family of distributive lattices for each object in $Ob(C)$, which can be used to classify subobjects. The topos of quivers is associated with the following lattice of vertex truth values: As well as the following lattice of edge truth values: These are combined to produce an object of truth values $\Omega$ which is internal to the topos of quivers. All that remains is to demonstrate that the working of the characteristic morphism, which maps a quivers to its vertex and edge truth values.

Definition. let $S \subseteq T$ be quivers. Then the characteristic morphism $\chi : T \to \Omega$ is the ordered pair of functions $(\chi_e,\chi_v)$. The first function $(\chi_e)$ maps an edge $(a,b)$ to a set of truth values containing the truth value $s$ iff the source element $a$ is in $T$, $t$ iff the target $b$ is in $T$, and $e$ iff $(a,b) \in T$. The second function $\chi_v$ is the characteristic function of sets.

Proposition. $(\chi_e,\chi_v) : T \to \Omega$ is a morphism of quivers.

Proof. let $e \in Hom(a,b)$. Then there are four cases (1) $f(e) = \emptyset$ then $f(e) \in Hom(\emptyset,\emptyset)$. (2) $f(e) = \{s\}$ then $f(e) \in Hom(\{v\},\emptyset)$ (3) $f(e) = \{t\}$ then $f(e) \in Hom(\emptyset,\{v\})$ (4) either $f(e) = \{s,t\}$ or $f(e) = \{s,t,e\}$ then $f(e) \in Hom(\{v\},\{v\})$. In each case $f(e) \in Hom(f(a),f(b))$. $\square$

Fundamental constructions:

Products and coproducts:
Let $Q$ and $R$ be quivers. Then the coproduct $Q+R$ corresponds to the disjoint union of graphs. Then $Q$ and $R$ are in two separate connected components. The product $Q \times R$ has $(E_Q \times E_R, V_Q \times V_R)$ as its underlying set, and it corresponds to the product of graphs. All other limits/colimits are defined componentwise.

Lattice of subobjects:
Let $Q$ be a quiver, then $Sub(Q)$ is the distributive lattice defined by lower sets of the dependency ordering, whereby an edge is dependent upon the vertices it contains. It is fully determined by the subobject classifier.

Lattice of congruences:
Let $Q$ be a quiver. Then $Con(Q)$ is the intersection of $Con(s)$ and $Con(t)$, the congruence lattices of the source and target functions. In particular, given an ordered pair of equivalence relations $(E_1,E_2)$ then this ordered pair is a congruence of both the source and target functions. Any such ordered pair produces a quotient quiver.

Functors:

The topos of quivers is associated to a number of forgetful functors. There are forgetful functors to the vertex set, edge set, and source and target functions. In particular, there is a forgetful functor to $Sets$ defined by mapping a quiver to the coproduct $V + E$, which makes $Quiv$ into a concrete category. Furthermore, there is a forgetful functor to $Rel$.

Theorem. let $r: Quiv \to Rel$ the function that maps any quiver to its underlying binary relation. Then $r$ is a functor.

Proof. let $f : Q \to T$ be a morphism of quivers. Then suppose $Hom(a,b) \not= \emptyset$ then $\exists e \in Hom(a,b)$ so that $f(e) \in Hom(f(a),f(b)$. Thus, $Hom(f(a),f(b)) \not= \emptyset$. An edge $(a,b)$ is in $r(Q)$ provided that its hom class is not empty, so that $(a,b) \in r(Q) \Rightarrow (f(a),f(b)) \in r(T)$. It follows that $r(f)$ is a relation homomorphism. $r$ corresponds to the forgetful functor to the vertex set, so $r$ is a well defined functor. $\square$

Lemma. let $f: Q \to T$ be a morphism of quivers, such that $T$ is a thin quiver. Then $f$ is fully determined by its vertex mapping.

Proof. let $e$ be an edge of $Q$ which is in $Hom(a,b)$ then $f(e) \in Hom(f(a),f(b))$. There is a unique edge $e' \in Hom(f(a),f(b))$ by the fact that $T$ is a thin quiver, so that $f(e) = e$ for every edge in $Q$. $\square$

Theorem. let $Tq$ be the full subcategory of the topos of quivers consisting of thin quivers. Then $f : Tq \to Rel$ is an isomorphism of categories.

Proof. (1) by restriction of the relation functor, $f$ is a functor from thin quivers to relations (2) by the previous lemma, given any morphism of relations we can cast it to a morphism of quivers so we can form the inverse functor $f^{-1}$. These two functors are inverses of one another, so they are isomorphisms. $\square$

Corollary. the category of simple graphs can be embedded in the topos of quivers, by taking the full subcategory of thin symmetric irreflexive thin quivers.

This interprets the category of simple graphs in terms of the topos of quivers, which may be of interest in algebraic graph theory. The category of simple graphs is typically the appropriate category to do graph theory in because of its relation to the lattice of cores, graph colourings, and so on.

See also:
Topoi of preorders
Topoi of monoid actions

External links:
Quiv at nlab