nLab free diagram

Redirected from "free diagrams".
Contents

Contents

Idea

A free diagram in a category π’ž\mathcal{C} is a particularly simple special case of the general concept of a diagram X β€’:β„β†’π’žX_\bullet \;\colon\; \mathcal{I} \to \mathcal{C}, namely the case where the shape ℐ\mathcal{I} of the diagram is a free category.

Many important types of limits and colimits are over free diagrams, for instance products/coproducts, equalizers/coequalizers, pullbacks/pushouts, sequential limits/sequential colimits.

Due to the simplicity of the concept of free diagrams, these types of limits and colimits may be discussed in a very low-brow way, without even making the concept of category and functor explicit. For this see the Exposition below.

Definition

Recall that

Definition

(diagram)

For π’ž\mathcal{C} a category, then a diagram in π’ž\mathcal{C} is

  1. a small category ℐ\mathcal{I} , the shape of the diagram;

  2. a functor X β€’:β„β†’π’žX_\bullet \;\colon\; \mathcal{I} \to \mathcal{C}.

Definition

(free category)

There is a free-forgetful adjunction

CatβŠ₯⟢Underlying⟡FreeDirGraph Cat \underoverset {\underset{Underlying}{\longrightarrow}} {\overset{Free}{\longleftarrow}} {\bot} DirGraph

between the 1-categories of categories and that of directed graphs.

A free category is one in the image of this left adjoint functor Free:DirGraphβ†’CatFree \colon DirGraph \to Cat (sometimes called a β€œpath category”).

Definition

(free diagram)

A free diagram in a category π’ž\mathcal{C} is a diagram in π’ž\mathcal{C} (def. ) whose shape is a free category (def. ).

In other words, a free diagram in π’ž\mathcal{C} is

  1. a directed graph II;

  2. a functor of the form X β€’:Free(I)β†’π’žX_\bullet \;\colon\; Free(I) \to \mathcal{C}.

Examples

Example

Types of free diagrams that are commonly encountered in practice, as well as the names of the limits/colimits over them are shown in the following table

shapes of free diagrams and the names of their limits/colimits

free diagramlimit/colimit
empty diagramterminal object/initial object
discrete diagramproduct/coproduct
parallel morphismsequalizer/coequalizer
span/cospanpullback,fiber product/pushout
tower/cotowersequential limit/sequential colimit

Exposition

We give an exposition of free diagrams, and their cones and limits, intentionally avoiding abstract category-theoretic language, expressing everything just in components. See also at limits and colimits by example.

For concreteness, we speak only of diagrams of sets and of topological spaces in the following:

Definition

(free diagram of sets/topological spaces)

A free diagram X β€’X_\bullet of sets or of topological spaces is

  1. a set {X i} i∈I\{ X_i \}_{i \in I} of sets or of topological spaces, respectively;

  2. for every pair (i,j)∈IΓ—I(i,j) \in I \times I of labels, a set {X i⟢f Ξ±X j} α∈I i,j\{ X_i \overset{ f_\alpha }{\longrightarrow} X_j\}_{\alpha \in I_{i,j}} of functions of of continuous functions, respectively, between these.

Example

(discrete diagram and empty diagram)

Let II be any set, and for each (i,j)∈IΓ—I(i,j) \in I \times I let I i,j=βˆ…I_{i,j} = \emptyset be the empty set.

The corresponding free diagrams (def. ) are simply a set of sets/topological spaces with no specified (continuous) functions between them. This is called a discrete diagram.

For example for I={1,2,3}I = \{1,2,3\} the set with 3-elements, then such a diagram looks like this:

X 1AAAX 2AAAX 3. X_1 \phantom{AAA} X_2 \phantom{AAA} X_3 \,.

Notice that here the index set may be empty set, I=βˆ…I = \emptyset, in which case the corresponding diagram consists of no data. This is also called the empty diagram.

Definition

(parallel morphisms diagram)

Let I={a,b}I = \{a, b\} be the set with two elements, and consider the sets

I i,j≔{{1,2} | (i=a)and(j=b) βˆ… | otherwise}. I_{i,j} \;\coloneqq\; \left\{ \array{ \{ 1,2 \} & \vert & (i = a) \,\text{and}\, (j = b) \\ \emptyset & \vert & \text{otherwise} } \right\} \,.

