I know at least two definitions of correspondence, and my question might as well be about both of them.
- Let $X,Y$ be objects in your favorite category. A correspondence is a span, namely a diagram $X \leftarrow Z \rightarrow Y$.
- 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.)