nLab span

This entry is about the notion of spans/correspondences which generalizes that of relations. For spans in vector spaces or modules, see linear span.

Definition

In set theory

In set theory, a span or correspondence between sets $A$ and $B$ is a set $C$ with a function $R:C \to A \times B$ to the product set $A \times B$. A span between a set $A$ and $A$ itself is a directed pseudograph, which is used to define categories in set theory.

In category theory

In any category $C$, a span, or roof, or correspondence, from an object $x$ to an object $y$ is a diagram of the form

$$\array{ && s \\ & {}^{f}\swarrow && \searrow^{g} \\ x &&&& y }$$

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

This diagram 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 binary relation.

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 the opposite category $C^op$ is called a co-span in $C$.

A span that has a cocone is called a coquadrable span.

In dependent type theory

In dependent type theory, there is a distinction between a span, a multivalued partial function, and a correspondence:

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

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

• A correspondence between types $A$ and $B$ is a type family $x:A, y:B \vdash R(x, y)$.

However, from any one of the above structures, one could get the other two structures, provided one has identity types and dependent pair types in the dependent type theory. Given a type family $x:A \vdash P(x)$, let $z:\sum_{x:A} P(x) \vdash \pi_1(z):A$ and $z:\sum_{x:A} P(x) \vdash \pi_2(z):P(\pi_1(z))$ be the dependent pair projections for the dependent pair type $\sum_{x:A} P(x)$.

• From every span one could get a multivalued partial function by defining the type family $x:A \vdash P(x)$ as $P(x) \coloneqq \sum_{y:C} g(y) =_A x$ and the family of elements $x:A, p:P(x) \vdash f(x, p):B$ as $f(x, p) \coloneqq h(\pi_1(x))$.

• From every multivalued partial function one could get a span by defining the type $C$ as $C \coloneqq \sum_{x:A} P(x)$ and the family of elements $x:C \vdash g(x):A$ as $g(x) \coloneqq \pi_1(x)$.

• From every multivalued partial function one could get a correspondence by defining the type family $x:A, y:B \vdash R(x, y)$ as $R(x, y) \coloneqq \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 \vdash P(x)$ as $P(x) \coloneqq \sum_{y:B} R(x, y)$, and the family of elements $x:A, p:P(x) \vdash h(x, p):B$ as $h(x, p) \coloneqq \pi_1(p)$

• From every span one could get a correspondence by defining the type family $x:A, y:B \vdash R(x, y)$ as $R(x, y) \coloneqq \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 \coloneqq \sum_{x:A} \sum_{y:B} R(x, y)$, the family of elements $z:C \vdash g(z):A$ as $g(z) \coloneqq \pi_1(z)$, and the function $z:C \vdash h(z):B$ as $h(z) \coloneqq \pi_1(\pi_2(z))$

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

$$(E \circ D, z:E \circ D \vdash g_{E \circ D}(z):A, z:E \circ D \vdash h_{E \circ D}(z):C)$$

defined by

$$E \circ D \coloneqq \sum_{x:D} \sum_{y:E} h_D(x) =_B g_E(y)$$

$$z:E \circ D \vdash g_{E \circ D}(z) \coloneqq g_D(\pi_1(z))$$

$$z:E \circ D \vdash h_{E \circ D}(z) \coloneqq h_E(\pi_1(\pi_2(\pi_1(z))(z)))$$

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

$$(S \circ R)(x, z) \coloneqq \sum_{y:B} R(x, y) \times S(y, z)$$

In synthetic $(\infty,1)$-category theory

In simplicial type theory, binary parametric observational type theory, and other type theoretic approaches to synthetic $(\infty,1)$-category theory, a span in a synthetic $(\infty,1)$-category $C$ can be defined as the following:

• a record consisting of objects (elements of types) $x:C$, $y:C$, and $z:C$ and morphisms (elements of hom types) $f:\mathrm{hom}_C(x, y)$ and $h:\mathrm{hom}_C(x, z)$

• a function $k:\Lambda_2^2 \to C$ from the (2,2)-horn type $\Lambda_2^2$ to $C$, where $\Lambda_2^2$ is defined in terms of the directed interval as the type of pairs of elements $i, j:\mathbb{I}$ such that $i = 0$ or $j = 0$.

