**Limits and colimits in topology and order theory **
We *do not* ask that the spaces be *T*_{0}, the preorders antisymmetric
or the groupoids skeletal, as this destroys the adjunction (g)
- a quotient such as that in Proposition 3.1.10
must be applied to the colimits.

1 (#1) ^

THEOREM 7.4.1 These categories have limits and colimits.

**(a)**- Any limit of preorders is the limit of the underlying sets, equipped
with some order; similarly the vertex classes of a limit of relations,
graphs, categories or groupoids (from b).
**(b)**- Moreover the hom-sets are also calculated as limits, and the
order relation as a conjunction (from d).
**(c)**- Any limit of spaces is the limit of the underlying sets, equipped
with some topology (from b).
**(d)**- The limit of a diagram of discrete relations,
*etc*is discrete (from a). This is not so for spaces, as it is not possible to define the connected components of an arbitrary topological space.omitted diagram environment omitted diagram environment omitted diagram environment

**(e)**- A colimit of preorders is the colimit of the underlying sets,
equipped with some
*pre*order; also the vertex classes of graphs,*etc*(from g). **(f)**- A colimit of spaces is the colimit of the underlying sets, equipped
with some topology or
*pre*order (from g). **(g)**- W:
**Sp**®**Frm**^{op}and*pts*:**Frm**®**Sp**^{op}(Exercise 4.14) are symmetrically adjoint on the right, so they send colimits to limits. The frame of open sets of a colimit is the limit of the frames of open sets of the spaces; in particular the Aleksandrov topology (whose open sets are the upper sets) on a colimit of preorders and the Scott topology (Proposition 3.4.9) on dcpos are found as limits (from e). **(h)**- A colimit of discrete spaces is discrete (from b).
**(i)**- The set of connected components of a colimit of graphs
*etc*is the colimit of those of the graphs in the diagram (from a). **(j)**- The space of points of a limit of locales is the limit of the spaces of points of the locales themselves (from e). []

REMARK 7.4.2 It remains to find the topology on a limit.

**(a)**- As we know the underlying set of a limit of spaces, identifying
the topology is reduced to a lattice-theoretic problem: it is the coarsest
that makes the projections continuous.
**(b)**- Similarly, a colimit carries the finest topology making the
inclusions continuous. (In fact these properties may also be expressed
in pure category theory, by observing that the points functor
**Sp**®**Set**is a bifibration, Definition 9.2.6(e).) **(c)**- Limits of locales (colimits of frames) are not in general the same as the corresponding limits of spaces; they must be found using generators and relations, as below. Nuclei (Example 3.9.10(a)) give the most efficient technique; see [Joh82] for more detail. []

REMARK 7.4.3
Van Kampen's Theorem 5.4.8 may also be formulated
as the preservation of colimits by a left adjoint. The right adjoint takes
a groupoid or category to its ** nerve**, which is a simplicial complex
whose 0- and 1-cells are the objects and morphisms, and whose higher

**Generators and relations **
We can exploit the relationship between left adjoints and colimits to construct
free algebras using coequalisers and *vice versa* .

THEOREM 7.4.4
Every finitary equational algebraic theory *L* has a free algebra
*FX*/*R* on any set *X* of generators for any set *R* of relations.

PROOF: We can only really sketch this complicated construction.

**(a)**- Forget the sorts and laws of
*L*and the relations*R*; **(b)**- add the generators
*X*as nullary operation-symbols to the theory; **(c)**- Proposition 6.1.11 and Example
6.2.7 give equationally free algebras;
**(d)**- the minimal subalgebra of an equationally free algebra, consisting
of raw terms, is well founded and parsable; recall that it may also be
constructed either as the colimit È
*T*^{n}(Æ), or as the union of all extensional well founded*T*-coalgebras (Section 6.3); **(e)**- it satisfies the recursion scheme by Theorem
6.3.13;
**(f)**- the sorts are restored by restricting to the well formed formulae
(Proposition 6.2.6); let \LeftAdjoint
_{0}*X*be the free algebra for the theory*L*_{0}(known as the) obtained by forgetting the laws of*signature**L*; **(g)**- the congruence
*K*is generated from the laws and relations*R*; **(h)**- the required free algebra
*FX*/*R*is the quotient*Q*= \LeftAdjoint_{0}*X*/*K*by this equivalence relation.

Let us spell out the last step; notice that it treats ``general'' laws and
``particular'' relations in the same way, so without loss of generality
*R* includes the laws of *L*. Each member of *R* relates two raw terms,
so we have a parallel pair of functions *R*\rightrightarrows \LeftAdjoint_{0}*X*.
Let *K* be the congruence generated from *R* in step (g), and *Q* its quotient
in **Set**^{S} .

omitted diagram environment

For Theorem 5.6.9, the theory must be finitary
in order to define the operations on the quotient, making it a coequaliser
in **Mod**(*L*). Any algebra Q for the equational
theory *L* is *a fortiori* a model of the free theory *L*_{0},
and so it has a unique homomorphism \LeftAdjoint_{0}*X*® Q. That
it satisfies the laws is exactly to say that the composites with
*R*\rightrightarrows \LeftAdjoint_{0} *X* are equal. The composite homomorphisms
with *K*\rightrightarrows \LeftAdjoint_{0}*X* are also equal because *K*
is the congruence-closure of *R*. Hence there is a mediating function
*Q*® Q, and this is a homomorphism. []

We shall discuss the way in which *K* is generated shortly.

EXAMPLE 7.4.5
Recall from Example 4.6.3(i) that a category
with a given set *O* of objects is an algebra for a theory with *O*^{2} sorts,
*O*+*O*^{3} operation-symbols and *O*^{2}+*O*^{2}+*O*^{4} laws. Theorem
6.2.8(a) constructed the free such algebra
on an oriented graph (with the same set *O* of nodes). By Theorem
7.4.4 we now have the free category on any elementary
sketch (Theorem 4.2.12). []

EXAMPLE 7.4.6
Every algebra presents itself by its *multiplication table*. It
is generated by its own elements *a* Î *A*, subject to the relations that each
depth 1 expression *r*([(*a*)\vec]) Î *TA* (Definition
6.1.1) is identified with its value
\opr_{A}([(*a*)\vec]) º \ev_{A}(*r*([(*a*)\vec])) Î *A* ( *cf* the ambiguity in the usage
of the word *law* mentioned in Remarks 1.2.2
and 6.6.4).

omitted diagram environment

This is the ** canonical language** for the algebra

Daniel Kan's original example of an adjoint derived the tensor product
*M*Ä(-) *à la* Remark 7.2.4 from the
internal hom ( = )Ä*M*. As such it is constructed from generators
and relations.

EXAMPLE 7.4.7
The tensor product of two modules *M* and *N* for a commutative ring *R*
is the free *R*-module generated by symbols \qq (*m*,*n*) (for *m* Î *M*,
*n* Î *N*) subject to relations such as *r*\qq (*m*,*n*) = \qq (*rm*,*n*) and
\qq (*m*,\argn_{1}+\argn_{2}) = \qq (*m*,\argn_{1})+\qq (*m*,\argn_{2})
( *cf* Example 3.9.10(e)). []

**Computing colimits **
Conversely, we may exploit the self-presentation of algebras for finitary
algebraic theories. If we had a convincing notion of morphism of languages
( *cf* Remark 7.1.13(a)), these results
would simply be applications of the fact that *Cn*^{×}_{(-)},
being a left adjoint, preserves colimits. Indeed the first is plausibly
the coproduct of theories.

LEMMA 7.4.8
Let *A* and *B* be generated by *X* and *Y* respectively, subject to the relations
*R* and *S*.

omitted diagram environment

Then the algebra-coproduct *A*+_{A}*B* is generated by the disjoint
union *X*+_{S}*Y* *modulo* *R*+_{S}*S*. []

LEMMA 7.4.9
With similar notation, the algebra-coequaliser of *B*\rightrightarrows *A*
is generated by *X* subject to relations *R*+*P*.

omitted diagram environment

PROOF: The relations *S* for *B* are irrelevant: *Q* is also the
coequaliser of *FY*\rightrightarrows *A*, where *FY* is the algebra *
freely* generated by the given generators of *B*. Then *Y* may be viewed as
an additional system of relations, but these are on *A*, not *FX* as required,
so let *P*® (*FX*)^{2} be the pullback of *Y*® *A*^{2}. (See
Exercise 5.53 for why this is not just the pullback
of *Y*\rightrightarrows *A*.) []

Some of these manipulations of colimits have been implemented in ML by David Rydeheard [RB88].

**Treating relations as another theory **
These constructions are not very tractable: they mix the fundamentally
incompatible techniques of structural recursion and quotients by equivalence
relations. We cannot expect any better (such as from the General Adjoint
Functor Theorem 7.3.12), because
**while** programs can be interpreted with coequalisers. From the point of view
of machine representation, we have to accept generators and relations as
a legitimate way of naming objects. We must also resort to these methods to
find coproducts of groups, and so the fundamental groupoids of spaces obtained
by surgery *à la* van Kampen (Theorem 5.4.8)
.

Nevertheless some unification is possible, by treating both the creation
of raw terms and their identifications under the laws in the same way, as generative
processes, but at different levels. (We shall have to do this for generalised
algebraic theories in Remark 8.4.2.) We should
take the principle of interchangeability more seriously, adding a categorical
dimension *below* that which we're used to considering in mathematics:
individuals can only be represented by tokens, with interchange arrows
between them, *cf* the comments in Definition
1.2.12 and Example
2.4.8.

REMARK 7.4.10
The congruence *K* may be generated in various ways:

**(a)**- It is the closure of (the image of)
*R*Ì*A*^{2}= (\LeftAdjoint_{0}*X*)^{2}under{(\arga _{1},\argb_{2}),(\arga_{2},\argb_{2}),¼,(\arga_{k}, \argb_{k})} \triangleright (\opr_{A}(® *a*

), \opr _{A}(® *b*

)) ( *r*Î W) It is not possible to separate this into two processes of generating an equivalence relation and generating anÆ\triangleright ( *a*,*a*) {(*a*,*b*)}\triangleright (*b*,*a*) {(*a*,*b*),(*b*,*c*)}\triangleright (*a*,*c*).*L*-subalgebra. **(b)**- It is the free algebra on
*R*for a more complicated theory than*L*, namely with*operation-symbols*for each of the closure conditions above, including reflexivity, symmetry and transitivity. **(c)**- This theory may be chosen to have all of the laws induced by being
a congruence on this particular algebra
*A*, or may instead have no laws at all (*cf*Lemma 7.4.9), making it a*free*theory. Another option is*the theory of groupoids in*. []**Mod**(*L*_{0})

Definition 8.1.11 and Example
9.2.4(h) suggest a framework in which such a
theory can be formulated, using dependent types and indexed categories.
The next section uses self-presentation to give a concise functorial description
of algebraic theories. Section 7.6 defines the self-
presentation or *canonical language* of any semantic category using
the type theory corresponding to the structure it has.