## The category of hypergraphs as a topos

It seems known that the category of hypergraphs is a topos. I am looking for any reference here, or just a statement of this in the literature, but can't find anything. There is one paper

A category-theoretical approach to hypergraphs, W. DÃ¶rfler and D. A. Waller, ARCHIV DER MATHEMATIK, Volume 34, Number 1, 185-192, DOI: 10.1007/BF01224952, 1980

which might contain information about that, but I don't have access to this paper (and it might take some time to get a copy, likely a paper-copy).

With a hypergraph I mean here a triple $(V,E,h)$, where $V$, $E$ are arbitrary sets, while $h$ is a map from $E$ to the set of finite subsets of $V$ (so $V$ is the set of vertices, $E$ the set of hyperedge-labels, and $h$ yields the hyperedge of a hyperedge-label). Morphisms are pairs $a: V \rightarrow V'$, $b: E \rightarrow E'$, which fulfil the usual commutativity condition.

-
 What is the terminal object of the category of hypergraphs? I thought at first it should have V = E = 1. But then you need a map from E to the finite powerset of V, that is, you need to choose one of the two subsets of 1. Neither does the job, if I'm understanding correctly. – Tom Leinster Mar 11 2012 at 22:53 The terminal object T is the (labelled) hypergraph with one vertex and two hyperedge labels 0, 1, which are mapped to the two possible subsets of the same size. For every hypergraph G, the vertices must map to the single vertex, while a hyperedge label must map to 0 iff the corresponding hyperedge is empty. So there is exactly one morphism from G to T. – Oliver Kullmann Mar 11 2012 at 23:02 OK, good . – Tom Leinster Mar 11 2012 at 23:04 A student showed (with my help) in his PhD thesis that the category of hypergraphs is a topos. I felt that people working with homomorphisms of graphs would know about this. Now I started thinking about publishing the more general results. The category of hypergraphs can also be obtained by Artin glueing of the finite (forward!) powerset endo-functor of SET. Now this functor does not preserve binary products, contradicting Corollary 4.4 in the paper you cited (if F is an endofunctor of a topos, then its Artin glueing is a topos iff F preserves pullbacks). So it seems that Corollary is false. – Oliver Kullmann Mar 11 2012 at 23:25 I have access to the paper, but it does not talk about the fact that this category is a topos, they only construct products and pullbacks and various other things related to graphs and $r$-uniform hypergraphs. And also, they do not have the same definition of hypergraph, their $h$ is a map from $E$ to the set of non empty subsets of $V$ (instead of finite subsets of $V$). – Guillaume Brunerie Mar 11 2012 at 23:29

One can reinterpret a hypergraph as a span-shaped diagram of sets where the left leg of the span is a finite map (meaning, all preimages are finite). Indeed, given a hypergraph, consider the span $$V\leftarrow\lbrace(v,e)\in V\times E\mid v\in h(e)\rbrace\rightarrow E;$$ it is clear that this gives a correspondence.

This seems more natural to work with.

The category of sets is a topos. The category of diagrams of some given shape in a topos is itself a topos, so the category of span-shaped diagrams of this sort is again a topos. Imposing finiteness conditions tends not to destroy the property of being a topos, and one can rapidly check that philosophy in this case.

-
It seems to me that your spans must also be required to be jointly monic (in addition to the left leg being finite-to-one). That looks like the sort of property that usually takes you from a topos into a quasitopos. – Mike Shulman Apr 4 2012 at 17:36
+1, for being correct. – James Cranch Apr 4 2012 at 18:23