$$\Lambda_2^2 \coloneqq \sum_{i:\mathbb{I}} \sum_{j:\mathbb{I}} (i = 0) \vee (j = 0)$$

The walking span

The walking span or walking correspondence or (2,2)-horn category is the category $\Lambda_2^2$ which consists of three objects $0, 1, 2 \in \Lambda_2^2$ and two morphisms $h_{01}:\mathrm{hom}_{\Lambda_2^2}(0, 1)$ and $h_{02}:\mathrm{hom}_{\Lambda_2^2}(0, 2)$.

The category $\Lambda_2^2$ is also called the (2,2)-horn preorder or the (2,2)-horn poset because $\Lambda_2^2$ can be shown to be a poset.

Every span in a category $C$ is represented by a functor $F:\Lambda_2^2 \to C$ from the walking span to $C$.

In type theoretic approaches to synthetic $(\infty,1)$-category theory, the (2,2)-horn type $\Lambda_2^2$ defined above plays the role of the walking span.

Properties

Relation to relations

Correspondences may be seen as generalizations of relations. A relation is a correspondence which is (-1)-truncated as a morphism into the cartesian product. See at relation and at Rel for more on this.

Left quotients

Following the notion of a left quotient of two elements in a monoid, we can define in category the notion of a left quotient of a span in a category.

A left quotient of a span $f:\mathrm{hom}_A(x, y)$ and $h:\mathrm{hom}_A(x, z)$ is a morphism $g:\mathrm{hom}_A(y, z)$ such that $h$ is the unique composite of $f$ and $g$, i.e. $g \circ f = h$.

Given a morphism $f:\mathrm{hom}_A(x, y)$, the span $(\mathrm{id}_x, f)$ is always left divisible with left quotient $f$. A retraction is a left quotient of the span $(f, \mathrm{id}_x)$.

The bicategory of spans

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

$$\array{ && s &&&& t \\ & {}^{f}\swarrow && \searrow^{g} & & {}^{h}\swarrow && \searrow^{i} \\ x &&&& y &&&& z }$$

we can take a pullback in the middle:

$$\array{ &&&& s \times_y t \\& && {}^{p_s}\swarrow && \searrow^{p_t} \\ && s &&&& t \\ & {}^{f}\swarrow && \searrow^{g} & & {}^{h}\swarrow && \searrow^{i} \\ x &&&& y &&&& z }$$

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

$$\array{ && s \times_y t \\ & {}^{f p_s}\swarrow && \searrow^{i p_t} \\ x &&&& z }$$

