nLab
Quiv

Context

Category theory

Topos Theory

topos theory

Background

Toposes

Internal Logic

Topos morphisms

Extra stuff, structure, properties

Cohomology and homotopy

In higher category theory

Theorems

Contents

Idea

QuivQuiv or DiGraphDiGraph is the category of quivers or (as category theorists often call them) directed graphs. It can be viewed as the default categorical model for the concept of a category of graphs.

Definition

We can define a quiver to be a functor G:X opSetG\colon X^{op} \to Set, where X opX^{op} is the category with an object 00, an object 11 and two morphisms s,t:10s, t\colon 1 \to 0, along with identity morphisms. This lets us efficiently define QuivQuiv as the category of presheaves on XX, where:

In other words, QuivQuiv is the functor category from this X opX^{op} to Set.

As a topos

The category Quiv=Set X opQuiv = Set^{X^{op}}, being a category of presheaves, is a topos. The representable functors X(,0),X(,1)X(-, 0), X(-, 1) may be pictured as the “generic figures” (generic vertex, generic edge) that occur in directed graphs:

X(,0)=,X(,1)=(xey)X(-, 0) = \bullet, \qquad X(-, 1) = (x \stackrel{e}{\to} y)

and from this picture we easily see that X(,0)X(-, 0) has two subobjects ,\emptyset, \bullet whereas X(,1)X(-, 1) has five: empty,x,y,(x,y),(xey)empty, x, y, (x, y), (x \stackrel{e}{\to} y).

Being a presheaf topos has a lot of nice consequences and instantly yields answer to questions like whether finite limits of directed graphs exist or how to construct the exponential quiver Y XY^X of all homomorphisms XYX\to Y between two quivers X,YX,Y in QuivQuiv since the answers are provided by topos theory.

In the following subsections some of the topos structure in QuivQuiv is worked out explicitly.

The subobject classifier

Knowing the subobjects of the representable functors in turn 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 opX^{op} i.e. the set of vertices of Ω\Omega is Ω(0)={,}\Omega(0)=\{\emptyset,\bullet\} and the set of edges is Ω(1)={empty,x,y,(x,y),(xey)}\Omega(1)=\{empty, x, y, (x, y), (x \stackrel{e}{\to} y)\}.

Whence pictured Ω\Omega is the quiver with two vertices and five edges that looks roughly like

xy empty xey (x,y)\array{ \emptyset & \underoverset{x}{y}{\rightleftarrows} & \bullet \\ \mathllap{empty} \circlearrowleft & & \circlearrowleft \circlearrowleft \mathrlap{x \stackrel{e}{\to} y} \\ & & \mathllap{(x, y)} }

(so there is one loop labeled “empty” at the vertex \emptyset, and two loops at the vertex \bullet, one labeled (x,y)(x, y) and the other xeyx \stackrel{e}{\to} y).

How does Ω\Omega work? Suppose that XYX\subseteq Y is a subgraph and χ X:YΩ\chi_X:Y\to\Omega its characteristic map, then χ X\chi_X maps vertices of YY not in XX to \emptyset and vertices in XX to \bullet (a vertex is either contained in a subgraph or not - the choice is binary and, accordingly, Ω\Omega needs two vertices to represent this). For edges the situation is more complicated since there are five ways (and, accordingly five edges in Ω\Omega to represent this) for an edge zz of YY to be related to the subgraph XX: the most straightforward is when zz has neither source nor target in XX, such zz are definitely not in XX and are represented in Ω\Omega by the loop at \emptyset. Now suppose that zz has either source or target vertex in XX but not both: χ X\chi_X maps these to the maps x,yx,y between \emptyset\rightleftarrows\bullet, respectively. When zz has both source and target in XX, the edge itself might or might not be in XX, and the corresponding two cases are represented by the two loops at \bullet , respectively, with ee representing the edges that are contained XX.

(Double) negation

The negation ¬:ΩΩ\neg:\Omega\to \Omega is defined as the characteristic map of :1Ω\bot:1\to\Omega. It specifies how

im()=emptyim(\bot)= \underoverset{{empty}}{\empty}{\circlearrowleft}

sits as a subgraph in Ω\Omega:

since \bullet is not im()im(\bot) whereas \empty is, ¬\neg interchanges the two vertices and, accordingly, all loops at \bullet must go empty{empty} . Conversely, emptyempty goes to ee (since it is fully contained in im()im(\bot)). Now xx has its target but not its source in im()im(\bot) hence it goes to yy whereas yy has its source but not its target in im()im(\bot) and therefor goes to xx.

Complementing a subobject XYX\subseteq Y i.e. taking the subobject ¬X\neg X of YY that is classified by ¬χ X\neg\circ\chi_X amounts to taking all vertices of YY not in XX and all the edges in YY between them.

Whence the result ¬¬X\neg\neg X of applying ¬\neg twice to XYX\subseteq Y amounts to adding to XX all the edges of YY that have source and target in XX. This implies in turn that a subgraph XYX\subseteq Y is dense for the double negation topology ¬¬:ΩΩ\neg\circ\neg:\Omega\to\Omega , precisely when it contains all vertices of YY since complementing twice will throw into ¬¬X\neg\neg X all the edges in YY between all the vertices in XX.

