If $H\_i = (V\_i, E\_i)$ for $i=1,2$ are [hypergraphs](https://en.wikipedia.org/wiki/Hypergraph) then a map $f:V\_1\to V\_2$ is said to be a *hypergraph homomorphism* if $f(e\_1)\in E\_2$ for all $e\_1\in E\_1$. Hypergraphs together with hypergraph homomorphisms form a category. Is this category [cartesian closed](https://en.wikipedia.org/wiki/Cartesian_closed_category)?



Is the category of hypergraphs cartesian-closed?
I think the answer is yes, although the internal-hom may be a little surprising.


First let's describe the cartesian product. I believe the category $\rm HyGph$ is a [topological concrete category](https://ncatlab.org/nlab/show/topological+concrete+category) over $\rm Set$, in the following way. Suppose $X$ is a set and $\{S\_i\}$ is a family of hypergraphs, with functions $f\_i : X \to V\_{S\_i}$ to their vertex sets. Then there is a "largest hypergraph" on $X$ rendering the $f\_i$ homomorphisms, where $E\_X$ consists of all subsets $e\subseteq X$ such that $f\_i(e)\in E\_{S\_i}$ for all $i$. In particular, given hypergraphs $Y,Z$, if we take $X = V\_Y \times V\_Z$ with the $f$'s the projections, we obtain the product hypergraph structure on $V\_Y\times V\_Z = V\_{Y\times Z}$: thus $E\_{Y\times Z}$ consists of all subsets $e\subseteq V\_Y\times V\_Z$ such that $\pi\_1(e)\in E\_Y$ and $\pi\_2(e)\in E\_Z$. Put differently, each edge of $Y\times Z$ is obtained by choosing an edge $e\_Y\in E\_Y$ and an edge $e\_Z\in E\_Z$, and then choosing a subset of the rectangle $e\_Y \times e\_Z \subseteq V\_Y \times V\_Z$ that projects onto both $e\_Y$ and $e\_Z$, i.e. contains at least one ordered pair with each possible first coordinate and at least one ordered pair with each possible second component.


Now there is a standard way to discover what an internal-hom must look like if it exists, by mapping out of small objects. To start with, let $I$ be the hypergraph with one vertex and no edges. Then for any hypergraph $X=(V\_X,E\_X)$, a homomorphism $I\to X$ simply picks out a vertex of $X$. Thus, if there is an internal-hom $Y^X$, the vertices of $Y^X$ are in bijection with the homomorphisms $I\to Y^X$, which must in turn be in bijection with the homomorphisms $I\times X\to Y$. But since $I$ has no edges, the above description of the product means that $I\times X$ has no edges either (in fact we could see this simply because any edge of $I\times X$ must project to an edge of $I$). Thus *every* set-function from $V\_{I\times X} \cong V\_X$ to $V\_Y$ determines a vertex of $Y^X$, whether or not it is a homomorphism.


The information about homomorphisms is instead carried by the unary edges (edges containing only one vertex). The terminal hypergraph $1$ is a one-element set with the unique possible (unary) edge. A homomorphism $1\to X$ picks out a vertex of $X$ *that belong to a unary edge*. Thus, a homomorphism $1\to Y^X$ picks out such a vertex of $Y^X$, but such homomorphisms must be bijective to homomorphisms $1\times X \to Y$, i.e. $X\to Y$ since $1\times X \cong X$. So the vertices of $Y^X$ are the arbitrary set-functions $V\_X\to V\_Y$, while the homomorphisms are the set-functions that belong to unary edges. This is similar to some other examples of cartesian closed categories, such as $G\text{-}\rm Set$ in which the elements of $Y^X$ are arbitrary functions $X\to Y$, with $G$ acting by conjugation, so that the actual $G$-equivariant maps $X\to Y$ (the "real morphisms" in the category) are instead the $G$-fixed-points of the $G$-set $Y^X$.


We can detect all the other edges of $Y^X$ in a similar way. For any nonempty set $A$, let $J\_A$ be the hypergraph with vertices $A$ and the only edge being the whole set $A$. Then a homomorphism $J\_A\to X$ is a function $A\to X$ whose image is an edge. Thus, an edge of $Y^X$ must be uniquely determined by picking a subset $A\subseteq V\_{Y^X}$ of functions $V\_X\to V\_Y$ such that the corresponding function $A\times V\_X \to V\_Y$ is a homomorphism $J\_A \times X\to Y$, which is to say such that for any edge $e\_X\in E\_X$, if a subset $e\subseteq A\times e\_X$ projects onto both $A$ and $e\_X$, then $\{ f(x) \mid (f,x)\in e \}$ is an edge of $Y$.


This defines a hypergraph $Y^X$ which *must be* the cartesian-closed exponential *if such exists*. It remains to prove that it actually *is*, but I think this is fairly straightforward. The evaluation map $Y^X\times X\to Y$ is a homomorphism, essentially by definition of the edges of $Y^X$. And if $Z\times X\to Y$ is a homomorphism, then there is a unique induced function $V\_Z\to V\_{Y^X} = (V\_Y)^{V\_X}$, which is a homomorphism again essentially by definition of the edges of $Y^X$.


