<<

. 30
( 60 .)



>>

mop .
1

Theorem 4. Let S be an FP-sketch. Then m is a model of S . Moreover, any
model of S in a category C with ¬nite products has an extension along m to a
model of FP(S ) in C . This extension is unique up to isomorphism in the functor
category. Furthermore, Mod(S ) is equivalent to Mod(FP(S )), where FP(S )) is
considered a sketch whose cones are all the ¬nite product cones.
Proof. Just as in Exercise 26 of Chapter 1.7, if u embeds S into a subcategory
of SetS , then uop preserves everything that every functor in that subcategory
preserves. It follows that uop and hence m is a model of S . Now let S1 = S and
S2 = C in Theorem 3. The fact that C is a category and has ¬nite products and
u2 is a functor and preserves ¬nite products implies that C is equivalent to FP(C ).
(Note that FP(S ) is the closure of S under two operations”composition of
arrows and ¬nite products”and C is closed under both of them).

Fine points

Observe that models of a sketch S which happens to be a category with ¬nite
products and whose cones happen to be all ¬nite product cones are the same as
FP-functors from the category.
It follows from the fact that Mod(S ) is equivalent to Mod(FP(S )) that m
is both mono and epi in the category of FP-sketches. Nevertheless, m need not
be surjective on objects, nor re¬‚ect isomorphisms (a property more relevant than
injectivity on objects). For example, the embedding of the sketch for groups into
the theory of groups is not surjective, since the latter has all powers of G.
As for re¬‚ecting isomorphisms, consider the sketch obtained from the sketch
for groups by adding an arrow G ’ G2 and a diagram forcing m to be invertible.

This forces all the powers of G to be isomorphic.

Single-sorted theories

An FP-theory Th is single-sorted (or an algebraic theory) if there is an
object G of Th with the property that every object of Th is a power of G. Most
4.3 Finite-Product Theories 157
of the familiar categories in mathematics which are categories of models of FP-
theories are actually models of single-sorted theories. This includes examples like
groups, rings, monoids, R-modules for a ¬xed ring R (each element of the ring is
a unary operation), and even unlikely looking examples such as the category of
all modules (but not the category of all monoid actions (Exercise 2)).
A set of objects in an FP-theory Th is a set of sorts for the theory if Th is the
smallest FP-subcategory of Th containing the set of objects. The examples just
mentioned, especially the last, illustrate that the number of sorts for a theory is
not well-de¬ned, although single-sorted is well-de¬ned. Even though the category
of all modules can be presented as algebras for a single sorted theory, that is
conceptually not the most reasonable way to present it.

Single-sorted FP-algebras are tripleable over sets

The proof of the following theorem requires material from Chapters 3, 8 and
9, but we include it here because of the connection it makes between theories and
tripleability.
Theorem 5. The category of models in Set of an FP-theory Th is tripleable
over Set if and only if it is the category of models of a single-sorted FP-theory.
Proof. We make use of Theorem 5 of Section 9.1. The category of models of an
FP-theory is exact, as we will see in Section 8.4. If Th is single-sorted, then its
generating object (lying in the category of models via the embedding u given
above) is a regular projective generator. The converse follows immediately from
Theorem 5 of Section 9.1.

Exercises 4.3

1. Show that mop in diagram (2) is full and faithful (but, as pointed out in the
text, not necessarily either injective or surjective on objects).

2. Show that the category of all modules (de¬ned analogously to the category
of all monoid actions de¬ned in Section 4.1) is given by a single-sorted theory.
(Hint: The underlying set of (R, M ) where R is a ring and M is an R-module is
R — M ).

3. Show that if Th is a single sorted FP-theory, and Mod(Th) the category
of models of Th, then Th is equivalent to the full subcategory of Mod(Th)op
consisting of the ¬nitely generated free algebras.
158 4 Theories
Note: The following two exercises require familiarity with Theorem 5 above,
parts of Section 3.4 and Theorem 5 of Section 9.1.

