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

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‚