ñòð. 6 
The intention is that in a Setmodel, the arrows of the sketch will be inter
preted as follows:
u is the unit function which assigns to each object its identity,
s and t are the source and target functions from the set of arrows to the
set of objects, and
c is the function which takes a composable pair of arrows to its composite.
The remaining arrows of the sketch are projections from a limit or are inter
preted as arrows to a limit with speciÂ¯ed projections.
The diagrams are
c3 c3
Â¡ @ Â¡ @
Â¡ hp2; p3 i @ Â¡ hp1 ; p2 i @
p2 p3 p1 p2
Â¡ @ Â¡ @
Âª
Â¡ ? R
@ Â¡
Âª ? @
R
c1 Â¾ p  c1 c1 Â¾ p  c1
c2 c2
p2 p2
1 1
c2 Â¾hp1 ; p2 i c3 c3 hp2; p3 i c2

@ Â¡
hc; p3 i @ Â¡ hp1; ci
p3 p1
c c
@ Â¡
? ? @
R Âª
Â¡ ? ?
c1 Â¾ p  c1 c1 Â¾ p 
c2 c2 c1
p2 p2
1 1
c0 Â¾ s
t c1 c1 c0
@ Â¡
@ id Â¡ hid; u Â± si
u hu Â± t; idi u
id
@ Â¡
? ? R
@ Â¡
Âª ? ?
c1 Â¾ p  c1 Â¾ 
c2 c1 c2 c1
p p1 p2
1 2
c1 hid; u si c2 Â¾hu t; idi c1
 hp1 ; ci 
Â± Â±
c3 c2
@ Â¡
@ Â¡
c hc; p3i c
id @ Â¡ id
@ Â¡
@
R ?Â¡Âª ? ?

c1 c2 c1
c
Finally, there are two cones that say that c2 and c3 are interpreted as the
objects of composable pairs and triples or arrows, respectively.
16 More about sketches
c3
Â¡ @
p1 Â¡ @
p2 p3
c2
Â¡ @
Â¡ @ Â¡
Âª ? R
@
p1 Â¡ @ p2 c1 c1 c1
Â¡ @
Â¡ @
Âª
Â¡ ? @
R
 c0 Â¾ Â¡t
c1 c1 s s@ t
s t Â¡ @
?Â¡Âª @
R?
c0 c0
This sketch is the sketch of categories and is one of the simpler FL sketches
around.
The category of models (in Set) of an FP sketch must be regular (see [Barr
and Wells, 1985], Theorem 1 of Section 8.4) and it can be proved that the category
of categories and functors is not regular (see Exercise 6 of Section 8.6). It follows
that categories and functors cannot be the models of an FP sketch.
Lawvere [1966] described another structure whose models are categories. Let 1; 2; 3
and 4 denote the total orders with one, two, three and four elements, considered as
categories in the usual way a poset is. Let denote the opposite category. In that
opposite category, it turns out that 3 = 2 Â£1 2 and 4 = 2 Â£1 2 Â£1 2. Then Cat is
the category of limitpreserving functors of into Set with natural transformations
as arrows. It follows that the sketch whose objects and arrows are those of , whose
diagrams are the commutative diagrams of and cones are the limit cones of is
another sketch, closely related in fact to the one above, whose category of models is
Cat.
We show how binary trees can be described as models of an FL sketch in the
next section.
2.1.6 Exercises
1. A groupoid is a category in which every arrow is an isomorphism. Explain
how to modify the sketch for categories to get a sketch for groupoids.
2. Show that in the category of sets, the deÂ¯nition of homomorphism between
two models of the sketch for categories gives the usual deÂ¯nition of functor.
2.2 Initial term models of FL sketches
Like FP sketches, FL sketches always have initial models. The construction 7.6.5
produced an initial term algebra for each Â¯nite FP sketch. A modiÂ¯cation of the
last three rules in 7.6.5 is suÂ±cient to construct an initial term algebra for each
Â¯nite FL sketch. This will be described below.
2.2 Initial term models 17
A diÂ®erent construction is in Barr [1986b], where it is proved that in fact FL
sketches have free algebras on any typed set X (see Section 9.2.) Volger [1987]
gives a logicbased proof for the special case of Horn theories (see [Volger, 1988]
for applications).
The modiÂ¯cation of 7.6.5 is required by the fact that the base diagram D of
a cone in need not be discrete in the case of general limits; that is, the shape
of the diagram D in Section 8.2 may have nontrivial arrows u : i Â¡ j. !
graph
A limit of such a cone in the category of sets is not just any tuple of elements of
the sets corresponding to the nodes of , but only tuples which are compatible
with the arrows of .
Â¡ Set is a Â¯nite diagram (we use the letter E
!
2.2.1 Precisely, suppose E :
instead of D to avoid confusion below). A compatible family of elements of E
is a sequence (x1; : : : ; xn ) indexed by the nodes of for which
C{1 xi 2 E(i) for each node i.
C{2 If u : i Â¡ j in , then E(u)(xi ) = xj .
!
An initial term algebra of an FL sketch =( ; ) is then the least model
;
satisfying the following requirements.
ñòð. 6 