How should I think about correspondences?

Question

I know at least two definitions of correspondence, and my question might as well be about both of them.

1. Let $X,Y$ be objects in your favorite category. A correspondence is a span, namely a diagram $X \leftarrow Z \rightarrow Y$.
2. Let $X,Y$ be objects in your favorite category with products. A correspondence is a subobject of $X\times Y$.

If your category has pull-backs, then there is a good notion of composition of spans. My understanding is that definition 2. does not usually give a good notion of composition. Also, sometimes these definitions should be modified. For example, when the category consists of spaces with structure (symplectic manifolds, for example), often I should replace $Y$ above with its opposite. In particular, the correct notion of any of these should be such that the graph of a function is an example of a correspondence.

I'm generally interested in very concrete categories — the category of smooth manifolds, for example — and I'm hoping for open-ended answers to my open-ended question. Which is: to what extent should I treat correspondences like functions?

For example, if $K$ is a ring object in my category, what conditions make the set of correspondences between $X$ and $K$ into a ring? (Or higher-categorical analogue, since really the span-category is a two-category, etc.)

Answer 1

You can think of replacing your category by its category of spans as a kind of "linearization" of the category. For instance if you start with the category of finite sets, a correspondence between X and Y is the same thing as a map from the free commutative monoid on X to the free commutative monoid on Y. (Here we have to ignore the automorphisms of correspondences.) More generally, the category of spans is enriched in commutative monoids (assuming your original category has finite coproducts).

If we want to work with the category of all sets, we can use, instead of the free commutative monoid on X, the category Set^X of X-tuples of sets. Associated to a function f : X → Y we have the restriction or pullback functor f^* : Set^Y → Set^X and its left adjoint the pushforward functor f_! : Set^X → Set^Y which takes the union of all the sets corresponding to elements of X sent by f to a given element of Y. Both these functors preserve colimits, because f^* also has a right adjoint. Given a correspondence f : X ← Z → Y : g we can form the composite g_!f^* : Set^X → Set^Y which is also a colimit-preserving functor. In fact, this construction identifies colimit-preserving functors from Set^X to Set^Y with correspondences, as 2-categories. When we restrict to the elements of Set^X which are finite at each element of X and decategorify, we recover the homomorphism between the free commutative monoids on X and Y (under a suitable finiteness condition on Z).

When we start with the category of schemes, rather than Set^X we should consider the derived category of quasicoherent sheaves on X. This leads to the subject of geometric function theory.

Answer 2

Well, one reason to think about correspondences as functions is that in (nice) geometric categories, they give maps on cohomology. For instance, let $X,Y$ be schemes (or manifolds, or topological spaces, or...) and let $Z\subset X\times Y$. Then $Z$ comes with two maps $Z\to X$ and $Z\to Y$ (or, it IS this, from your definition one). Under nice circumstances (proper, flat, etc) you get pushforwards and pullbacks between $Z$ and $X,Y$. So then you can get a map $\pi_1^\ast:H^\ast(X)\to H^\ast(Z)$ which can be composed with $\pi_{2\ast}:H^{\ast}(Z)\to H^\ast(Y)$, and another from $H^\ast(Y)\to H^\ast(X)$ by switching $\pi_1$ and $\pi_2$. So under fairly reasonable conditions, you get pushforwards and pullbacks along correspondences.

Now, as for the more general categorical question, and span categories, and higher rings, I don't know much. I just know the above is necessary to even state the Geometric Langlands Conjecture properly, because you get Hecke correspondences between stacks, which give pushforwards and pullbacks on the derived categories.

Answer 3

The convention that the word "function" refers to something that takes exactly one value on every element of its domain is only about a hundred years old. A correspondence is a formalization of the older notion of a none-one-or-many-valued function, such as the square root or the reciprocal, in the framework of this convention. It's also possible to work with multivalued functions outside of this framework--Riemann surfaces were invented before this convention was established, to better understand multivalued functions in complex analysis.

In your version 2, we literally regard a correspondence as a (single-valued) function that takes an element x in X to a set of values in Y, by intersecting the defining subset of X x Y with {x} x Y and projecting to Y. In the more general version 1, we allow the set of values to be parameterized by something that's not necessarily a subset of Y.

To compose two correspondences, we say that g(f(x)) is the image of the set of values of f on x under the multivalued function g. This agrees with the usual fiber-product definition of composition.

From this point of view I think that the ring-valued correspondences on a set X won't themselves form a ring, for instance because there won't be additive inverses. (E.g. the function whose set of values on each element is the whole ring has no negative.) In category theory language the point is that the cartesian product is just some monoidal structure on correspondences, not necessarily a categorical product, so Cor(X,K x K) is not the same as Cor(X,K) x Cor(X,K).

Answer 4

I would call a subobject of $X\times Y$ a relation. And you're right that they don't compose in general; to have a good notion of composition for relations, you mostly need to be in a regular category. This includes many "algebraic" categories, but not (say) manifolds.

Answer 5

My understanding is that definition 2. does not usually give a good notion of composition.

Why? In categories of sets and quasicoherent sheaves you can compose $\alpha \subset X\times Y\ $ with $\beta \subset Y\times Z\ $ by something like $\alpha \circ \beta = \pi_*(i^*(\alpha \boxtimes \beta))\ \ $ where $i: X\times Y\times Z \to X\times Y\times Y\times Z\ \ $ and $\pi:X\times Y \times Z\to X\times Z\ \ $. You do need pushfowards for that.

This is used in algebrac geometry a lot, e.g. take a bundle $\mathcal L$ on $X\times Y$, then you have a map between $D^b(X) \to D^b(Y)$ given by pullback, twisting by $\mathcal L$ and pushforward.