1. Show that the category of all monoid actions (for all monoids) de¬ned in
Section 4.1 is the category of models of an FP-theory but not of a single-sorted
FP-theory. (Use Theorem 5, and show that it cannot have a single projective
generator. Remember the set acted upon can be empty. Or else use the following
exercise.)

2. (a) Prove that if A is a set of sorts for a theory Th, then Mod(Th) is tripleable
over SetA .
(b) Prove that the full subcategory of SetA consisting of functions whose
values are either always empty or never empty satis¬es VTT (see Section 3.5)
over Set, with underlying functor taking a function to the product of its values.
(Its left adjoint takes a set to a constant function.)
(c) Prove that the following three statements about an FP-theory Th are
equivalent:
(i) Th is equivalent to a single-sorted FP-theory.
(ii) If M is a model of Th in Set, then either M A is empty for every object
A of Th or M A is nonempty for every object A of Th.
(iii) The underlying functor Mod(Th) ’ Set re¬‚ects isomorphisms. (Hint:

Show that if Th is generated by a single object X then evaluation at X re¬‚ects
isomorphisms).

3. Show that the elements of the free algebra on n generators for a single sorted
theory are in 1-1 correspondence with the set of n-ary operations. (Hint: The
n-ary operations are the maps Gn ’ G in Th which are the same as arrows G

’ Gn in the category of models. Now use adjointness.)



4.4 Left Exact Theories
An LE-category is a left exact category, i.e. a category which has all ¬nite limits.
An LE-functor between LE-categories is one which preserves ¬nite limits. An
LE-sketch is a sketch, all of whose cones are over ¬nite diagrams.
Given an LE-sketch S , we can construct the LE-theory associated to S ,
denoted LE(S ), in exactly the same way that we constructed FP(S ) in Sec-
tion 4.3. As there, we also get a generic LE-model m: S ’ LE(S ) and we can

prove the following two theorems. In Theorem 1, vi is de¬ned as in Section 4.3.
4.4 Left Exact Theories 159
Theorem 1. Let f : S1 ’ S2 be a morphism of LE-sketches. Then f induces

a map f — : Mod(S2 ) ’ Mod(S1 ) which has a left adjoint f# . Moreover, if, for

i = 1, 2, ui = vi —¦ mi is the embedding of Siop into Mod(Si ), then there is a
op

functor LE(f )op which is the unique functor making the bottom square in the
following diagram commute. Moreover, any functor from LE(S1 )op to LE(S2 )op
that makes the top square commute must be naturally isomorphic to LE(f )op .

f op E S op
S1op 2


mop mop
1 2
c c
LE(f )op
E
LE(S1 )op LE(S2 )op

r1 r2
c c
f# E Mod(S )
Mod(S1 ) ' 2
f—
Theorem 2. Let S be a LE-sketch. Then any model of S in an LE-category
C has an extension along m to a model of LE(S ) in C . This model is unique
up to isomorphism in the functor category. Moreover, Mod(S ) is equivalent to
Mod(LE(S )) where the latter is considered a sketch whose cones are all the cones
over ¬nite diagrams.
The following corollary is immediate from Theorem 2.
Corollary 3. Every FP-theory has an extension to an LE-theory which has the
same models in any LE-category.
Thus for example there is an LE-theory of groups. Besides the powers of the
generic group G, it contains constructions which can be made from the powers
of G and the arrows in the FP-theory by forming ¬nite limits. Since the models
preserve these limits, and homomorphisms of groups are just natural transforma-
tions of the models, it follows that homomorphisms in a ¬xed LE-category must
preserve all constructions which can be made on the groups using ¬nite limits
in the theory of groups. For example, homomorphisms must preserve the subset
{(x, y) | xy = yx} of the product of a group with itself, since the latter is an
equalizer in the LE-theory of groups. Another example is the subset consisting
of elements whose order divides 2 (or any other ¬xed integer). This subset is
the equalizer of the homomorphism which is identically 1 and the squaring map,
both of which can be expressed in the theory of groups.
160 4 Theories
The center of a group can be described as {x ∈ G | for all y ∈ G, xy = yx}.
This does not have the form of a limit because of the universal quanti¬er inside
the de¬nition. Moreover, there can be no clever way to express the center as a
¬nite limit, because it is not preserved by homomorphisms.
In chapter 8, we are going to study in some detail the properties of categories
of models. However, one important property of models of LE-theories will be
used before that and we give the result here.
We must begin with a de¬nition. A diagram D: I ’ C is called ¬ltered if