This way of composing spans lets us define a bicategory Span$(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 nontrivial associator: composition of spans is not strictly associative, because pullbacks are defined only up to canonical isomorphism. A naturally defined strict 2-category which is equivalent to $Span(C)$ is the strict 2-category of linear polynomial functors between slice categories of $C$.

(Note that we must choose a specific pullback when defining the composite of a pair of morphisms in $Span(C)$, if we want to obtain a bicategory as traditionally defined; this requires the axiom 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 an anabicategory or an opetopic bicategory?.)

We can also obtain a pseudo-double category?, whose loose structure is as above, whose tight morphisms are functions, and whose cells are commuting diagrams,

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

The 1-category of spans

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

Then

• $Span_1(C)$ is a dagger category.

Next assume that $C$ is a cartesian monoidal category. Then clearly $Span_1(C)$ naturally becomes a monoidal category itself, but more: then

• $Span_1(C)$ is a dagger compact category.

Universal property of the bicategory of spans

We discuss the universal property that characterizes 2-categories of spans.

For $C$ be a category with pullbacks, write

1. $Span_2(C) \coloneqq (Span(C))_{\sim2}$ for the weak 2-category of objects of $C$, spans as morphisms, and maps between spans as 2-morphisms,

2. $\eta_C: C \rightarrow Span_2(C)$ for the functor given by:

Now let

1. $K$ be any bicategory

2. $F, G \,\colon\, C \rightarrow K$ be functors such that every map in $C$ is sent to a map in $K$ possessing a right adjoint and satisfying the Beck-Chevalley Condition for any commutative square in $K$,

3. $\alpha \,\colon\, F \rightarrow G$ be a natural transformation.

Then:

Proposition

(universal property of the bicategory of spans)
The following holds:

1. $\eta_C$ is universal among such functors $F$, i.e. $F$ as above factors as $F = \hat{F} \circ \eta_C$ for a functor $\hat{F} \,\colon\, Span_2(C) \rightarrow K$ which is unique up to isomorphism.

2. There exists a unique lax natural transformation: $\hat{\alpha} \,\colon\, \hat{F} \rightarrow \hat{G}$ such that $\hat{\alpha} \eta_C = \alpha$.

3. Let $x, y$ be objects in $C$ and $f: x \rightarrow y$ be a morphism in $C$. If $(\alpha_x, \alpha_y)$ induce a pseudo-map of adjoints $F(f) \dashv (Ff)^* \rightarrow G(f) \dashv (Gf)^*$, then $\hat{\alpha}$ is a pseudonatural transformation

Furthermore, if we denote $Pbk$ as the 2-category of categories with pullbacks, pullback-preserving functors, and equifibered natural transformations and $BiCat$ as the tricategory of bicategories, $Span(-): Pbk \rightarrow BiCat$ is well-defined as a functor.

This is due to Hermida 1999.

Limits and colimits

Since a category of spans/correspondences $Corr(\mathcal{C})$ is evidently equivalent to its opposite category, it follows that to the extent that limits exists they are also colimits and vice versa.

If the underlying category $\mathcal{C}$ is an extensive category, then the coproduct/product in $Corr(\mathcal{C})$ is given by the disjoint union in $\mathcal{C}$. (See also this MO discussion).

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

Closure

When $E$ is a locally cartesian closed category, $Span(E)$ is a closed bicategory: see there for details.

Examples

• Spans in FinSet behave like the categorification of matrices with entries in the natural numbers: for $X_1 \leftarrow N \to X_2$ a span of finite sets, the cardinality of the fiber $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 the Lawvere theory of commutative monoids, that is, to the PROP for the free bicommutative bialgebra. Spans over finite sets is a rig 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 bilinear tensor product of modules.

• The Burnside category is essentially the category of correspondences in G-sets for $G$ a finite group.

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

• In prequantum field theory (see there for details), spans of stacks model trajectories of fields.

• The category of Chow motives has as morphisms equivalence classes of linear combinations of spans of smooth projective varieties.

• The Weinstein symplectic category has as morphisms Lagrangian correspondences between symplectic manifolds.

  More generally symplectic dual pairs are correspondences between Poisson manifolds.

• Cospans of homomorphisms of C*-algebras represent morphisms in KK-theory (by Cuntz’ result).

• Correspondences of flag manifolds play a role as twistor correspondences, see at Schubert calculus – Correspondences and at horocycle correspondence

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

• Hecke correspondence

• A hypergraph 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

• horn

• span, cospan

• composable pair

• composite

• commutative triangle

• isomorphism

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

• walking structure

  • the boolean domain $2 \coloneqq \partial \Delta^1$; i.e. the walking pair of objects

  • the directed interval category $I \coloneqq \Delta^1$; i.e. the walking morphism

  • the (2,0)-horn category $\Lambda_0^2$; i.e. the walking cospan

  • the (2,1)-horn category $\Lambda_1^2$; i.e. the walking composable pair

  • the (2,2)-horn category $\Lambda_2^2$; i.e. the walking span

  • the 2-simplex category $\Delta^2$; i.e. the walking commutative triangle

  • the walking parallel pair

  • the walking isomorphism

  • Adj; i.e. the walking adjunction

  • the walking equivalence

  • the walking adjoint equivalence

  • the walking 2-isomorphism with trivial boundary

  • the syntactic category of a theory $T$; i.e. the walking $T$-model

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 $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 in quantum theory:

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

The relationship between spans and bimodules is briefly discussed in

• John Baez, Bimodules versus spans (blog)

The relation to van Kampen colimits is discussed in

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

The universal 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 Categories 13, 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, TAC MR2720187

• 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 a monoidal tricategory on spans in 2-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