F # (A) = {M f (F B) | f : B ’ A}

’

(union over all arrows into A) and a function F — by

F — (A) = F Di | M Ddxi = xj for all d: i ’ j ∈ I }

{x ∈ ’

the union over all those cones from A to D: I ’ G which are in the set C of

’

cones of S . (G is the underlying graph of S and each cone is to some diagram

D: I ’ G de¬ned on some index category I .)

’

For the purpose of understanding F — , observe that since M is a model, if ±: A

’ D is a cone, then M ±: M A ’ M D is a limit cone in Set, whence

’ ’

M A = {x ∈ M Di | M Ddxi = xj for all d: i ’ j ∈ I}

’

4.2 The Ehresmann-Kennison Theorem 151

and xi = M ±i (x) for x ∈ M A.

For any given F , let m denote the smallest cardinal which is greater than

(i) The cardinality of the set of arrows of S ;

(ii) the cardinality of F (A) for every object A of S ; and

(iii) the cardinality of I for every cone A ’ D(I) of S .

’

Clearly, F # (A) has cardinality less than m and it is not much harder to see

that F — (A) has cardinality less than mm (one is quantifying over sets”the sets

of projections ±i ”of cardinality less than m).

We construct a trans¬nite sequence of maps F± , beginning with F0 = F . For

an ordinal ±, if F± has been de¬ned, then f±+1 = (F± )#— . If ± is a limit ordinal,

then for each object A,

F± (A) = {Fβ (A) | β < ±}

According to the observations in the preceding paragraph, at each stage of

this construction the bound m on the cardinality of the sets F (A) may do no

more than exponentiate”and this bound is a function of S and the function F

we started with, but independent of M .

Now let F = Fγ , where γ is the smallest ordinal of cardinality greater than

the cardinality of the set of all arrows of S . (Note that γ is a limit ordinal). If

we can show F is the object function of a model, we are done.

In the ¬rst place, if f : B ’ A, then M f (F (B) ⊆ F (A). For if x ∈ F (B),

’

then x ∈ Fβ (B) for some ordinal β < γ, whence M f (x) ∈ Fβ+1 (A) ⊆ F (A). Thus

one can de¬ne F (f ) to be the restriction of M f to F (B) and make F a morphism

of sketches.

To show that F preserves the limits in the sketch S , let ±: A ’ D be a cone

’

of S , where D: I ’ G. If x ∈ F (A), then x ∈ M A, so for each d: i ’ j in I,

’ ’

M Ddxi = xj , so F Ddxi = xj because F Dd is the restriction of M Dd. Hence

F (A) ⊆ {x ∈ F Di | F Ddxi = xj for all d: i ’ j in I} = lim F D

’

Conversely, suppose x ∈ F Di has the property that F Ddxi = xj for all

d: i ’ j in I. For each i, xi ∈ F Di, so there is some ordinal βi γ for which

’

xi ∈ Fβi Di. Now since x ∈ M A, xi = M ±i (x), and we can assume that if ±i = ±j

then βi = βj . (For it is perfectly possible that I have greater cardinality than the

set of arrows of S ). Thus the set of all βi has cardinality less than or equal to the

cardinality of the set of arrows of S . That means there is a single ordinal β < γ

for which xi ∈ Fβ Di for all objects i of I. Thus it follows from the de¬nition that

x ∈ Fβ+1 (A) ⊆ F (A) which must therefore be lim F D.

152 4 Theories

Note: Exercise 1 shows that the information in the proof of the lemma yields

a more precise description of the left adjoint.

Exercises 4.2

1. Let E ∈ SetS , let M be a model of S , and let »: F ’ S be a natural

’

transformation.

(i) Show that the model F constructed above is the smallest submodel of M

through which » factors. We say » is dense if F = M .

(ii) Prove that if ±, β: M ’ N are natural transformations of models, » is

’

dense, and ± —¦ » = β —¦ », then ± = β.

(iii) Let φi : E ’ Mi be the solution set for E constructed in the text. Then

’

the φi determine a map E ’ ’ Mi ; let E be the smallest model through which

this map factors. Show that the function E ’ E is the object function of a left

’

adjoint to the inclusion of Mod(S ) in SetS .

2. Let A be a category and C be a class of diagrams in A , each of which has a

limit in A . Suppose that I is index category and D: I ’ SetA a diagram of

’

functors such that each value of D preserves all the limits in the class C. Show

that lim D also preserves the limits in C. (Note that the functor category is

complete because Set is (see Exercise 25 of Section 1.7).)

4.3 Finite-Product Theories

Given an FP-sketch S , we want to construct the FP-category which will be the

theory generated by the sketch. Letting X be the unknown theory, let us discover

properties it must have until enough of them emerge to characterize it.

X will be the generic model of S , so there will be a sketch morphism m: S

’ X . Moreover, composing with m should induce a bijection between the

’

models of X considered as a sketch with all its product cones and the models

of S . Now because X is a category and its cones are products, by Yoneda we

can get a canonical embedding y: X op ’ Mod(X ): For an object X of X ,

’

y(X)(X ) = Hom(X, X ). Then y(X) is a model because representable functors

preserve limits and”like all functors”preserve commutative diagrams. With the

requirement that m induce an equivalence between Mod(X ) and Mod(S ), this

produces the following diagram of sketch morphisms, in which e is the equivalence

and u = e —¦ y —¦ mop by de¬nition. The composite across the top is the Yoneda

4.3 Finite-Product Theories 153

embedding Y .

yE E SetX

X op Mod(X )

T

(1)

Setm

mop e

c c

E Mod(S E E SetS

op

S )

u

Because e is an equivalence, m has to be an epimorphism in the category of

sketches. This would seem to mean that every object in X is a product of objects

in S . Moreover, Y , hence y, is full and faithful and X op is closed under ¬nite

sums and contains the image of S op . This suggests that we try to construct X

by de¬ning u and letting X op be the full FP-subcategory generated by the image

of u. We will construct u by constructing X in the special case that S has no

cones, and then bootstrap up to the FP case using Kennison™s theorem.

Theorem 1. Given a sketch S with no cones (i.e., a graph with diagrams)

there is a category C and a model m: S ’ C such that composition with m is

’

an equivalence between SetS and SetC .

Proof. We constructed the free category for a graph with no diagrams in Ex-

ercise 11 of Section 1.9. Here, C can be obtained as a quotient category from

this free category by factoring out the smallest congruence making every diagram

commute (see Exercise 11 of Section 1.1). Then m is the map into the free cat-

egory followed by the quotient map. The required equivalence follows from the

de¬nition of “free” and “quotient”.

In this case, u is the composite Setm —¦ j —¦ mop , where j: C op ’ SetC is the

’

Yoneda embedding. u has the Yoneda-like property that for any model F : S

’ Set,

’

Hom(u(S), F ) ∼ F (S)—¦

(Y) =

This follows since m is full and faithful and uS = Hom(mS, m(’)); then use

Yoneda. Note that, as the composite of full and faithful functors, u is full and

faithful.

To get the case when S does have nontrivial cones, we must have a map u: S

’ Mod(S ) rather than into SetS . We have a map u1 : S op ’ SetS , namely

’ ’

the map constructed above called u for sketches with no cones (when S has no

cones it is the u we want because then SetS = Mod(S )). We take u to be k —¦ u1 ,

where k is the adjoint to the inclusion of Mod(S ) in SetS given by Kennison™s

Theorem (Section 4.2). It is a trivial consequence of adjointness that property

(Y) continues to hold in this case.

154 4 Theories

As suggested in our heuristic argument at the beginning of the section, we

de¬ne FP(S ), the FP-theory generated by S , to be the full FP-subcategory

of Mod(S )op generated by the image of uop . In the rest of this section, we will

use the factorization

u E Mod(S )

S op

d

mopd v (2)

d

d

‚©

FP(S )op

where v is the inclusion.

A theorem on adjoints

To see that FP(S ) has the same models as S , we need the following theorem.

Theorem 2. In the diagram of categories and functors,

F

X0 ' 0 Y0

T

(3)

I LJ

c c

X' Y

F

suppose that L is left adjoint to J. Then

(a) If I is full and faithful, F has a left adjoint E and F J naturally equivalent

to IF0 , then E0 = LEI is left adjoint to F0 ;

(b) If J is full and faithful, F has a right adjoint R, I has a left adjoint

K and KF is equivalent to F0 L, then there is a functor (unique up to natural

isomorphism) R0 : X0 ’ Y0 for which JR0 ∼ RI; R0 is right adjoint to F0 .

’ =

Proof. For (a),

Hom(LEIX0 , Y0 ) ∼ Hom(EIX0 , JY0 ) ∼ Hom(IX0 , F JY0 )

= =

∼ Hom(IX0 , IF0 Y0 ) ∼ Hom(X0 , F0 Y0 )—¦

= =

As for (b), ¬rst note that since J is full and faithful, LJL ∼ L so that we

=

have,

Hom(JLY, RIX0 ) ∼ Hom(F JLY, IX0 ) ∼ Hom(KF JLY, X0 )

= =

∼ Hom(F0 LJL, X0 ) ∼ Hom(F0 LY, X0 )

= =

∼ Hom(KF Y, X0 ) ∼ Hom(F Y, IX0 )

= =

∼ Hom(Y, RIX0 )—¦

=

4.3 Finite-Product Theories 155

Therefore, by Exercise 7(c) of Section 1.9, there is a unique Y0 which we will

denote R0 X0 , for which JY0 ∼ RIX0 . Veri¬cation of the adjunction equation is

=

easy, so that R0 extends to a right adjoint to F0 by the pointwise construction of

adjoints.

Properties of morphisms of FP-sketches

Theorem 3. Let f : S1 ’ S2 be a morphism of FP-sketches. Then composition

’

with f de¬nes a functor f — : Mod(S2 ) ’ Mod(S1 ) which has a left adjoint f# .

’

Moreover, if ui = vi —¦ mi is the embedding of Siop into Mod(Si ), then there

op

is a functor FP(f )op which is the unique functor making the middle square in

the diagram commute. Moreover, every functor from FP(S1 )op to FP(S2 )op that

makes the top square commute is naturally isomorphic to FP(f )op .

Proof. We have the following diagram:

f op E S op

S1op 2

mop mop

1 2

c c

FP(f )op

E

FP(S1 )op FP(S2 )op

r1 r2 (4)

c c

f# E Mod(S )

Mod(S1 ) ' 2

f—

T T

c c

f! E

SetS1 ' SetS2

f—

In this diagram, the lower f — is induced by composing with f , and since f takes

cones to cones, f — restricts to a map with the same name on models. f! is the left

Kan extension (Section 1.9). The inclusions of models into the functor categories

have left adjoints by Kennison™s theorem, and f# exists by Theorem 2(a).

The commutativity f# —¦ u1 = u2 —¦ f op follows from this computation, where

the last two isomorphisms follow from property (Y):

Hom(f# u1 (X), M2 ) ∼ Hom(u1 (X), f — M2 ) ∼ Hom(u1 (X), M2 —¦ f )

= =

∼ M2 (f (X)) ∼ Hom(u2 (f (X)), M2 )—¦

= =

Here X an object of S1 and M2 a model of S2 .

156 4 Theories

op

Since f# is a left adjoint, it preserves colimits, whence f# preserves limits.

op

Moreover, f# (S1 ) ⊆ S2 ⊆ FP(S2 ), FP(S1 ) is the full closure of S1 under ¬nite

products and FP(S2 ) is full and closed under ¬nite products, so it follows that

f# (FP(S1 )op ) ⊆ FP(S2 )op . We let FP(f )op be the restriction of f# . Clearly it

makes both squares commute. Uniqueness for the middle one follows from the

fact that v2 is monic, and uniqueness up to natural isomorphism for the top one

from the fact that FP(S1 )op is the FP-subcategory generated by the image of