An FP-category is a category with ¬nite products, and an FP-functor be-

tween FP-categories is a functor which preserves ¬nite products. The FP theory

of groups should be an FP-category G containing a group object G which is

generic in the sense that every group object in any FP-category is the image of

G under a unique FP-functor from G to the category.

We will begin by constructing the FP-theory of groups from the ground up,

so to speak, but then interrupt ourselves for a di¬erent approach which makes it

obvious that the theory thus constructed is uniquely determined.

To construct the FP-theory of groups, we must have an object representing

the group, powers of that object, morphisms representing the projection maps

from those powers, and morphisms representing the operations (identity, inverse,

multiplication). A law like the associative law is stated by requiring that two

maps (representing the two ways of multiplying) in the category are equal.

Thus we need a category containing an object G and all its powers, speci¬cally

including G0 , which is the terminal object. It must have morphisms m: G2 ’ G,

’

0 k

i: G ’ G and u: G ’ G as operations. Each power G must have k projections

’ ’

pi : G ’ G, and for each k and n each n-tuple of maps Gk ’ G induces a

k

’ ’

k n

map G ’ G . A category containing all these maps must contain all their

’

composites; for example the composites m —¦ m — 1 and m —¦ 1 — m: G3 ’ G. The

’

group laws are equivalent to requiring that the following diagrams commute:

1 —E

u u—1

G—G '

G G

d

(1)

idd id

m

d

dc

‚ ©

G

(i, 1)

(1, i)

G—G '

E G

G

(2)

m

c

c c

EG' 1

1

146 4 Theories

and

m—1

E

G3 G2

(3)

m

1—m

c c

EG

G2 m

The commutativity of these diagrams, of course, forces many other pairs of

arrows of the category to be equal.

At ¬rst sight, it seems reasonably clear that the data we have given determine

a unique category G . Assuming that that is the case, it is easy to see that giving

a group object in a category with ¬nite products (in other words, giving a model

of the theory of groups in such a category) is the same as giving a ¬nite-product-

preserving functor from G to the category.

However, there are complications in carrying out the construction of G (even

more so in the case of multi-sorted algebraic structures, about which more below).

These di¬culties are analogous to the di¬culties in constructing the free group on

a set as consisting of equivalence classes of strings: they are not insurmountable,

but a construction using the adjoint functor theorem is much less fussy.

Sketches

In this section, we introduce some machinery (sketches) which will enable us

to give, in Section 4.3, a formal construction of G and analogous categories by

embedding the given data in a functor category and de¬ning G to be the smallest

subcategory with the required properties (having ¬nite products in the case of

groups). Our sketches are conceptually similar to, but di¬erent in detail from

those of Ehresmann (see the historical notes in Section 4.5). Note that sketches

here have only cones. Sketches in many texts also have cocones (we consider this

possibility in detail in Chapter 8); in those texts what we call sketches may be

called projective sketches.

Recall that a graph G consists of a set of vertices denoted G0 and a set of

arrows denoted G1 together with the operators d0 , d1 : G1 ’ G0 which assign to

’

each arrow its source and target. Cones and diagrams are de¬ned for graphs in

exactly the same way as they are for categories. Note that we have carefully

distinguished between cones and commutative cones and between diagrams and

commutative diagrams. Commutative cones and diagrams of course make no

sense for graphs.

By a sketch we mean a 4-tuple S = (G , U, D, C) where G is a graph, U : G0

’ G1 is a function which takes each object A of G0 to an arrow from A to A,

’

4.1 Sketches 147

D is a class of diagrams in G and C is class of cones in G . Each cone in C goes

from some vertex to some diagram; that diagram need not be in D; in fact in

general it is necessary to allow diagrams which are not in D as bases of cones.

An FP-sketch is a sketch in which the cones are discrete; that is, there are

no arrows between two distinct vertices of the base.

If S is another sketch, a morphism of S into S = (G , U , D , C ) is a

graph homomorphism h: G ’ G such that h —¦ U = U —¦ h, every diagram in D is

’

taken to a diagram in D , and every cone in C is taken to a cone in C .

If C is a category, the underlying sketch S = (G , U, D, C) of C has as

graph the underlying graph of C , for U the map which picks out the identity

arrows of C , takes D to be the class of all commutative diagrams of C and for C

all the limit cones.

A model for a sketch S in a category C is then a sketch morphism from S

into the underlying sketch of C . It follows that a model forces all the diagrams

of the sketch to commute and all the cones of the sketch to be limit cones (hence

commutative cones).

The models in C form a category. The morphisms are “natural” transforma-

tions, de¬ned in just the same way as natural transformations of functors (whose

de¬nition, after all, makes no use of composition in the domain category). The

models of S in Set will be denoted Mod(S ). The category of graph morphisms

from S to Set which take all the diagrams to commutative diagrams will be

denoted throughout the book as SetS .

The sketch of the theory of groups

We may construct a suitable FP-sketch for the theory of groups using the data

given above. The objects of the graph of the sketch should be 1 = G0 , G = G1 ,

G2 and G3 . Note that these are just formal names for objects at this point. We

will shortly introduce cones to force a model in the sense just de¬ned to take

them to the powers of one object. These powers are just those needed to state

the various group laws.

The sketch for groups must have the following arrows, besides the identity

arrows required by the de¬nition of sketch:

(i) Three arrows m: G2 ’ G, i: G ’ G and u: 1 ’ G for the operations.

’ ’ ’