By definition, a quiver XX is separated for ¬¬\neg\neg when for every other quiver YY and dense subobject i:SYi:S\hookrightarrow Y and any map f:SXf:S\to X there is at most one g:YXg:Y\to X such that the following diagram commutes:

S i f Y g X \array{ S & & \\ i\downarrow &\searrow &f \\ Y &\underset{g}{\to} & X }

A separated quiver XX is a ¬¬\neg\neg-sheaf when such a unique gg always exists.

Suppose that a quiver XX has a pair of parallel edges w,zw,z. Then the subgraph i:SXi:S\hookrightarrow X that is just like XX but has w,zw,z ommitted is dense in XX. Let τ zw:XX\tau_{zw}:X\to X be the automorphism of XX that is just like the identity on XX except that it interchanges ww and zz. Then id Xi=τ zwi=iid_X\circ i=\tau_{zw}\circ i=i and one sees that XX is not separated.

Conversely, let XX be a quiver with at most one edge xyx\to y between any pair (x,y)(x,y) of vertices and f:SXf:S\to X be a map with i:SYi:S\hookrightarrow Y is dense in YY. Since ii is a bijection on the vertex sets of SS and YY, if a factorization of ff through g:YXg:Y\to X and ii exists the effect of gg on the vertices is uniquely determined by ff but since in XX there is at most one edge between any pair of vertices the image of any edge aba\to b in YY under gg is already fixed: it is the unique edge between g(a)g(a) and g(b)g(b). In particular, one sees that a separated object XX is a sheaf precisely when there exists exactly one edge between any pair of vertices since then arbitrary edges in arbitrary factors YY can be mapped to the appropriate edge in XX. To sum up:

Proposition

A quiver XX is separated for the double negation topology ¬¬\neg\neg precisely if there exists at most an edge aba\to b between any pair (a,b)(a,b) of vertices. XX is a ¬¬\neg\neg-sheaf precisely if there exists a unique edge aba\to b between any pair (a,b)(a,b). \Box

The corresponding full subcategories are denoted by Sep ¬¬(Quiv)Sep_{\neg\neg}(Quiv) and Sh ¬¬(Quiv)Sh_{\neg\neg}(Quiv) , respectively. By generalities, it follows that Sep ¬¬(Quiv)Sep_{\neg\neg}(Quiv) is a quasitopos and Sh ¬¬(Quiv)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 ¬¬(Quiv)Sep_{\neg\neg}(Quiv) and Sh ¬¬(Quiv)Sh_{\neg\neg}(Quiv) are equivalent to the categories BinBin with objects (X,ρ)(X,\rho) where XX is a set and ρ\rho a binary endorelation on XX, and, respectively, the category TotalRelTotalRel of sets equipped with the total relation. The latter can be identified with SetSet since morphisms between sets equipped with the total relation behave just like ordinary functions between sets.

Some subcategories and adjunctions

The inclusion Sh ¬¬(Quiv)Sep ¬¬(Quiv)Sh_{\neg\neg}(Quiv)\hookrightarrow Sep_{\neg\neg}(Quiv) is actually an essential localisation since it corresponds (from the relational perspective) to the adjoint string eut:SetBine\dashv u\dashv t:Set\hookrightarrow Bin where tt maps a set XX to (X,τ X)(X,\tau_X) with τ X\tau_X the total relation on XX, uu is the forgetful functor mapping (X,ρ)(X,\rho) to XX and, ee maps a set XX to (X,)(X,\empty).

Similarly, Sh ¬¬(Quiv)iQuivSh_{\neg\neg}(Quiv)\overset{i}{\hookrightarrow} Quiv is an essential subtopos: if we identify sheavification rr 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 lril\dashv r\dashv i where ll forgets the edges of a complete quiver.

In particular, it follows then from general properties of the double negation topology that Sh ¬¬(Quiv)Sh_{\neg\neg}(Quiv) is the Aufhebung of 010\dashv 1. Whence, there exists indeed a notion of ‘codiscreteness’ (= an Aufhebung of 010\dashv 1) for quivers, namely ‘completeness’, but it does not arise from a right adjoint to the section functor Γ:QuivSet\Gamma: Quiv\to Set that maps a quiver to its set of loops. Indeed, the adjoint string ΠΔΓ:QuivSet\Pi\dashv\Delta\dashv\Gamma:Quiv\to Set that comes with the ‘discrete’ inclusion Δ\Delta that maps a set to the quiver with vertex set XX 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 BB 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 Γ:QuivSet\Gamma:Quiv\to Set has no right adjoint.

References

  • R. T. Bumby, D. M. Latch, Categorical Constructions in Graph Theory , Internat. J. Math. & Math. Sci. 9 no.1 (1986) pp.1-16.

  • 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.

  • S. Vigna, A Guided Tour in the Topos of Graphs , arXiv.0306394 (2003). (abstract)

category: category

Revised on September 6, 2017 18:26:36 by Todd Trimble (47.18.191.229)