This entry is about the notion of spans/correspondences which generalizes that ofrelations. For spans invector spaces ormodules, seelinear span.

Contents

Definition

In set theory

Inset theory, aspan orcorrespondence betweensets$A$ and$B$ is a set$C$ with afunction$R:C\to A\times B$ to theproduct set$A\times B$. A span between a set$A$ and$A$ itself is adirected pseudograph, which is used to definecategories in set theory.

In dependent type theory

Independent type theory, there is a distinction between aspan, amultivalued partial function, and acorrespondence:

• Aspan between types$A$ and$B$ is a type$C$ with families of elements$x:C⊢g(x):A$ and$x:C⊢h(x):B$

• Amultivalued partial function from type$A$ to type$B$ is a type family$x:A⊢P(x)$ with a family of elements$x:A,p:P(x)⊢f(x,p):B$

• Acorrespondence between types$A$ and$B$ is a type family$x:A,y:B⊢R(x,y)$.

However, from any one of the above structures, one could get the other two structures, provided one hasidentity types anddependent pair types in the dependent type theory. Given a type family$x:A⊢P(x)$, let$z:{\sum }_{x:A}P(x)⊢{\pi }_1(z):A$ and$z:{\sum }_{x:A}P(x)⊢{\pi }_2(z):P({\pi }_1(z))$ be the dependent pair projections for thedependent pair type${\sum }_{x:A}P(x)$.

• From every span one could get a multivalued partial function by defining the type family$x:A⊢P(x)$ as$P(x)≔{\sum }_{y:C}g(y){=}_{A}x$ and the family of elements$x:A,p:P(x)⊢f(x,p):B$ as$f(x,p)≔h({\pi }_1(x))$.

• From every multivalued partial function one could get a span by defining the type$C$ as$C≔{\sum }_{x:A}P(x)$ and the family of elements$x:C⊢g(x):A$ as$g(x)≔{\pi }_1(x)$.

• From every multivalued partial function one could get a correspondence by defining the type family$x:A,y:B⊢R(x,y)$ as$R(x,y)≔{\sum }_{p:P(x)}f(x,p){=}_{B}y$.

• From every correspondence one could get a multivalued partial function by defining the type family$x:A⊢P(x)$ as$P(x)≔{\sum }_{y:B}R(x,y)$, and the family of elements$x:A,p:P(x)⊢h(x,p):B$ as$h(x,p)≔{\pi }_1(p)$

• From every span one could get a correspondence by defining the type family$x:A,y:B⊢R(x,y)$ as$R(x,y)≔{\sum }_{z:C}(g(z){=}_{A}x)\times (h(z){=}_{B}y)$.

• From every correspondence one could get a span by defining the type$C$ as$C≔{\sum }_{x:A}{\sum }_{y:B}R(x,y)$, the family of elements$z:C⊢g(z):A$ as$g(z)≔{\pi }_1(z)$, and the function$z:C⊢h(z):B$ as$h(z)≔{\pi }_1({\pi }_2(z))$

Given types$A$,$B$, and$C$ and spans$(D,x:D⊢g_D(x):A,x:D⊢h_D(x):B)$ between$A$ and$B$ and$(E,y:E⊢g_E(y):B,y:E⊢h_E(y):C)$ between$B$ and$C$, there is a span

defined by

Given types$A$,$B$, and$C$ and correspondences$x:A,y:B⊢R(x,y)$ and$y:B,z:C⊢S(y,z)$, there is a correspondence$x:A,z:C⊢(S\circ R)(x,z)$ defined by

In category theory

In anycategory$C$, aspan, orroof, orcorrespondence, from anobject$x$ to an object$y$ is adiagram of the form

where$s$ is some other object of the category. (The word “correspondence” is also sometimes used for aprofunctor.)

Thisdiagram is also called a ‘span’ because it looks like a little bridge; ‘roof’ is similar. The term ‘correspondence’ is prevalent in geometry and related areas; it comes about because a correspondence is a generalisation of a binaryrelation.

Note that a span with$f=1$ is just a morphism from$x$ to$y$, while a span with$g=1$ is a morphism from$y$ to$x$. So, a span can be thought of as a generalization of a morphism in which there is no longer any asymmetry between source and target.

A span in theopposite category$C^{\mathrm{op}}$ is called aco-span in$C$.

