$Quiv$ or $DiGraph$ is the category of quivers or directed graphs. It can be viewed as the default categorical model for the concept of a category of graphs.
We can define a quiver to be a functor $G\colon X^{op} \to Set$, where $X^{op}$ is the category with an object $0$, an object $1$ and two morphisms $s, t\colon 1 \to 0$, along with identity morphisms. This lets us define $Quiv$ as the category of presheaves on $X$, where:
In other words, $Quiv$ is the functor category from $X^{op}$ to Set.
The category $Quiv = Set^{X^{op}}$, being a category of presheaves, is a topos. The representable functors $X(-, 0), X(-, 1)$ may be thought of as the “generic figures” (generic vertex, generic edge) that occur in directed graphs:
From this picture, we can see that:
The fact that $Quiv$ is a presheaf topos allows us to use topos theory, which give answers to questions like whether finite limits of directed graphs exist, or how to construct the exponential quiver $Y^X$ of all morphisms $X\to Y$ between two quivers in $Quiv$.
The initial object $0$ in $Quiv$ is the graph without vertices and edges aka the empty graph. The terminal object is the graph $1$ with one vertex and one edge. Points of an arbitrary graph $Y$ i.e. maps $1\to Y$ then correpond to loops in $Y$ whence any loopfree graph with a vertex has no points but is not empty ($\neq 0$).
In the following subsections, more of the structure of the topos $Quiv$ will be worked out explicitly.
Knowing the subobjects of the representable functors allows us to calculate the structure of the subobject classifier $\Omega$, since they correspond to the elements of the value of $\Omega$ at the corresponding objects of $X^{op}$:
We can visualize $\Omega$ as the following quiver with two vertices and five edges:
where the vertex $\emptyset$ has one loop labeled “empty”, and the vertex $\bullet$ has two loops with labels $(x, y)$ and ($x \stackrel{e}{\to} y$).
Suppose now that $X\subseteq Y$ is a subgraph and $\chi_X \colon Y\to\Omega$ is its characteristic map. On vertices:
Thus, a vertex is either contained in a subgraph or not. This is represented in $\Omega$ by two vertices.
For edges, the situation is more complicated since there are five cases, which are represented by five edges in $\Omega$. On edges:
The negation $\neg \colon \Omega \to \Omega$ is defined as the characteristic map of $\bot \colon 1 \to\Omega$. It specifies how
sits as a subgraph in $\Omega$:
Taking the complement of a subobject $X\subseteq Y$, i.e. taking the subobject $\neg X$ of $Y$ that is classified by $\neg\circ\chi_X$, then amounts to taking all vertices of $Y$ not in $X$ and all the edges in $Y$ between them.
Hence, the result $\neg\neg X$ of applying $\neg$ twice to $X\subseteq Y$ amounts to adding to $X$ all the edges of $Y$ that have source and target in $X$. This implies that a subgraph $X\subseteq Y$ is dense for the double negation topology given by $\neg\circ\neg \colon\Omega\to\Omega$ precisely when it contains all vertices of $Y$, since taking the complement twice will throw into $\neg\neg X$ all the edges in $Y$ between all the vertices in $X$.
By definition, a quiver $X$ is separated for $\neg\neg$ when, for every other quiver $Y$ and dense subobject $i \colon S\hookrightarrow Y$, and any map $f \colon S\to X$, there is at most one $g \colon Y\to X$ such that the following diagram commutes:
A separated quiver $X$ is a $\neg\neg$-sheaf when such a unique $g$ always exists.
Suppose that a quiver $X$ has a pair of parallel edges $w,z$. Then the subgraph $i:S\hookrightarrow X$ that is just like $X$ but has $w,z$ omitted is dense in $X$. Let $\tau_{zw}:X\to X$ be the automorphism of $X$ that is just like the identity on $X$ except that it interchanges $w$ and $z$. Then $id_X\circ i=\tau_{zw}\circ i=i$ and one sees that $X$ is not separated.
Conversely, let $X$ be a quiver with at most one edge $x\to y$ between any pair $(x,y)$ of vertices and $f:S\to X$ be a map with $i:S\hookrightarrow Y$ is dense in $Y$. Since $i$ is a bijection on the vertex sets of $S$ and $Y$, if a factorization of $f$ through $g:Y\to X$ and $i$ exists the effect of $g$ on the vertices is uniquely determined by $f$ but since in $X$ there is at most one edge between any pair of vertices the image of any edge $a\to b$ in $Y$ under $g$ is already fixed: it is the unique edge between $g(a)$ and $g(b)$. In particular, one sees that a separated object $X$ is a sheaf precisely when there exists exactly one edge between any pair of vertices since then arbitrary edges in arbitrary factors $Y$ can be mapped to the appropriate edge in $X$. To sum up:
A quiver $X$ is separated for the double negation topology $\neg\neg$ precisely if there exists at most an edge $a\to b$ between any pair $(a,b)$ of vertices. $X$ is a $\neg\neg$-sheaf precisely if there exists a unique edge $a\to b$ between any pair $(a,b)$. $\Box$
The corresponding full subcategories are denoted by $Sep_{\neg\neg}(Quiv)$ and $Sh_{\neg\neg}(Quiv)$ , respectively. By generalities, it follows that $Sep_{\neg\neg}(Quiv)$ is a quasitopos and $Sh_{\neg\neg}(Quiv)$ is a Boolean topos.
Quivers that have at most one edge between any pair of vertices can be called ‘simple’ with the caveat that contrary to (the usual concept of) a simple graph they are allowed to have loops. Similarly, $\neg\neg$-sheaves can be called ‘complete’.
Since the edges of $\neg\neg$-separated quivers simply encode a binary endorelation on their vertex sets and being a morphism between $\neg\neg$-separated quivers then amounts to preserve that relation one sees that $Sep_{\neg\neg}(Quiv)$ and $Sh_{\neg\neg}(Quiv)$ are equivalent to the categories $Bin$ with objects $(X,\rho)$ where $X$ is a set and $\rho$ a binary endorelation on $X$, and, respectively, the category $TotalRel$ of sets equipped with the total relation. The latter can be identified with $Set$ since morphisms between sets equipped with the total relation behave just like ordinary functions between sets.
The inclusion $Sh_{\neg\neg}(Quiv)\hookrightarrow Sep_{\neg\neg}(Quiv)$ is actually an essential localization, since it corresponds (from the relational perspective) to the adjoint triple $e\dashv u\dashv t:Set\hookrightarrow Bin$ where $t$ maps a set $X$ to $(X,\tau_X)$ with $\tau_X$ the total relation on $X$, $u$ is the forgetful functor mapping $(X,\rho)$ to $X$ and, $e$ maps a set $X$ to $(X,\empty)$.
Similarly, $Sh_{\neg\neg}(Quiv)\overset{i}{\hookrightarrow} Quiv$ is an essential subtopos: if we identify sheafification $r$ with the functor that maps a quiver to the quiver on the same vertex set with edge set the total relation on the vertex set, then $l\dashv r\dashv i$ where $l$ forgets the edges of a complete quiver.
In particular, it follows then from general properties of the double negation topology that $Sh_{\neg\neg}(Quiv)$ is the Aufhebung of $0\dashv 1$. Whence, there exists indeed a notion of ‘codiscreteness’ (= an Aufhebung of $0\dashv 1$) for quivers, namely ‘completeness’, but it does not arise from a right adjoint to the section functor $\Gamma \colon Quiv\to Set$ that maps a quiver to its set of loops. Indeed, the adjoint string $\Pi\dashv\Delta\dashv\Gamma \colon Quiv\to Set$ that comes with the ‘discrete’ inclusion $\Delta$ that maps a set to the quiver with vertex set $X$ and edge set precisely one loop for every vertex, is not a localisation since $\Pi\dashv\Delta$ is not a geometric morphism because $\Pi$ fails to preserve products.
Furthermore, since it is a general result for presheaf toposes (cf. La Palme Reyes et al. 2004, p.204) that $\Gamma$ has a right adjoint $B$ precisely if a generic figure has a point and in the case of Quiv neither the generic vertex nor the generic edge contains a loop, we see that the functor $\Gamma:Quiv\to Set$ has no right adjoint.
R. T. Bumby, D. M. Latch, Categorical Constructions in Graph Theory , Internat. J. Math. & Math. Sci. 9 no.1 (1986) pp.1-16. (web)
F. W. Lawvere, Qualitative Distinctions between some Toposes of Generalized Graphs, Cont. Math. 92 (1989) pp.261-299.
M. La Palme Reyes, G. E. Reyes, H. Zolfaghari, Generic Figures and their Glueings, Polimetrica Milano 2004. (pdf)
S. Vigna, A Guided Tour in the Topos of Graphs , arXiv.0306394 (2003). (arXiv)
Last revised on August 31, 2022 at 01:19:23. See the history of this page for a list of all contributions to it.