The corresponding free diagrams (def. ) are called pairs of parallel morphisms. They may be depicted like so:

X aAAAAA⟢f 2⟢f 1X b. X_a \underoverset {\underset{f_2}{\longrightarrow}} {\overset{f_1}{\longrightarrow}} {\phantom{AAAAA}} X_b \,.
Example

(span and cospan diagram)

Let I={a,b,c}I = \{a,b,c\} the set with three elements, and set

I i,j={{f 1} |(i=c)and(j=a) {f 2} |(i=c)and(j=b) βˆ… |otherwise I_{i ,j} = \left\{ \array{ \{f_1\} & \vert \, (i = c) \,\text{and}\, (j = a) \\ \{f_2\} & \vert \, (i = c) \,\text{and}\, (j = b) \\ \emptyset & \vert \, \text{otherwise} } \right.

The corresponding free diagrams (def. ) look like so:

X c f 1↙ β†˜ f 2 X a X b. \array{ && X_c \\ & {}^{\mathllap{f_1}}\swarrow && \searrow^{\mathrlap{f_2}} \\ X_a && && X_b } \,.

These are called span diagrams.

Similary, there is the cospan diagram of the form

X c f 1β†— β†– f 2 X a X b. \array{ && X_c \\ & {}^{\mathllap{f_1}}\nearrow && \nwarrow^{\mathrlap{f_2}} \\ X_a && && X_b } \,.
Example

(tower diagram)

Let I=β„•I = \mathbb{N} be the set of natural numbers and consider

I i,j≔{{f i,j} | i≀j βˆ… | otherwise I_{i,j} \;\coloneqq\; \left\{ \array{ \{f_{i,j}\} & \vert & i \leq j \\ \emptyset & \vert & \text{otherwise} } \right.

The corresponding free diagrams (def. ) are called tower diagrams. They look as follows:

X 0⟢Af 0,1AX 1⟢Af 1,2AX 2⟢Af 2,3AX 3βŸΆβ‹―. X_0 \overset{\phantom{A}f_{0,1} \phantom{A} }{\longrightarrow} X_1 \overset{\phantom{A} f_{1,2} \phantom{A} }{\longrightarrow} X_2 \overset{\phantom{A} f_{2,3} \phantom{A} }{\longrightarrow} X_3 \overset{}{\longrightarrow} \cdots \,.

Similarly there are co-tower diagram

X 0⟡Af 0,1AX 1⟡Af 1,2AX 2⟡Af 2,3AX 3βŸ΅β‹―. X_0 \overset{\phantom{A} f_{0,1} \phantom{A} }{\longleftarrow} X_1 \overset{\phantom{A} f_{1,2} \phantom{A}}{\longleftarrow} X_2 \overset{\phantom{A} f_{2,3} \phantom{A}}{\longleftarrow} X_3 \overset{}{\longleftarrow} \cdots \,.

\,

Definition

(cone over a free diagram)

Consider a free diagram of sets or of topological spaces (def. )

X β€’={X i⟢f Ξ±X j} i,j∈I,α∈I i,j. X_\bullet \,=\, \left\{ X_i \overset{f_\alpha}{\longrightarrow} X_j \right\}_{i,j \in I, \alpha \in I_{i,j}} \,.

Then

  1. a cone over this diagram is

    1. a set or topological space X˜\tilde X (called the tip of the cone);

    2. for each i∈Ii \in I a function or continuous function X˜⟢p iX i\tilde X \overset{p_i}{\longrightarrow} X_i

    such that

    • for all (i,j)∈IΓ—I(i,j) \in I \times I and all α∈I i,j\alpha \in I_{i,j} then the condition

      f α∘p i=p j f_{\alpha} \circ p_i = p_j

      holds, which we depict as follows:

      X˜ p i↙ β†˜ p j X i ⟢f Ξ± X j \array{ && \tilde X \\ & {}^{\mathllap{p_i}}\swarrow && \searrow^{\mathrlap{p_j}} \\ X_i && \underset{f_\alpha}{\longrightarrow} && X_j }
  2. a co-cone over this diagram is

    1. a set or topological space X˜\tilde X (called the tip of the co-cone);

    2. for each i∈Ii \in I a function or continuous function q i:X i⟢X˜q_i \colon X_i \longrightarrow \tilde X;

    such that

    • for all (i,j)∈IΓ—I(i,j) \in I \times I and all α∈I i,j\alpha \in I_{i,j} then the condition

      q j∘f α=q i q_j \circ f_{\alpha} = q_i

      holds, which we depict as follows:

      X i ⟢f Ξ± X j q iβ†˜ ↙ q j X˜. \array{ X_i && \overset{f_\alpha}{\longrightarrow} && X_j \\ & {}_{\mathllap{q_i}}\searrow && \swarrow_{\mathrlap{q_j}} \\ && \tilde X } \,.
Example

(solutions to equations are cones)

Let f,g:ℝ→ℝf,g \colon \mathbb{R} \to \mathbb{R} be two functions from the real numbers to themselves, and consider the corresponding parallel morphism diagram of sets (example ):

ℝAAAAA⟢f 2⟢f 1ℝ. \mathbb{R} \underoverset {\underset{f_2}{\longrightarrow}} {\overset{f_1}{\longrightarrow}} {\phantom{AAAAA}} \mathbb{R} \,.

Then a cone (def. ) over this free diagram with tip the singleton set *\ast is a solution to the equation f(x)=g(x)f(x) = g(x)

* const x↙ β†˜ const y ℝ AAAAA⟢f 2⟢f 1 ℝ. \array{ && \ast \\ & {}^{\mathllap{const_x}}\swarrow && \searrow^{\mathrlap{const_y}} \\ \mathbb{R} && \underoverset {\underset{f_2}{\longrightarrow}} {\overset{f_1}{\longrightarrow}} {\phantom{AAAAA}} && \mathbb{R} } \,.

Namely the components of the cone are two functions of the form

cont x,const y:*→ℝ cont_x, const_y \;\colon\; \ast \to \mathbb{R}

hence equivalently two real numbers, and the conditions on these are

f 1∘const x=const yAAAAf 2∘const x=const y. f_1 \circ const_x = const_y \phantom{AAAA} f_2 \circ const_x = const_y \,.
Definition

(limiting cone over a diagram)

Consider a free diagram of sets or of topological spaces (def. ):

{X i⟢f αX j} i,j∈I,α∈I i,j. \left\{ X_i \overset{f_\alpha}{\longrightarrow} X_j \right\}_{i,j \in I, \alpha \in I_{i,j}} \,.

Then

  1. its limiting cone (or just limit for short, also β€œinverse limit”, for historical reasons) is the cone

    { lim⟡ kX k p i↙ β†˜ p j X i ⟢f Ξ± X j} \left\{ \array{ && \underset{\longleftarrow}{\lim}_k X_k \\ & {}^{\mathllap{p_i}}\swarrow && \searrow^{\mathrlap{p_j}} \\ X_i && \underset{f_\alpha}{\longrightarrow} && X_j } \right\}

    over this diagram (def. ) which is universal among all possible cones, in that for

    { X˜ pβ€² i↙ β†˜ pβ€² j X i ⟢f Ξ± X j} \left\{ \array{ && \tilde X \\ & {}^{\mathllap{p'_i}}\swarrow && \searrow^{\mathrlap{p'_j}} \\ X_i && \underset{f_\alpha}{\longrightarrow} && X_j } \right\}

    any other cone, then there is a unique function or continuous function, respectively

    Ο•:X˜⟢lim⟢ iX i \phi \;\colon\; \tilde X \overset{}{\longrightarrow} \underset{\longrightarrow}{\lim}_i X_i

    that factors the given cone through the limiting cone, in that for all i∈Ii \in I then

    pβ€² i=p iβˆ˜Ο• p'_i = p_i \circ \phi

    which we depict as follows:

    X˜ βˆƒ!ϕ↓ β†˜ pβ€² i lim⟢ iX i ⟢p i X i \array{ \tilde X \\ {}^{\mathllap{ \exists !\, \phi}}\downarrow & \searrow^{\mathrlap{p'_i}} \\ \underset{\longrightarrow}{\lim}_i X_i &\underset{p_i}{\longrightarrow}& X_i }
  2. its colimiting cocone (or just colimit for short, also β€œdirect limit”, for historical reasons) is the cocone

    {X i ⟢f Ξ± X j q iβ†˜ ↙ q j lim⟢ iX i} \left\{ \array{ X_i && \overset{f_\alpha}{\longrightarrow} && X_j \\ & {}^{\mathllap{q_i}}\searrow && \swarrow^{\mathrlap{q_j}} \\ \\ && \underset{\longrightarrow}{\lim}_i X_i } \right\}

    under this diagram (def. ) which is universal among all possible co-cones, in that it has the property that for

    {X i ⟢f Ξ± X j qβ€² iβ†˜ ↙ qβ€² j X˜} \left\{ \array{ X_i && \overset{f_\alpha}{\longrightarrow} && X_j \\ & {}^{\mathllap{q'_i}}\searrow && \swarrow_{\mathrlap{q'_j}} \\ && \tilde X } \right\}

    any other cocone, then there is a unique function or continuous function, respectively

    Ο•:lim⟢ iX i⟢X˜ \phi \;\colon\; \underset{\longrightarrow}{\lim}_i X_i \overset{}{\longrightarrow} \tilde X

    that factors the given co-cone through the co-limiting cocone, in that for all i∈Ii \in I then

    qβ€² i=Ο•βˆ˜q i q'_i = \phi \circ q_i

    which we depict as follows:

    X i ⟢q i lim⟢ iX i qβ€² iβ†˜ ↓ βˆƒ!Ο• X˜ \array{ X_i &\overset{q_i}{\longrightarrow}& \underset{\longrightarrow}{\lim}_i X_i \\ & {}_{q'_i}\searrow & \downarrow^{\mathrlap{\exists ! \phi}} \\ && \tilde X }

\,

All the limits and colimits over the free diagram in the above list of examples have special names:

shapes of free diagrams and the names of their limits/colimits

free diagramlimit/colimit
empty diagramterminal object/initial object
discrete diagramproduct/coproduct
parallel morphismsequalizer/coequalizer
span/cospanpullback,fiber product/pushout
tower/cotowersequential limit/sequential colimit
Example

(initial object and terminal object)

Consider the empty diagram (def. ).

  1. A cone over the empty diagram is just an object XX, with no further structure or condition. The universal property of the limit β€œastβ€³overtheemptydiagramishencethatforeveryobject'' over the empty diagram is hence that for every object X,thereisauniquemapoftheform, there is a unique map of the form X \to \ast.Suchanobject. Such an object \ast$ is called a terminal object.

  2. A co.cone? over the empty diagram is just an object XX, with no further structure or condition. The universal property of the colimit β€œβ€³overtheemptydiagramishencethatforeveryobject'' over the empty diagram is hence that for every object X,thereisauniquemapoftheform, there is a unique map of the form 0 \to X.Suchanobject. Such an object \ast$ is called a initial object.

Example

(Cartesian product and coproduct)

Let {X i} i∈I\{X_i\}_{i \in I} be a discrete diagram (example ), i.e. just a set of objects.

  1. The limit over this diagram is called the Cartesian product, denoted ∏i∈IX i\underset{i \in I}{\prod} X_i;

  2. The colimit over this diagram is called the coproducts, denoted ∐i∈IX i\underset{i \in I}{\coprod} X_i.

Example

(equalizer)

Let

X 1⟢AAf 2AA⟢AAf 1AAX 2 X_1 \underoverset {\underset{\phantom{AA}f_2\phantom{AA}}{\longrightarrow}} {\overset{\phantom{AA}f_1\phantom{AA}}{\longrightarrow}} {} X_2

be a free diagram of the shape β€œpair of parallel morphisms” (example ).

A limit over this diagram according to def. is also called the equalizer of the maps f 1f_1 and f 2f_2. This is a set or topological space eq(f 1,f 2)eq(f_1,f_2) equipped with a map eq(f 1,f 2)⟢p 1X 1eq(f_1,f_2) \overset{p_1}{\longrightarrow} X_1, so that f 1∘p 1=f 2∘p 1f_1 \circ p_1 = f_2 \circ p_1 and such that if Yβ†’X 1Y \to X_1 is any other map with this property

Y ↓ β†˜ eq(f 1,f 2) ⟢p 1 X 1 ⟢AAf 2AA⟢AAf 1AA X 2 \array{ && Y \\ && \downarrow & \searrow \\ eq(f_1,f_2) &\overset{p_1}{\longrightarrow}& X_1 & \underoverset {\underset{\phantom{AA}f_2\phantom{AA}}{\longrightarrow}} {\overset{\phantom{AA}f_1\phantom{AA}}{\longrightarrow}} {} & X_2 }

then there is a unique factorization through the equalizer:

Y βˆƒ!↙ ↓ β†˜ eq(f 1,f 2) ⟢p 1 X 1 ⟢f 2⟢f 1 X 2. \array{ && Y \\ &{}^{\mathllap{\exists !}}\swarrow& \downarrow & \searrow \\ eq(f_1,f_2) &\overset{p_1}{\longrightarrow}& X_1 & \underoverset {\underset{f_2}{\longrightarrow}} {\overset{f_1}{\longrightarrow}} {} & X_2 } \,.

In example we have seen that a cone over such a pair of parallel morphisms is a solution to the equation f 1(x)=f 2(x)f_1(x) = f_2(x).

The equalizer above is the space of all solutions of this equation.

Example

(pullback/fiber product and coproduct)

Consider a cospan diagram (example )

Y ↓ f X ⟢g Z. \array{ && Y \\ && \downarrow^{\mathrlap{f}} \\ X &\underset{g}{\longrightarrow}& Z } \,.

The limit over this diagram is also called the fiber product of XX with YY over ZZ, and denoted XΓ—ZYX \underset{Z}{\times}Y. Thought of as equipped with the projection map to XX, this is also called the pullback of ff along gg

XΓ—XZ ⟢ Y ↓ (pb) ↓ f X ⟢g Z. \array{ X \underset{X}{\times} Z &\longrightarrow& Y \\ \downarrow &(pb)& \downarrow^{\mathrlap{f}} \\ X &\underset{g}{\longrightarrow}& Z } \,.

Dually, consider a span diagram (example )

Z ⟢g Y f↓ X \array{ Z &\overset{g}{\longrightarrow}& Y \\ {}^{\mathllap{f}}\downarrow \\ X }

The colimit over this diagram is also called the pushout of ff along gg, denoted XβŠ”ZYX \underset{Z}{\sqcup}Y:

Z ⟢g Y f↓ (po) ↓ X ⟢ XβŠ”ZY \array{ Z &\overset{g}{\longrightarrow}& Y \\ {}^{\mathllap{f}}\downarrow &(po)& \downarrow \\ X &\longrightarrow& X \underset{Z}{\sqcup} Y }

\,

Here is a more explicit description of the limiting cone over a diagram of sets:

Proposition

(limits and colimits of sets)

Let {X i⟢f αX j} i,j∈I,α∈I i,j\left\{ X_i \overset{f_\alpha}{\longrightarrow} X_j \right\}_{i,j \in I, \alpha \in I_{i,j}} be a free diagram of sets (def. ). Then

  1. its limit cone (def. ) is given by the following subset of the Cartesian product ∏i∈IX i\underset{i \in I}{\prod} X_i of all the sets X iX_i appearing in the diagram

    lim⟡ iX iβ†ͺAAA∏i∈IX i \underset{\longleftarrow}{\lim}_i X_i \,\overset{\phantom{AAA}}{\hookrightarrow}\, \underset{i \in I}{\prod} X_i

    on those tuples of elements which match the graphs of the functions appearing in the diagram:

    lim⟡ iX i≃{(x i) i∈I|βˆ€i,j∈Iα∈I i,j(f Ξ±(x i)=x j)} \underset{\longleftarrow}{\lim}_{i} X_i \;\simeq\; \left\{ (x_i)_{i \in I} \,\vert\, \underset{ {i,j \in I} \atop { \alpha \in I_{i,j} } }{\forall} \left( f_{\alpha}(x_i) = x_j \right) \right\}

    and the projection functions are p i:(x j) j∈I↦x ip_i \colon (x_j)_{j \in I} \mapsto x_i.

  2. its colimiting co-cone (def. ) is given by the quotient set of the disjoint union βŠ”i∈IX i\underset{i \in I}{\sqcup} X_i of all the sets X iX_i appearing in the diagram

    βŠ”i∈IX i⟢AAAlim⟢ i∈IX i \underset{i \in I}{\sqcup} X_i \,\overset{\phantom{AAA}}{\longrightarrow}\, \underset{\longrightarrow}{\lim}_{i \in I} X_i

    with respect to the equivalence relation which is generated from the graphs of the functions in the diagram:

    lim⟢ iX i≃(βŠ”i∈IX i)/((x∼xβ€²)⇔(βˆƒi,j∈Iα∈I i,j(f Ξ±(x)=xβ€²))) \underset{\longrightarrow}{\lim}_i X_i \;\simeq\; \left( \underset{i \in I}{\sqcup} X_i \right)/ \left( (x \sim x') \Leftrightarrow \left( \underset{ {i,j \in I} \atop { \alpha \in I_{i,j} } }{\exists} \left( f_\alpha(x) = x' \right) \right) \right)

    and the injection functions are the evident maps to equivalence classes:

    q i:x i↦[x i]. q_i \;\colon\; x_i \mapsto [x_i] \,.
Proof

We dicuss the proof of the first case. The second is directly analogous.

First observe that indeed, by consturction, the projection maps p ip_i as given do make a cone over the free diagram, by the very nature of the relation that is imposed on the tuples:

{(x k) k∈I|βˆ€i,j∈Iα∈I i,j(f Ξ±(x i)=x j)} p i↙ β†˜ p j X i ⟢f Ξ± X j. \array{ && \left\{ (x_k)_{k \in I} \,\vert\, \underset{ {i,j \in I} \atop { \alpha \in I_{i,j} } }{\forall} \left( f_{\alpha}(x_i) = x_j \right) \right\} \\ & {}^{\mathllap{p_i}}\swarrow && \searrow^{\mathrlap{p_j}} \\ X_i && \underset{f_\alpha}{\longrightarrow} && X_j } \,.

We need to show that this is universal, in that any other cone over the free diagram factors universally through it. First consider the case that the tip of a give cone is a singleton:

* pβ€² i↙ β†˜ pβ€² j X i ⟢f Ξ± X j. \array{ && \ast \\ & {}^{\mathllap{p'_i}}\swarrow && \searrow^{\mathrlap{p'_j}} \\ X_i && \underset{f_\alpha}{\longrightarrow} && X_j } \,.

This is hence equivalently for each i∈Ii \in I an element xβ€² i∈X ix'_i \in X_i, such that for all i,j∈Ii, j \in I and α∈I i,j\alpha \in I_{i,j} then f Ξ±(xβ€² i)=xβ€² jf_\alpha(x'_i) = x'_j. But this is precisely the relation used in the construction of the limit above and hence there is a unique map

*⟢{(x k) k∈I|βˆ€i,j∈Iα∈I i,j(f Ξ±(x i)=x j)} \ast \longrightarrow \left\{ (x_k)_{k \in I} \,\vert\, \underset{ {i,j \in I} \atop { \alpha \in I_{i,j} } }{\forall} \left( f_{\alpha}(x_i) = x_j \right) \right\}

such that for all i∈Ii \in I we have

* ↓ β†˜ pβ€² i {(x k) k∈I|βˆ€i,j∈Iα∈I i,j(f Ξ±(x i)=x j)} ⟢p i X i \array{ \ast \\ \downarrow & \searrow^{\mathrlap{p'_i}} \\ \left\{ (x_k)_{k \in I} \,\vert\, \underset{ {i,j \in I} \atop { \alpha \in I_{i,j} } }{\forall} \left( f_{\alpha}(x_i) = x_j \right) \right\} &\underset{p_i}{\longrightarrow}& X_i }

namely that map is the one that picks the element (xβ€² i) i∈I(x'_i)_{i \in I}.

This shows that every cone with tip a singleton factors uniquely through the claimed limiting cone. But then for a cone with tip an arbitrary set YY, this same argument applies to all the single elements of YY.

Last revised on May 8, 2017 at 16:51:45. See the history of this page for a list of all contributions to it.