ñòð. 22 |

5.2.4 Kernel pairs Here is one case in which this condition is automatic. If

g : A Â¡ C is an arrow, the pullback of the square

!

5.2 Properties of toposes 61

d- A

E

g

e

? ?

-C

A g

is called a kernel pair of g. Notation: we will write that

d g

Â¡!

Â¡

E Â¡! A Â¡! C

Â¡

Â¡

e

is a kernel pair. For an object B of , the deÂ¯nition of this limit is that there is a

one to one correspondence between arrows B Â¡ E and pairs of arrows (h; k) from

!

B to A such that g Â± h = g Â± k and that the correspondence is got by composing

an arrow from B to E with d and e, resp. To put it in other words, Hom(B; E)

is isomorphic to

f(h; k) 2 Hom(B; A) Â£ Hom(B; A) j g Â± h = g Â± kg

which is an equivalence relation.

5.2.5 Suppose that E Â¡ A describes an equivalence relation. We say that the

!

Â¡

!

equivalence relation is eÂ®ective if it is a kernel pair of some arrow from A. We

say that a category has eÂ®ective equivalence relations if every equivalence

relation is eÂ®ective. We give the following without proof. The interested reader

may Â¯nd the proof in [Barr and Wells, 1985] Theorem 7 of Section 2.3, [Johnstone,

1977], Proposition 1.23, p. 27, or [McLarty, 1992], Section 16.7.

5.2.6 Theorem In a topos, every equivalence relation is eÂ®ective.

5.2.7 Example Equivalence relations in the categories Set and Mon are ef-

fective. An equivalence relation in Set is simply an equivalence relation, and the

class map to the quotient set is a function that has the equivalence relation as

kernel pair. An equivalence relation on a monoid M in Mon is a congruence

relation on M (see Exercise 6 of Section 3.5); it is eÂ®ective because a monoid

multiplication can be deÂ¯ned on the quotient set of the congruence relation that

makes the quotient map a homomorphism (Exercise ES 3).

There are many categories which lack eÂ®ective equivalence relations. One is the

category of partially ordered sets and monotone maps. Here is a simple example.

Let C be a two-element chain x < y. Consider the subset E of C Â£ C consisting

of all four pairs (x; x), (x; y), (y; x) and (y; y). The only ordering is that (x; x) Â·

(y; y). Then E is an equivalence relation, but is not the kernel pair of any arrow

out of C. The least kernel pair that includes E has the same elements as E, but

has the additional orderings (x; x) Â· (x; y) Â· (y; y) and (x; x) Â· (y; x) Â· (y; y).

Other important properties of toposes are contained in the following.

62 Toposes

5.2.8 Theorem Let be a topos.

(a) has Â¯nite colimits.

(b) has Â¯nite disjoint and universal sums.

(c) Every epi in is regular, and is a regular category.

An early proof of the fact that a topos has Â¯nite colimits ([Mikkelson, 1976] mimicked

the construction in sets. For example, the coequalizer of two arrows was constructed

as a set of subsets, which can be identiÂ¯ed as the set of equivalence classes mod the

equivalence relation generated by the two arrows. However, the argument is diÂ±cult.

The modern proof (due to ParÂ¶) is much easier, but it involves some legerdemain

e

with triples and it is hard to see what it is actually doing. See [Barr and Wells, 1985],

Corollary 2 of 5.1 for the latter proof. The rest is found in 5.5 of the same source.

5.2.9 The initial topos There is an FL sketch whose models are toposes.

(See [Barr and Wells, 1985], Section 4.4. In that book, FL sketches are called LE

sketches.) It follows that there is an initial model of the topos axioms. This topos

lacks a natural numbers object. It might be an interesting model for a rigidly

Â¯nitistic model of computation, but would not allow the modeling of such things

as recursion.

The phrase `initial topos' is usually reserved for the initial model of the axioms

for toposes with a natural numbers object (Section 5.5). This category provides

an interesting model for computation. The arrows from N to N in that category

are, not surprisingly, the total recursive functions. In fact, all partial recursive

functions are modeled in there as well, but as partial arrows, which we now

describe.

5.2.10 Partial arrows In 2.1.13 we discussed partial functions between sets.

This concept can be extended to any category. Let A and B be objects. A partial

arrow A to B consists of a subobject A0 Âµ A and an arrow f : A0 Â¡ B. This

!

deÂ¯nes the partial arrow f in terms of a particular representative A0 Â¡ A of the

!

0

subobject, but given any other representative A0 Â¡ A, there is a unique arrow

!

0

from A0 to A0 commuting with the inclusions which determines an arrow from

A00 to B by composition with f . The subobject determined by A0 is called the

domain of the partial arrow. If g : A1 Â¡ B is another partial arrow on A we

!

say the f Â· g if A0 Âµ A1 and the restriction of g to A0 is f . If we let i : A0

Â¡ A1 denote the inclusion arrow, then the second condition means simply that

!

g Â± i = f . We will say that f and g are the same partial arrow if both f Â· g and

g Â· f. This means that the domains of f and g are the same subobject of A and

that f and g are equal on that domain.

We say that partial arrows to B are representable if there is an object

e !e

B and an embedding B )Â¡ B such that there is a one to one correspondence

!e

between arrows A Â¡ B and partial arrows A to B, the correspondence given by

pulling back:

5.2 Properties of toposes 63

-A

A0

? ?

- e

B B

In a topos, the arrow true: 1 Â¡ - represents partial functions to 1. The reason

!

is that since each object has a unique arrow to 1, a partial arrow from A to 1 is

equivalent to a subobject of A.

In a topos, partial arrows into any object are representable.

5.2.11 Theorem

See [Johnstone, 1977], Section 1.26 or [McLarty, 1992], Section 17.1 for the

proof.

5.2.12 Exercises

1. Verify the isomorphisms of (ES 5.2) for Set.

2. Let S be a set and E be an equivalence relation on S. Then there are two arrows

E to S, being the inclusion of E into S Â£ S, followed by the two projections on

S. Show that E, together with these two arrows, is the kernel pair of the function

that takes each element of S to the equivalence class containing it.

3. a. Let d; e : E Â¡ M be two monoid homomorphisms. Show that they form an

!

Â¡

!

equivalence relation in Mon if and only if the arrow

hd; ei

E Â¡Â¡ Â¡ M Â£ M

Â¡ Â¡!

is a monomorphism and the image of hd; ei is a congruence on M (see Exercise 6

of Section 3.5 with d; e the projections).

b. Show that equivalence relations in Mon are eÂ®ective.

ñòð. 22 |