Let $\mathbf{Rel}$ be the bicategory of sets, relations, and inclusions between relations. The following fact is well-known:

  • Any ordinary function $f : X \to Y$ between sets induces a pair of relations $B(1,f) : X \to Y$ and $B(f,1) : Y \to X$ in $\mathbf{Rel}$, defined explicitly by \begin{align*} B(1,f) &= (x,y) \mapsto y = f(x)\\ B(f,1) &= (y,x) \mapsto f(x) = y \end{align*} forming an adjunction $B(1,f) \dashv B(f,1)$. In particular, the unit and the counit of this adjunction correspond to the following logical implications: $$ \eta : x' = x \longrightarrow \exists y. y = f(x) \wedge f(x') = y $$ $$ \epsilon : \exists x. f(x) = y \wedge y' = f(x) \longrightarrow y' = y $$

One way of generalizing this example is by replacing sets with categories and relations by profunctors, considering the bicategory $\mathbf{Prof}$ as a proarrow equipment over $\mathbf{Cat}$.

I'm interested in a different sort of potential generalization. At least in the case of finite sets, a relation $X \to Y$ can be seen as an $X\times Y$ matrix with boolean-valued entries. Suppose we generalize to finite matrices valued in an arbitrary field $k$. Such matrices clearly form a 1-category (call it $\mathbf{FinMat}_k$), with composition defined by matrix multiplication. Moreover, every finite function $f : X \to Y$ induces a pair of matrices $B(1,f) : X \to Y$ and $B(f,1) : Y \to X$, corresponding to the indicator function \begin{align*} B(1,f) &= (x,y) \mapsto [y = f(x)]\\ B(f,1) &= (y,x) \mapsto [f(x) = y] \end{align*} where $[a = b]$ is 1 if $a = b$ and 0 otherwise.

Question: Is there a natural bicategorical structure on $\mathbf{FinMat}_k$ (at least for certain values of $k$), such that for every finite function $f : X \to Y$, we have an adjunction $B(1,f) \dashv B(f,1)$ in $\mathbf{FinMat}_k$? (Perhaps it is necessary to adjust the definition of $B(1,f)$ or $B(f,1)$?)

As a non-example which was my first attempt, in the case of $k = \mathbb{R}$, we could define 2-cells between real-valued matrices $\alpha : f \Rightarrow g : X \to Y$ as a family of inequalities $$ \alpha_{x,y} : f(x,y) \le g(x,y) $$ However, this would not verify the adjunction. In particular, although we do have an $\eta$ inequality \begin{align*} [x' = x] &\le [f(x') = f(x)] \\ &= \sum_y [y = f(x)] \cdot [f(x') = y] \end{align*} for every $x$ and $x'$, the $\epsilon$ inequality $$ \sum_x [f(x) = y] \cdot [y' = f(x)] \le [y' = y] $$ does not necessarily hold (in general, only if $f$ is injective).

  • $\begingroup$ you can consider vector spaces with a fixed finite base, the tensor product as arrows and linear morphisms as cells, this is a classical module's bicategory type. $\endgroup$ – Buschi Sergio Mar 31 '14 at 10:40
  • $\begingroup$ $\mathbf{FinMat}$ is a monoidal category, and so can be re-interpreted as a 2-category in the way you describe, but that just shifts my question one dimension up. Under that interpretation, each finite function $f : X \to Y$ determines a pair of linear transformations $k^{|X|} \to k^{|Y|}$ and $k^{|Y|} \to k^{|X|}$, and the question is whether/in what sense these can be seen as "adjoint"? $\endgroup$ – Noam Zeilberger Mar 31 '14 at 11:13
  • 3
    $\begingroup$ The $\mathbf{Poset}$-enrichment of $\mathbf{Rel}$ is coming from the fact that $\{ 0, 1 \}$ is itself partially ordered. Perhaps you might have better luck with a (tropical) semiring instead of a field? $\endgroup$ – Zhen Lin Mar 31 '14 at 13:10
  • $\begingroup$ One thing you can do is generalize relations by giving a function on the middle set (the one that maps to the ends) and then this corresponds to a morphim from functions on one set to functions on the other, so basically to this matrix. This can be generalized by replacing function with distribution, vector bundle, sheaf etc. $\endgroup$ – Adam Gal Oct 13 '14 at 19:55

It's not strictly speaking true that working with a field $k$ generalizes the case of relations: composition of relations doesn't agree with composition of $\mathbb{F}_2$-valued matrices. Relations are instead matrices valued in the Boolean semiring $B = \{ 0, 1 \}$, where addition is logical OR instead of logical XOR. The Boolean semiring is fundamentally a poset, with addition coming from taking categorical coproducts and multiplication coming from taking categorical products, so it's natural to try to replace $B$ with a distributive lattice $L$ rather than a field.

I claim that this works; the crucial fact is that addition is idempotent so there's no issue with the failure of $f$ to be injective.

More generally, for a suitably nice monoidal category $V$ we can construct a bicategory out of $V$-enriched profunctors / bimodules. Composition of profunctors is defined in terms of enriched coends. In particular we can take $V$ to be a suitably nice monoidal poset, which should give generalizations of the above construction as well as Zhen Lin's suggestion of using a tropical semiring in the comments.

  • $\begingroup$ For "suitably nice" it probably suffices to take $V$ to be cocomplete and closed. In the poset case this corresponds to taking $V$ to be a quantale (ncatlab.org/nlab/show/quantale). $\endgroup$ – Qiaochu Yuan Apr 1 '14 at 4:53
  • $\begingroup$ Thank you, this is helpful. I am still interested in the original example (in particular, real-valued matrices with ordinary matrix multiplication) and whether it can be given something like the structure of a proarrow equipment, but it's helpful to have spelled out how this example differs from $\mathbf{Rel}$. $\endgroup$ – Noam Zeilberger Apr 1 '14 at 6:25
  • $\begingroup$ @Noam: I don't think so, but it's hard to give a negative answer without a more precise definition of "natural bicategorical structure." This is related to how it seems hard to see adjoint linear operators as genuine special cases of adjoint functors. $\endgroup$ – Qiaochu Yuan Apr 1 '14 at 23:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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