ñòð. 9 
Â¡!
d1
the cone
d 0 a
c
d1 d
? ?

a b
d
It follows from Exercise 5 of Section 8.4 that if d has a kernel pair, then d is
a regular epimorphism if and only if it is the coequalizer of that kernel pair.
The addition of this cone thus adds no new data, at least in the case of models
in a category with Â¯nite limits and coequalizers. The preservation of the kernel
pair and the two arrows by homomorphisms of models is automatic, given the
universal mapping properties of limits.
The point of these considerations is that a regular sketch can be described
as one in which one can specify any kind of Â¯nite limits and that any particular
arrow is a coequalizer of some pair, without having to specify (or preserve in an
arrow between models) what pair of arrows it coequalizes.
One of the things we want a sketch to do is minimize the number of items { or
amount of information { that has to be speciÂ¯ed and maximize the amount that is
implicit in the sketch. Thus we want to be able to say that an arrow is a regular
epimorphism (that is, coequalizer of some pair of arrows) without specifying what
pair it coequalizes. In the preceding discussion, we described a way to do this: to
observe that a regular epi is a coequalizer of its own kernel pair and that the kernel
pair can be calculated. There is a price to pay in solving the problem in this way,
since this works only when you form models in a category that has that kernel pair.
An alternative approach would be to simply add regular epi to the list of primitives
that a sketch can make use of, so that one could require than an arrow be a regular
epi, without having to specify the arrows it coequalizes, in a category that may or
may not have pullbacks. This is an example of expanding the concept of sketch to
allow speciÂ¯cation of constructions other than commutative diagrams, limits and
colimits. (References to generalized sketches are given at the end of this chapter.)
As an example, we construct a sketch for reÂ°exive graphs { graphs with the
property that there is at least one loop on each node. The problem that arose
in 4.6.9 that homomorphisms had to take certain speciÂ¯c loops to other speciÂ¯c
loops does not arise in this construction.
24 More about sketches
We take the sketch for graphs with nodes n and a and arrows source; target : a
Â¡ n. We add a new type r with a cone
!
source
Â¡Â¡ Â¡ ! n
Â¡Â¡
r Â¡ a Â¡Â¡ Â¡ !
! Â¡Â¡
target
and a cocone to express that the composite r Â¡ a Â¡ n (the latter arrow being
!!
either source or target) is regular epic. In a model, r becomes the set of loops.
The fact that the arrow r Â¡ a Â¡ n maps surjectively to the nodes implies that
!!
there is at least one loop at each node. A homomorphism from M to M 0 must
take M (r) to M 0(r) as a set, but there is no particular loop in M (r) that is
distinguished by the construction.
2.4.7 Theories of sketches with colimits. The reader may have noticed
that in Chapter 7, we discussed FP sketches, their initial algebras and their
theories, and in Chapter ES 1 we discussed FD sketches and their initial algebras.
We did not discuss theories for FD sketches. In fact, theories exist for FD sketches,
and indeed for all sketches. This is because sketches can themselves be modeled
by an FL theory, and the theory of a sketch can then be realized as an initial
algebra (see Section ES 2.2). See [Wells, 1990], [Bagchi and Wells, 1994].
Here, we state the universal properties for theories of FD sketches for models
in categories with Â¯nite products and Â¯nite disjoint universal sums. The resulting
theory has these properties, too, and is embedded in a topos. The proof by initial
algebras just mentioned does not give such an embedding.
2.4.8 Theorem Let be an FD sketch. Then there is a category denoted
Â¡ ThFD ( )
!
ThFD ( ) with Â¯nite disjoint universal sums and a model M0 :
Â¡! into a category with Â¯nite products and Â¯nite
such that for any model M :
disjoint universal sums, there is a functor F : ThFD ( ) Â¡ ! that preserves
Â¯nite products and Â¯nite sums for which
(i) F Â± M0 = M , and
(ii) If F 0 : ThFD ( ) Â¡
! is another functor that preserves Â¯nite products and
Â¯nite sums for which F 0 Â± M0 = M , then F and F 0 are naturally isomorphic.
A proof may be found in [Barr and Wells, 1985], Proposition 1 of Section 8.2.
(FD sketches are called FS sketches there.)
The situation is similar for regular sketches.
2.4.9 Theorem Let be a regular sketch. Then there is a regular category
Â¡ ThReg ( ) such that, for any model
!
denoted ThReg ( ) and a model M0 :
Â¡! into a regular category, there is a regular functor F : ThReg ( )
M:
Â¡
! such that
(i) F M0 = M , and
Â±
2.4 General deÂ¯nition of sketch 25
(ii) if F 0 : ThReg ( ) Â¡
! is another regular functor for which F 0 Â± M0 = M ,
then F and F 0 are naturally isomorphic.
The theories of many types of sketches can be constructed as subcategories
of toposes; this is done in [Barr and Wells, 1985], Chapters 4 and 8. Other con
structions of theories for special kinds of sketches are given in [Ehresmann, 1968],
[Bastiani and Ehresmann, 1972], [Peake and Peters, 1972], [Kelly, 1982], [Wells,
1990] and [Barr and Wells, 1994].
2.4.10 Categories of setvalued models of general sketches can be axiomatized
as accessible categories (see [Makkai and ParÂ¶, 1990], [AdÂ¶mek and RosiÂ·ky,
e a c
1994].) A precise statement of the relationship between categories of models of
Â¯rst order theories and categories of models of sketches is given in [AdÂ¶mek and
a
RosiÂ·ky, 1994] (Theorems 5.35 and 5.44).
c
Generalizations of the concept of sketch are given by Lair [1987], Wells [1990]
(see also [Bagchi and Wells, 1994]), Power and Wells [1992], and Makkai [Makkai,
1994].
3
The category of sketches
The Â¯rst section of this chapter deÂ¯nes the concept of homomorphism of sketches,
yielding a category of sketches. In Section ES 3.2 we describe a formalism for
deÂ¯ning parametrized data types using sketch homomorphisms. In Section ES 3.3
we develop the theory of sketches further, showing that a homomorphism of
sketches induces a contravariant functor between the model categories and making
contact with Goguen and Burstall's concept of institution.
Section ES 3.3 requires only Section ES 3.1 to read. Nothing in this chapter is
needed later in the book.
Much more is known about the category of sketches than is mentioned here.
It is cartesian closed, for example. A basic study in English of the category of
sketches which is oriented toward computer science is given by Gray [1989].
3.1 Homomorphisms of sketches
= ( ; ; ; ) and 0 = ( 0 ; 0; 0 ; 0 ) be sketches. A graph
3.1.1 Let
homomorphism F : Â¡ 0 takes a diagram D :
! Â¡
! to a diagram F Â± D :
Â¡ 0 which is called the image of D in 0 . It takes a cone p : v Â¡ D to a cone
! !
F (p) : F (v) Â¡ F Â± D where, for each node a of the shape graph of D, F (p)a : F (v)
!
Â¡ F (D(a)) is deÂ¯ned to be F (pa ). It is deÂ¯ned on cocones similarly.
!
! 0 is a graph homo
ñòð. 9 