A span that has acocone is called acoquadrable span.

Categories of spans

If the category$C$ haspullbacks, we can compose spans. Namely, given a span from$x$ to$y$ and a span from$y$ to$z$:

we can take a pullback in the middle:

and obtain a span from$x$ to$z$:

This way of composing spans lets us define abicategorySpan$(C)$ with:

• objects of$C$ as objects
• spans as morphisms
• maps between spans as 2-morphisms

This is a weak 2-category: it has a nontrivialassociator: composition of spans is not strictly associative, because pullbacks are defined only up to canonical isomorphism. Anaturally definedstrict 2-category which is equivalent to$\mathrm{Span}(C)$ is the strict 2-category oflinear polynomial functors betweenslice categories of$C$.

(Note that we must choose a specific pullback when defining the composite of a pair of morphisms in$\mathrm{Span}(C)$, if we want to obtain abicategory as traditionally defined; this requires theaxiom of choice. Otherwise we obtain a bicategory with ‘composites of morphisms defined only up to canonical iso-2-morphism’; such a structure can be modeled by ananabicategory or anopetopic bicategory?.)

We can also obtain apseudo-double category?, whoseloose structure is as above, whosetight morphisms are functions, and whose cells are commuting diagrams,

Moreover, when$C$ is an arbitrary category, not necessarily having pullbacks, one can still obtain acovirtual double category. More details can be found in Section 4 ofDawson, Paré, Pronk (where the term oplax double category is used).

Properties

The 1-category of spans

Let$C$ be a category withpullbacks and let${\mathrm{Span}}_1(C):=(\mathrm{Span}(C){)}_{\sim 1}$ be the 1-category of objects of$C$ and isomorphism classes of spans between them as morphisms.

Then

• ${\mathrm{Span}}_1(C)$ is adagger category.

Next assume that$C$ is acartesian monoidal category. Then clearly${\mathrm{Span}}_1(C)$ naturally becomes amonoidal category itself, but more: then

• ${\mathrm{Span}}_1(C)$ is adagger compact category.

Universal property of the bicategory of spans

We discuss theuniversal property that characterizes 2-categories of spans.

For$C$ be acategory withpullbacks, write

1. ${\mathrm{Span}}_2(C)≔(\mathrm{Span}(C){)}_{\sim 2}$ for theweak 2-category of objects of$C$, spans as morphisms, and maps between spans as 2-morphisms,

2. ${\eta }_C:C\to {\mathrm{Span}}_2(C)$ for the functor given by:

Now let

1. $K$ be anybicategory

2. $F,G:C\to K$ befunctors such that every map in$C$ is sent to a map in$K$ possessing aright adjoint and satisfying theBeck-Chevalley Condition for anycommutative square in$K$,

3. $\alpha :F\to G$ be anatural transformation.

Then:

Limits and colimits

Since a category of spans/correspondences$\mathrm{Corr}(𝒞)$ is evidentlyequivalent to itsopposite category, it follows that to the extent thatlimits exists they are alsocolimits and vice versa.

If the underlying category$𝒞$ is anextensive category, then thecoproduct/product in$\mathrm{Corr}(𝒞)$ is given by thedisjoint union in$𝒞$. (See alsothis MO discussion).

More generally, everyvan Kampen colimit in$𝒞$ is a (co)limit in$\mathrm{Corr}(𝒞)$ — and conversely, this property characterizes van Kampen colimits. (Sobocinski-Heindel 11).

Relation to relations

Correspondences may be seen as generalizations ofrelations. A relation is acorrespondence which is(-1)-truncated as amorphism into thecartesian product. See atrelation and atRel for more on this.

Closure

When$E$ is alocally cartesian closed category,$\mathrm{Span}(E)$ is aclosed bicategory: see there for details.

Examples

• Spans inFinSet behave like thecategorification ofmatrices with entries in thenatural numbers: for$X_1\leftarrow N\to X_2$ a span of finite sets, thecardinality of thefiber$X_{x_1,x_2}$ over any two elements$x_1\in X_1$ and$x_2\in X_2$ plays the role of the corresponding matrix entry. Under this identification composition of spans indeed corresponds to matrix multiplication. This implies that the category of spans of finite sets is equivalent to theLawvere theory of commutative monoids, that is, to thePROP for the free bicommutativebialgebra. Spans over finite sets is arig category with respect to the tensor products induced by the coproduct and product in FinSet. The coproduct in FinSet remains the coproduct, but the product becomes the bilineartensor product of modules.

