The n-Category Café

That’s essentially right, and it’s an interesting observation which I think is due to Lawvere (who else?). There are some slightly persnickety (co, contra) variances to keep track of, but let’s have a look.

Categorifying, one naturally replaces the power set $P A$ in the 1-topos $Set$ by $Set^{C^{op}}$ in the 2-topos $Cat$, and the singleton mapping $\{- \}: A \to P A$ by the Yoneda embedding $y_C: C \to Set^{C^{op}}$. Here, $Set^{C^{op}}$ is the category of right (i.e., contravariant) $C$-sets.

In the categorical literature (e.g., in the work of Street and Walters on yoneda structures, and more recently in Mark Weber’s work on 2-toposes), it is common practice to abbreviate $Set^{C^{op}}$ to $P C$, and I’ll do that here as well.

Some general principles.

It is pertinent to remark that $P C$ is the free cocompletion of $C$ [assuming $C$ is small]: if $E$ is cocomplete, then a functor $F: C \to E$ determines, uniquely up to isomorphism, a cocontinuous functor

$$\hat{F}: P C \to E$$

which extends $F$ along the Yoneda embedding $y_C: C \to P C$. The way this works is that $\hat{F}$ assigns, to an object of $P C$, that is to say a weight $X: C^{op} \to Set$, the following weighted colimit in $E$:

$$X \otimes_C F = \int^c X(c) \cdot F(c).$$

By definition of weighted colimit, this fits in an adjunction formula

$$E(X \otimes_C F, e) \cong P C(X, hom_E(F-, e)).$$

It follows that in fact $\hat{F}$ is not just cocontinuous, but actually a left adjoint: its right adjoint is the functor $E \to P C$ which takes an object $e$ to the functor $hom_E(F-, e): C^{op} \to Set$.

Dually, $(P D)^{op}$ is the free completion of $D$. Now, this category is not only complete, but cocomplete (since $P D$, being a power of $Set$, is complete). Therefore, by the free cocompletion property above, a functor

$$R: C \to (P D)^{op} = (Set^{op})^D$$

induces an adjoint pair whose left adjoint is $\hat{R}$, and whose right adjoint takes an object $W$ of $(P D)^{op}$ to the functor

$$C^{op} \to Set: c \mapsto hom_{(P D)^{op}}(R c, W) = P D(W-, R c).$$

The main point.

Let’s recap. Start with a 2-relation

$$R: C^{op} \times D^{op} \to Set.$$

This induces, in the obvious way, a functor

$$\tilde{R}: C \to (Set^{op})^D = (P D)^{op}$$

and thence an adjunction whose right adjoint part is a functor $(P D)^{op} \to P C$. Our calculation above shows that this is precisely the contravariant functor $P D \to P C$ which takes a weight $W$ in $P D$ to

$$c \mapsto hom_{P D}(W, R(c, -)).$$

Does this look familiar yet? In fact, all we are really saying is that given a weight $X$ in $P C$, we have a natural bijective correspondence (using ? and $-$ to denote dummy variables $c$, $d$):

$$\frac{X(?) \to hom_{P D}(W(-), R(?, -))}{X(?) \times W(-) \to R(?, -)}.$$

We can turn this around, by a kind of reciprocity familiar from Galois connections, into the form

$$\frac{X(?) \times W(-) \to R(?, -)}{W(-) \to hom_{P C}(X(?), R(?, -))}$$

Now we arrive at the categorification of the Galois connection which David referred to (coming from my post on Concrete Groups and Axiomatic Theories): each 2-relation $R: C^{op} \times D^{op} \to Set$ induces a pair of contravariant functors

$$P C \to P D: X \mapsto hom_{P C}(X(?), R(?, -))$$

$$P D \to P C: W \mapsto hom_{P D}(W(-), R(?, -))$$

which fit into an adjunction

$$(P C \to (P D)^{op}) \dashv ((P D)^{op} \to P C).$$

At this point, we can if we like eliminate all the ‘ops’, and say: a 2-relation $R: C \times D \to Set$ induces a contravariant adjunction between $Set^C$ and $Set^D$. This implies, as a particular case, what David said:

Restricting to groups, a representation of $G \times H$ allows such a mapping [an adjunction] between $G$-$Set$ and ($H$-$Set)^{op}$.

Some loose ends.

I’d also like to mention, for those following the thread on Comparative Smootheology, that this categorified Galois connection is what Andrew Stacey was working out, where he describes a process which passes from a presheaf to a copresheaf, and vice-versa. It is the particular case where the 2-relation $R$ is the hom-functor $S^{op} \times S \to Set$; the corresponding adjunction is something which Lawvere calls conjugation.

Finally, a small comment on categorifying first-order logical formulae. For the ordinary Galois connection induced by a relation $R \subseteq A \times B$, I had written down an equivalent pair of formulae:

$$\frac{A′ \subseteq \{a \in A: \forall_{b: B'} (a,b) \in R\}}{B′ \subseteq \{b \in B: \forall_{a \in A'} (a,b) \in R\}}iff$$

For purposes of categorification, it is better if we think of a subset $A'$ of $A$ as a predicate on $A$, i.e., as a truth-valued function $A'(-): A \to \mathbf{2}$. Then, we would write

$$\frac{A'(a) \leq (\forall_{b: B} B'(b) \Rightarrow R(a, b))}{B'(b) \leq (\forall_{a: A} A'(a) \Rightarrow R(a, b))}iff$$

where $\Rightarrow$ is the implication operator (internal hom) in $\mathbf{2}$.

Categorifying this equivalence, we have an adjunction [a natural bijection]

$$\frac{A'(a) \to \int_{b: B} hom(B'(b), R(a, b))}{B'(b) \to \int_{a: A} hom(A'(a), R(a, b))}$$

where now $A'$, $B'$ are weights, and the categorified form of universal quantification is given by taking ends. These end formulas give the correct $Set$-valued homs on presheaf categories $P A$, $P B$, in exact accordance with our calculations above, where we had

$$\frac{A'(?) \to hom_{P B}(B'(-), R(?, -))}{B'(-) \to hom_{P A}(A'(?), R(?, -))}.$$

For the 2-categorical Galois correspondance, there is this paper of I. Waschkies and P. Polesello

http://www.intlpress.com/hha/v7/n1/a7/pdf