Quiv (Rev #17, changes) in nLab

How where does the vertex Ω ∅ \Omega \emptyset work? has Suppose one that loop labeled “empty”, and the vertexX•⊆Y X\subseteq \bullet Y is has a two subgraph loops and with labelsχ X(:xY,→yΩ) \chi_X:Y\to\Omega (x, y) its and characteristic ( map, thenχ Xx→ey \chi_X x \stackrel{e}{\to} y ). maps vertices ofYY 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 in XX.

Suppose now that X⊆YX\subseteq Y is a subgraph and χ X:Y→Ω\chi_X \colon Y\to\Omega is its characteristic map. On vertices:

• χ X\chi_X maps vertices of YY not in XX to ∅\emptyset.
• χ X\chi_X maps vertices in XX to •\bullet.

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:

• χ X\chi_X maps edges which have neither source nor target in XX to the loop at ∅\emptyset.
• χ X\chi_X maps edges with only the source vertex in XX to xx.
• χ X\chi_X maps edges with only the target vertex in XX to yy.
• χ X\chi_X maps edges with both source and target vertices in XX, but where the edges themselves are not in the subgraph XX, to (x,y)(x,y).
• χ X\chi_X maps edges that are in the subgraph XX to (x→eyx \stackrel{e}{\to} y).

(Double) negation

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

im(⊥)=↺empty∅im(\bot)= \underoverset{{empty}}{\empty}{\circlearrowleft}

sits as a subgraph in Ω\Omega:

since •\bullet is not in im(⊥)im(\bot) whereas ∅\empty is, ¬\neg interchanges the two vertices and, accordingly, all loops at •\bullet must go to 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.

• Since •\bullet is not in im(⊥)im(\bot), but ∅\empty is, ¬\neg interchanges the two vertices.
• Thus, all loops at •\bullet must go to the loop empty{empty}.
• The edge emptyempty goes to (x→eyx \stackrel{e}{\to} y), since it is fully contained in im(⊥)im(\bot).
• Now xx has only its target vertex in im(⊥)im(\bot), hence it goes to the edge yy.
• However, yy has only its source vertex in im(⊥)im(\bot), so it goes to the edge xx.

Complementing Taking a the subobjectX⊆YX\subseteq Ycomplement i.e. of taking a the subobject¬X⊆Y \neg X\subseteq X Y , of i.e. taking the subobjectY¬X Y \neg X that of is classified by¬Y∘χ X \neg\circ\chi_X Y amounts that to is taking classified all by vertices ofY¬∘χ X Y \neg\circ\chi_X , not then in amounts to taking all vertices of X Y X Y and not all the edges in Y X Y X and all the edges in YY between them.

Whence Hence, 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 subgraphX⊆YX\subseteq Y is dense for the double negation topology given by¬∘¬::Ω→Ω \neg\circ\neg:\Omega\to\Omega \neg\circ\neg \colon\Omega\to\Omega , precisely when it contains all vertices ofYY , since complementing taking the complement 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 when, for every other quiverYY and dense subobject i::S↪Y i:S\hookrightarrow i \colon S\hookrightarrow Y , and any mapf::S→X f:S\to f \colon S\to X , there is at most oneg::Y→X g:Y\to g \colon 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:S↪Xi:S\hookrightarrow X that is just like XX but has w,zw,z ommitted omitted is dense inXX. Let τ zw:X→X\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 X∘i=τ zw∘i=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 x→yx\to y between any pair (x,y)(x,y) of vertices and f:S→Xf:S\to X be a map with i:S↪Yi: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:Y→Xg: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 a→ba\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:

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 localization , since it corresponds (from the relational perspective) to the adjoint string triple e⊣u⊣t:Set↪Bine\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 sheafificationrr 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⊣r⊣il\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 0⊣10\dashv 1. Whence, there exists indeed a notion of ‘codiscreteness’ (= an Aufhebung of 0⊣10\dashv 1) for quivers, namely ‘completeness’, but it does not arise from a right adjoint to the section functor Γ::Quiv→Set \Gamma: \Gamma \colon Quiv\to Set that maps a quiver to its set of loops. Indeed, the adjoint string Π⊣Δ⊣Γ::Quiv→Set \Pi\dashv\Delta\dashv\Gamma:Quiv\to \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 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. 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 Γ:Quiv→Set\Gamma:Quiv\to Set has no right adjoint.

• hypergraph

References

• 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). ( abstract arXiv)