<<

. 31
( 60 .)



>>

A


Examples of LE-theories

The main point of LE-theories is that many mathematical structures are mod-
els of LE-theories. In the remainder of this section, we will show that
(i) posets and order-preserving maps,
(ii) categories and functors,
(iii) LE-categories and LE-functors, and
(iv) toposes and logical functors
are all categories of models of LE-theories. None of these is the category of
models of an FP-theory (see Exercise ??).
Toposes are the subject of Chapter 2, and logical functors are de¬ned in
Section 5.3. We de¬ne them below to maintain the independence of this chapter
from Chapter 2.
We ¬rst observe that to make an arrow f : B ’ A become a mono in all the

LE-models of the sketch, one only need add the cone
U AE
A A
d
df f
UA
d
c ‚
dc
EB
A
f
4.4 Left Exact Theories 163
to the set of cones of the sketch. This is shorthand for saying, “Add the cone
with vertex A whose base is the diagram
A

f
c
EB
A
f
and whose transition arrows are U A, U A and f to the sketch”. The diagram then
must become a pullback in any model (and U A must become idA ), forcing f to
be monic. (Note that this cone is made up of data already given in the sketch).
Similarly, to construct a pullback of a diagram
A

f
c
EC
B g
where the objects and arrows are already in the diagram, one adds an object P
and arrows p1 : P ’ A, p2 : P ’ B, and p3 : P ’ C and makes these data a
’ ’ ’
cone of the sketch.
To force the following diagram

f
e ’’B

E ’’ A ’ ’
’ ’
g

to become an equalizer in the models, one must add a cone with vertex E and
arrows to the diagram
f
A’’B’
’’

g
The latter diagram must not be included as one of the diagrams in the sketch
as that would obviously force f = g.
One can construct other limits in a similar way. In the sequel, that is what
we mean when we say that a sketch must have an arrow “which is to be a monic”
or an object “which is to be a limit” of some given diagram.
Thus we can describe the sketch for posets as containing the following items.
(i) An object S, which will become the underlying set of the poset.
(ii) An object S 2 to be the product of S and S.
164 4 Theories
(iii) An object R (the relation) and a monic i: R ’ S 2 .

To force R to be re¬‚exive, you need an object ∆, a monic δ: ∆ ’ S 2 and a

cone forcing it to be the equalizer of the projections. Then add an arrow r: ∆
’ R and a diagram

rE
∆ R
d
δd i
d
dc

S2
You could instead construct a common right inverse to the projections of R
onto S but we need ∆ anyway.
For antisymmetry, add an arrow S 2 ’ S 2 and a diagram forcing it to be the

switching map. Then add an arrow s: R ’ R and a diagram forcing it to be the

restriction of the switching map. With this you can add an object A and a cone
forcing it to be the ¬ber product R —S R where the ¬rst projection is UR and the
second is s. Thus A must become the set

{(r, r ) | (r, r ) ∈ R and (r , r) ∈ R}

Note that A must become a subobject of R in the model (the pullback of
a monic is a monic), and so a subobject of S 2 . Antisymmetry is simply the
requirement that there is a monic e from A to ∆ and a diagram forcing the
inclusion of A in S 2 to factor through it.
Transitivity can be attained by constructing the pullback

P = [(r1 , r2 , r3 ) | (r1 , r2 ) ∈ R and (r2 , r3 ) ∈ R]

and an arrow p: P ’ R with a diagram forcing p(r1 , r2 , r3 ) = (r1 , r3 ).

We will see in Chapter 8 (Theorem 1 of Section 8.4) that, since the category
of posets is not regular, it cannot be expressed as models of an FP-theory.

Categories

The work of constructing a sketch whose models are categories was essentially
done in Section 1.1, where categories were de¬ned by commutative diagrams.
Thus the sketch for categories must contain objects A (to be the set of arrows),
O (to be the set of objects) P , and Q, along with arrows di : A ’ O, (i = 0, 1),

0 1
u: O ’ A and m: P ’ A, cones making P = [(f, g) | d (f ) = d (g)] and
’ ’