(ii) Projection arrows for cones pi : G2 ’ G, (i = 1, 2) and qi : G3 ’ G, (i =

’ ’

1, 2, 3). In each case the cone is to the discrete diagram all of whose nodes are G.

(iii) An arrow G ’ 1.

’

148 4 Theories

(iv) ri : G ’ G2 , (i = 1, 2), which will be forced to be id — u and u — id

’

respectively. To allay any confusion, we should make it perfectly clear that G2 is

in no sense yet a product. Thus the ri have to be explicitly assumed.

(v) si : G ’ G2 , (i = 1, 2), to be (id, i) and (i, id)).

’

(vi) ti : G3 ’ G2 , (i = 1, 2), to be (q1 , q2 ) and (q2 , q3 ).

’

(vii) ni : G3 ’ G2 , (i = 1, 2), to be id — m and m — id.

’

As its designated cones, it must have the cones given in (ii) above and the

empty cone de¬ned on 1. Its diagrams must be diagrams (1) through (3) above

(with arrows renamed as just described) and forcing diagrams such as

E1

G

id r1 u

©

c c

' EG

G2

G p1 p2

which will force the r1 in models to be id — u,

q2 E

G3 G

d T

q1 p2

d t1

d

c d

‚

' GT

2

G p1

which will force t1 to be (q1 , q2 ), and

' q1 t2 E

3

G2

G G

n1 m

id

c c c

G ' p1 EG

G2 p2

which will force n1 to be id — m.

The preceding construction is involved, but the principle behind it is straight-

forward. You need

(i) an object to be the generic algebraic structure (group in the example

above);

(ii) objects to be the powers needed to de¬ne the operations and state the

laws;

4.2 The Ehresmann-Kennison Theorem 149

(iii) arrows for identities, for the operations, and for the cones forcing the

powers to be actual powers; and

(iv) diagrams to state the laws.

In the process of constructing these diagrams you may need

(v) arrows composed out of operations and projections.

The de¬nition in (v) requires additional diagrams such as the last three in the

de¬nition of groups above.

It should be clear that algebraic structures with ¬nitary operations satisfying

universal equations (unlike ¬elds, for example, where one needs statements like

“x = 0 or xx’1 = 1”) can all be modeled in this way.

More complicated algebraic structures may be modeled by an FP-sketch, too.

As an example, consider the category of all M -actions for all monoids M . An

object is a pair (M, A) where M is a monoid which acts on the set A. A morphism

(f, φ): (M, A) ’ (M , A ) has f a monoid homomorphism and φ a set map for

’

which f (m)(φ(a)) = φ(ma) for m ∈ M and a ∈ A. (One can de¬ne the category

of all modules (R, M ) where R is a ring and M is an R-module analogously).

The sketch for monoid actions will have to contain objects M and A and objects

representing M n for n = 0, 2, 3 as well as products of certain powers of M with

A.

The sketch for a theory for groups, for example, is essentially a direct trans-

lation of the ingredients that go into the usual de¬nition of groups in a textbook.

However, the sketch which results is not a category, and so we cannot use the

machinery of category theory to study the resulting models. In Section 4.3, using

the Ehresmann-Kennison theorem from Section 4.2, we show how to achieve our

original goal of producing a theory of groups which is itself a category, in fact the

category generated in a strong sense by the sketch constructed above.

4.2 The Ehresmann-Kennison Theorem

This section is devoted to proving the following theorem, due independently to

Ehresmann [1967a], [1967b] and Kennison [1968]. A generalization to base cate-

gories other than Set was proved by Freyd and Kelly [1972].

Theorem 1. Let S be a small sketch. Then Mod(S ) is a re¬‚ective subcategory

of SetS .

Proof. We follow Kennison™s original proof, which was stated for S a category

and for models which preserve all limits; but it works without change in the

present case. Ehresmann proved a much more general theorem of which this is a

special case.

150 4 Theories

It is necessary to construct a left adjoint for the inclusion of Mod(S ) in SetS .

We will do this using the adjoint functor theorem.

Limits in SetS are constructed pointwise in exactly the same way as for

functor categories (see Exercise 25 of Section 1.7). It is necessary to show that a

limit of a diagram of morphisms (objects in SetS ) takes the diagrams which are

part of the structure of S to commutative diagrams; but that is an easy exercise.

To show that inclusion preserves all limits requires showing that a morphism

constructed as a limit of a diagram of models takes cones to limit cones. This

follows easily in exactly the same way as it does for a limit of ordinary functors

(Exercise 2).

We need the following lemma to get the solution set condition.

Lemma 2. Let S be a small sketch, and F : S ’ Set a function on the objects

’

of S . There is a cardinal „µ with the following property: If M is any model of

S with the property that F (A) ⊆ M (A) for every object A of S , then there is a

model F of S for which for every object A of S ,

(i) F (A) ⊆ F (A) ⊆ M (A), and

(ii) The cardinality of F (A) is less than „µ.

Given the lemma, let E ∈ SetS , let M be a model, and let »: E ’ M be a

’

natural transformation. Let F be the function whose value on an object A is the

image of »A. The lemma provides a cardinal „µ(F ) with the property that F is

contained in a model F ⊆ M whose cardinality at each object of S is at most

„µ(F ). Now let „µ be the sup of the „µ(F ) as F varies over all object functions

which are quotients of E. Then a solution set for E will be the set of all natural

transformations φi : E ’ Mi for all models Mi for which for all objects A of S ,

’

the cardinal of Mi (A) is less than or equal to „µ.

Proof. Proof of Lemma 2. For any such F as in the hypothesis, de¬ne a function