Quiv (Rev #8, changes) in nLab

Showing changes from revision #7 to #8: Added | Removed | Changed

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 op→SetG\colon X^{op} \to Set, where X opX^{op} is the category with an object 00, an object 11 and two morphisms s,t:1→0s, t\colon 1 \to 0, along with identity morphisms. This lets us efficiently define QuivQuiv as the category of presheaves on XX, where:

• objects are functors G:X op→SetG\colon X^{op} \to Set,
• morphisms are natural transformations between such functors.

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)=(x→ey)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),(x→ey)empty, x, y, (x, y), (x \stackrel{e}{\to} y).

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),(x→ey)}\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↺ ↺↺x→ey (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 x→eyx \stackrel{e}{\to} y).

How does Ω\Omega work? Suppose that X⊆YX\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.

(Double) negation

The negation ¬:Ω→Ω\neg:\Omega\to \Omega is defined as the characteristic map of ⊥:1→Ω\bot:1\to\Omega. It interchanges the vertices ∅\empty and •\bullet (vertices inside a subgraph are vertices outside its complement and vice versa) and maps emptyempty to ee (edges fully outside a subgraph are fully inside its complement) and maps the loops at •\bullet to emptyempty (an edge is outside the complement of a subgraph as long as its source and target are in the subgraph) and interchanges x,yx,y.

Complementing a subobject X⊆YX\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 X⊆YX\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 X⊆YX\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 arrows in YY between all the vertices in XX.

• hypergraph

References

• R. T. Bumpy, 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.

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