MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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 '12 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 '12 at 23:02
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 '12 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 '12 at 23:29
@Oliver: interesting. The fact that the finite powerset functor fails to preserve binary products doesn't imply that it fails to preserve pullbacks. Nevertheless, I agree that it fails to preserve pullbacks. So something's wrong somewhere. It would be interesting to go through the proof of Cor 4.4 in the case at hand; this should show whether it's Cor 4.4 or the result that hypergraphs form a topos (or both!) that's wrong. – Tom Leinster Mar 12 '12 at 0:09

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.

share|cite|improve this answer
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 '12 at 17:36
+1, for being correct. – James Cranch Apr 4 '12 at 18:23

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.