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](http://en.wikipedia.org/wiki/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.)



How should I think about correspondences?
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 SetX of X-tuples of sets. Associated to a function f : X → Y we have the restriction or pullback functor f\* : SetY → SetX and its left adjoint the pushforward functor f! : SetX → SetY 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\* : SetX → SetY which is also a colimit-preserving functor. In fact, this construction identifies colimit-preserving functors from SetX to SetY with correspondences, as 2-categories. When we restrict to the elements of SetX 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 SetX we should consider the derived category of quasicoherent sheaves on X. This leads to the subject of [geometric function theory](http://ncatlab.org/nlab/show/geometric+function+theory).