Q = [(f, g, h) | d0 (f ) = d1 (g) and d0 (g) = d1 (h)]
4.4 Left Exact Theories 165
It must also contain the diagrams (i) through (iv) of Section 1.1; to include
these diagrams, we have to add the four arrows in those diagrams not already
in the sketch, such as 1 — m, and diagrams forcing those four arrows to be what
they should be, in much the same way as we added arrows to get the FP-sketch
for groups in Section 4.1. We omit the details. (Note that we do not need to
add arrows to be idO or idA because of the incorporation of the function U in the
de¬nition of sketch).
By omitting some of these arrows, you get a sketch for the category of graphs
and morphisms of graphs. However, that category is actually given by an FP-
theory (see Exercise 2).

Left exact categories

By adding appropriate data to the LE-theory of categories, one can force
the models to be left exact categories with designated limits; the morphisms of
models are exactly the functors that preserve the designated limits.
To get left exactness, we force the existence of a terminal object and of pull-
backs. We do pullbacks in considerable detail as an example of how to do other
constructions later; the terminal object is done by similar methods (but more
easily) and is omitted.
To the sketch for categories we add an object CC, which is to be the set of
pairs of arrows with common codomain, i.e.,

CC = {(f, g) ∈ A — A | d1 (f ) = d1 (g)};

an object CD, which is to be the set of pairs of arrows with common domain;
and CS, which is to be the set of commutative squares. Thus CC and CD must
be the vertices of the following ones:
cc2 E cd2E
CC A CD A

cc1 d1 d0
cd1
c c c c
EO EO
A A
d1 d0
Similarly, CS must be a cone which in an interpretation becomes

[(f, g, h, k) | d0 (f ) = d0 (g),d1 (h) = d1 (k), d1 (f ) = d0 (h),
d1 (g) = d0 (k), and m(h, f ) = m(k, g)]—¦
166 4 Theories
This comes equipped with four projections si : CS ’ A. (Don™t confuse these

pullbacks with the pullbacks which we are trying to force the existence of in the
models.)
We also add an arrow t: CS ’ CC which projects a commutative square

onto its lower right half; this is forced by adding the diagram
s4 E
CS A
d
s3 cc2
dt
d
c dc

E CS
A cc1

to the sketch.
Forming the pullback of something in CC must be an arrow »: CC ’ CD; ’
on this we must impose equations forcing the codomains of the two arrows which
make up »(f, g) to be the domains of f and g respectively. These are the diagrams
» E CD
CC

cci cdi
c c
EO'
A A
d0 d1
for i = 1, 2.
To get the pullback condition, any commutative square must have a unique
arrow to the appropriate pullback square with the appropriate commutativity
conditions. The existence of the arrow is assured by including an arrow θ: CS
’ A in the sketch which for a given commutative square S = (f, g, h, k) makes

everything in the following diagram commute. Note that this diagram, unlike the
ones above, is intended to be in a model, not in the sketch.
g E S2
S1
d 
 
 
d θ(S) s
 
d


f »(h, k) k
 
 r
 
c  
© c
E S4
S3
h
4.4 Left Exact Theories 167
Here, r = cd1 (»(t(S))) and s = cd2 (»(t(S))).
To make everything in the preceding diagram commute requires several dia-
grams to be added to the sketch. These diagrams must
(i) force the domain of θ(S) to be the upper left corner of S;
(ii) force the codomain of θ(S) to be the upper left corner of »(t(S));
(iii) and make the two triangles in the preceding diagram commute.
In some cases, arrows and other diagrams de¬ning them must be added to
the sketch before these diagrams are included. For example, the diagram which
makes the upper triangle commute is the right diagram below, where the left
diagram de¬nes u.
t θE
CC ' S A S
d T d
p2 d s2
ud u
»
d d
c d
‚ c ‚
d
EA' EA
A2 2
CD A m
p1
cd2
Finally, to get the uniqueness of θ, we must de¬ne an object SS in the sketch
that is to represent all sextuples of arrows in the following con¬guration
g E S2
S1
d
d 
 
 
dv
ud s
 
d
dd‚ 

<<

. 31
( 60 .)



>>