Is the category of hypergraphs cartesian-closed?

Question

If $H_i = (V_i, E_i)$ for $i=1,2$ are hypergraphs 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?

Answer 1

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 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$.