<<

. 28
( 60 .)



>>

Groups

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

<<

. 28
( 60 .)



>>