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