Then the topos theory of graphs can be understood by a functor $f : Digraph \to Quiv$ that takes a directed graph to its corresponding quiver and another functor $f: Graph \to Sets^C$ that takes a given undirected graph to its corresponding permutable quiver in the topos $Sets^C$. This resolves the problem of the topos theory of graphs. The topos theory of hypergraphs on the other hand is a little bit more involved, and its far less developed which makes it an interesting avenue for exploration.
Definition 1. let $(V,E)$ be a hypergraph with a vertex set $V$ and an edge set $E \subseteq \mathcal{P}(V)$. Then define an object of the elementary presheaf topos $Sets^{[1,2]}$ by $(F,V,E)$ where $F$ is the binary relation consisting of ordered pairs $(V,E)$ with $V \in E$. Then the projection functions have $p(v,e) = v$ and $l(v,e) = e$.
This defines how we can represent hypergraphs as presheaves. The first and foremost task of topos theory is to determine how we can represent objects as presheaves, because then we can see what happens reason about them topos theoretically. For example, in the topos theory of categories we saw that a category can be represented as a copresheaf over a category with three objects and generated by four morphisms.
This presheaf topos theoretic representation of categories is then very fruitful, because it demonstrates how we can create a number of different presheaf-valued functors from the category of categories $Cat$ which allow us to reason logically about categories. For example, with this mechanism we define the idea of a congruence of a category, and this lead to the interesting realisation that while every quotient of a category by a congruence is a presheaf it is not always a category. We now have a similar situation where we can now reason logically about hypergraphs.
In order to make this representation more substantial we need for it to be functorial. Then we can reason functorially about hypergraphs in much the same way that we can about graphs and digraphs. In order to do this we will construct a functor $f: Hypergraph \to Sets^{[2,1]}$ from the category of hypergraphs to the topos of presheaves $Sets^{[1,2]}$.
Definition 2. let $Hypergraph$ be the category of hypergraphs. Then we map objects of $Hypergraph$ to copresheaves using definition 1. Further, we map morphisms of $Hypergraph$ to morphisms in $Sets^{[1,2]}$ by taking a morphism $f : (V_1, E_1) \to (V_2, E_2)$ and then making it into a morphism $f^* : (F_1, V_1, E_1) \to (F_2, V_2, E_2)$. There are the following components of this natural transformation:
- Vertices are directly mapped to vertices $f^*(v) = f(v)$
- Edges are mapped to their images $f^*(e) = f(e)$
- Flags are mapped componentwise $(v,e) = (f^*(v), f^*(e))$
Proof. by definition one we know that $F$ is a valid mapping of objects of categories. It remains to show that definition 2 produces a valid morphism of copresheaves in the topos $Sets^{[1,2]}$. To see this, first recall that a hypergraph morphism $f : (V_1, E_1) \to (V_2, E_2)$ has the property that for each edge $e \in E_1$ we have that $f(e) \in E_2$. By this fact we see that $(E_1, E_2)$ is a valid subobject of the image function $f : \mathcal{P}(E_1) \to \mathcal{P}(E_2)$ in the topos of functions $Sets^{\to}$. It follows that there is an induced subobject mapping $f : E_1 \to E_2$.
It remains to show that this satisfies the definition of a natural transformation. In the case of the presheaf topos $Sets^{[1,2]}$ this requires that $p(f(a)) = f(p(a))$ and $l(f(a)) = f(l(a))$ for each flag $a$. So let $(v,e)$ be a flag then we have that $f(p(a)) = f(v)$ and that $p(f(a)) = f(v)$ so the two coincide on points. On the other hand, $f(l(a)) = f(e)$ and $l(f(a)) = l(f(v), f(e)) = f(e)$ so that $F$ satisfies the definition of a natural transformation. Composition is defined componentwise so it satisfies functorial composition. $\square$
This demonstrates the functoriality of the mapping from the category of hypergraphs to the topos $Sets^{[1,2]}$ so that we can really consider hypergraphs topos theoretically. With this preliminary out of the way, we are now ready to consider how topos theory reveals new ideas about hypergraphs.
Subobjects
Consider the old set theoretical notion of a set system. Set theory is based upon building up hierarchies of nested sets. The basic notion of set theory is that of a subset. But to begin with, if we consider a set system in the old context of a set theory, we see that the basic idea of a subset is not a good means of reasoning about the parts of set systems. In the case of a set system, we have the possibility of not only taking a subset of the set system but also one of its members.
So already at the level of set systems, set theory reveals its flaws. I have considered a number of notions to deal with this in the study of set systems. One was to consider combinational multisets that arise from the finite set systems of combinatorics. Then these combinational multisets are invariants with respect to both taking non-trivial subsets and subsets of member sets, and so they give a better understanding of the size of a set. But even in this case, this formalism is limited by the requirement that the sets be finite.
How fortunate then that in the general case, the idea of a subobject of a set system can be recovered from the topos theoretic perspective. This works even when the set system is not finite. We can both take a subset of the set by reducing the edge set of the presheaf, or a subset of a member of the set by taking a subset of the sets flags that map edges to vertices. So this produces the correct notion of a subobject of a set system, even in the general case!
So topos theory is better then set theory even at its alleged forte: the study of nested systems of sets. As we see here, presheaf topos theory produces a better theory of nesting of sets. Topos theory is better then set theory in every way, but I have no interest in "dethroning" set theory or anything like that. I just want the best means of reasoning about the objects of mathematics, including sets. In each case that is provided by topos theory.
The topos $Sets$ provides the best means we have of reasoning about sets, and so classical set theory can just be considered to be the theory of sets which is now subsumed by the topos theory of $Sets$. These are just sets without any special type of elements, beyond that if we want to consider sets whose elements are sets themselves we can consider the topos $Sets^{[1,2]}$. So at every level topos theory improves upon the picture previously provided by set theory.
So even on the level of set systems, we see that the topos theoretic approach provides a better mechanism for reasoning. A set system is actually not a set, but rather a presheaf of the topos $Sets^{[1,2]}$. On the other hand, a set is a presheaf of the topos $Sets$. So we see that presheaves and not sets are actually the basic structures of mathematics. This basic realisation is key to improving our theory of computation, as we can apply topos theory to theoretical computer science.
Congruences
The topos theory of hypergraphs is reminiscent of the topos theory of categories in a number of ways. In both cases, we see that congruences need not always have quotients that belong in the same category. A quotient of a hypergraph need not be a hypergraph because consider that $Sets^{[1,2]}$ includes not only hypergraphs but also generalisations with repeated edges and edges that have repeated members.
As a consequence, if we take a congruence of a hypergraph it might have repeated edges or edges that have repeated vertices. In the same way, if we take a congruence of a category it doesn't necessarily have a categorical quotient. This is one reason why the category $Cat$ doesn't have epi-mono factorisations and other nice properties. This problem is solved by presheaf topos theory, which embeds categories into the nice setting of a topos. In both cases, we can get a subset of congruences that have appropriate quotients, which produces a monomorphism of partial orders to the congruence lattice.
See also:
Topoi as foundations
