<<

. 29
( 60 .)



>>

F # on objects by
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  

‚©
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

<<

. 29
( 60 .)



>>