• TheBurnside category is essentially the category of correspondences inG-sets for$G$ afinite group.

• Acobordism$\Sigma$ from${\Sigma }_{\mathrm{in}}$ to${\Sigma }_{\mathrm{out}}$ is an example of a cospan${\Sigma }_{\mathrm{in}}\to \Sigma \leftarrow {\Sigma }_{\mathrm{out}}$ in the category ofsmooth manifolds. However, composition of cobordisms is not quite the pushout-composition of these cospans: to make the composition be asmooth manifold again some extra technical aspects must be added (“collars”).

• Inprequantum field theory (see there for details), spans ofstacks modeltrajectories offields.

• Thecategory of Chow motives has asmorphismsequivalence classes oflinear combinations of spans ofsmoothprojective varieties.

• TheWeinstein symplectic category has as morphismsLagrangian correspondences betweensymplectic manifolds.

  More generallysymplectic dual pairs are correspondences betweenPoisson manifolds.

• Cospans of homomorphisms ofC*-algebras represent morphisms inKK-theory (by Cuntz’ result).

• Correspondences offlag manifolds play a role astwistor correspondences, see atSchubert calculus – Correspondences and athorocycle correspondence

• TheFourier-Mukai transform is a pull-push operation through correspondences equipped with objects in a cocycle given by an object in aderived category of quasi-coherent sheaves.

• Hecke correspondence

• Ahypergraph is a span from a set of vertices to a set of (hyper)edges.

Related concepts

• (∞,n)-category of spans.

• sink,cosink

• product,coproduct

• multispan

• correspondence type

• reflexive graph

A category of correspondences is a refinement of a categoryRel of relations. See there for more.

References

The terminology “span” appears on page 533 of:

• Nobuo Yoneda,On ext and exact sequences (PhD thesis), Journal of the Faculty of Science, Section I.8 University of Tokyo (1960) 507–576 [pdf,CiNii:naid/500000325773]

The$\mathrm{Span}(C)$ construction was introduced by Jean Bénabou (as an example of a bicategory) in

• Jean Bénabou, Introduction to Bicategories,Lecture Notes in Mathematics 47, Springer (1967), pp.1-77. (doi)

Bénabou cites an article by Yoneda (1954) for introducing the concept of span (in the category of categories).

An exposition discussing the role of spans inquantum theory:

• John Baez,Spans in quantum Theory (web,pdf,blog)

The relationship between spans andbimodules is briefly discussed in

• John Baez,Bimodules versus spans (blog)

The relation tovan Kampen colimits is discussed in

• Pawel Sobocinski, Tobias Heindel,Being Van Kampen is a universal property, (arXiv:1101.4594)

Theuniversal property of categories of spans is due to

• Claudio Hermida,Representable Multicategories, Advances in Mathematics,151 (2000), No. 2, 164-225, (doi:10.1006/aima.1999.1877)

and further discussed in:

• R. Dawson,Robert Paré,Dorette Pronk,Universal properties of Span, Theory and Appl. of Categories13, 2004, No. 4, 61-85,TAC,MR2005m:18002

• R. Dawson,Robert Paré,Dorette Pronk,The span construction, Theory Appl. Categ.24 (2010), No. 13, 302–377,TACMR2720187

• Charles Walker?,Universal properties of bicategories of polynomials, Journal of Pure and Applied Algebra 223.9 (2019): 3722-3777.

• Charles Walker?,Bicategories of spans as generic bicategories,arXiv:2002.10334 (2020).

See also Theorem 5.2.1 and 5.3.7 of:

• Paul Balmer, and Ivo Dell’Ambrogio.Mackey 2-functors and Mackey 2-motives.arXiv:1808.04902 (2018).

The structure of amonoidaltricategory on spans in2-categories is discussed in

• Alex Hoffnung,Spans in 2-Categories: A monoidal tricategory (arXiv:1112.0560)

Generally, an(∞,n)-category of spans is indicated in section 3.2 of

• Jacob Lurie,On the Classification of Topological Field Theories

Last revised on March 25, 2025 at 14:07:56. See thehistory of this page for a list of all contributions to it.