(i) given any two objects i and j of I there is a third object k to which i
and j both map, and
(ii) given two arrows
f
’’J

I ’’

g
of I there is an arrow h: j ’ k such that D(h) —¦ D(f ) = D(h) —¦ D(g).

The slight awkwardness of this de¬nition is the price we must pay for using
index graphs instead of index categories. We believe it is worth it for the reasons
mentioned at the end of Chapter 1. “endcomment“endcommentA colimit taken
over a ¬ltered diagram is called a ¬ltered colimit. The main signi¬cance is that
¬ltered colimits commute with limits in Set and many other interesting categories
(Exercise 1).
Theorem 4. The category of set-valued models of a left exact theory has ar-
bitrary limits and all ¬ltered colimits; moreover, these are preserved by the set-
valued functors of evaluation at the objects of the theory.
Proof. Let Th be an LE-theory. If {Mi } is a diagram of models, the fact that
limits commute with limits implies that the pointwise limit lim Mi is a model
and is evidently the limit of the given diagram. Similarly, the fact that ¬nite
limits commute with ¬ltered colimits implies that the ¬ltered colimit of models is
a model. To say that these limits and ¬ltered colimits are computed “pointwise”
is the same thing as saying that they are preserved by the evaluation.

Finitely presented algebras

A ¬nitely presented algebra for an equational theory (that is, a single-
sorted FP-theory) is an algebra which is a coequalizer of two arrows between
¬nitely generated free algebras. Since the LE theory associated with an equational
theory is the ¬nite limit closure of the sketch in the dual of the category of models,
it can also be viewed as the dual of the ¬nite colimit closure of the category of
¬nitely generated free algebras in the category of algebras and hence contains
4.4 Left Exact Theories 161
every ¬nitely presented algebra. Moreover, it clearly consists of exactly that
category if and only if that category is cocomplete.
Theorem 5. Let C be the category of algebras for an equational theory. Then
the category of ¬nitely presented algebras is ¬nitely cocomplete, hence is the dual
of the associated LE theory.
Proof. We let F (n) denote the free algebra on n generators for a ¬nite integer n.
Since the sum of coequalizer diagrams is a coequalizer and the sum of ¬nite free
algebras is ¬nite free, it is evident that this category has ¬nite sums. So we must
show that in any coequalizer diagram

A ’ A’ A
’ ’
’’

if A and A are ¬nitely presented, so is A . Consider the picture

D0 E DE A
E F (n )
F (m )
1
D
d0 d0
cc
D0 E EA
E F (n)
F (m)
D
1
D
d
c
A
in which the two rows and the column are coequalizers. The properties of free-
ness, in conjunction with the fact that D: F (n) ’ A is surjective, allow us to

0 1
¬nd arrows d , d : F (n ) ’ F (n) making the diagram serially commutative. Fur-

thermore, by replacing the top row by the sum of the top row and the second,
making the di be the identity on the second component, everything remains as
is and now both pairs of di have a common right inverse in such a way that
the diagram remains serially commutative. By applying the same trick to the
top row we can suppose that the top row is also a re¬‚exive coequalizer. Thus
the result follows from the following lemma whose proof we leave as an exercise
(Exercise 5).
Lemma 6. In any category, if the top row and right column are re¬‚exive co-
equalizers and the middle column is a re¬‚exive parallel pair, then the diagonal
162 4 Theories
sequence is a coequalizer.
E DE
C' EB A
T T

c c c c
EA
B
D
d
c

<<

. 30
( 60 .)



>>