idA and t is the sum of the coequalizers of idA and t and of idA and t . Such

a sum cannot be 1 unless one of the terms is 0 (Proposition 2(a) of Section 7.1).

Since A is a substructure it contains the global element a and so cannot be 0;

hence it must be A, as required.

We now have all the ingredients to prove Theorem 6. Suppose we are given

a natural number object N = (N, 0, s). We ¬rst show (i) of the theorem. A

straightforward diagram chase shows that if i1 : 1 ’ 1 + N is the inclusion and

’

t = i2 —¦ 0, s : 1 + N ’ 1 + N , then (1 + N, i1 , t) is a PE-structure and 0, s

’

is a morphism from this structure to N. Thus the composite 0, s —¦ t(’) (i1 ) (we

remind you just this once that the last morphism, by de¬nition, is the unique

morphism from N to (1 + N, i1 , t)) is an endomorphism of N as a PE-structure,

so by de¬nition of NNO must be the identity.

264 7 Representation Theorems

If we can show that the opposite composite t(’) (i1 ) —¦ 0, s is the identity on

1 + N we will have shown that 0, s is an isomorphism. That follows from this

calculation, in which we use the notation of (ii) at the beginning of this section:

t(’) (i1 ) —¦ 0, s = t0 (i1 ), ts (i1 )

= i1 , ts—¦idN (i1 ) = i1 , t —¦ t(’) (i1 ) —¦

But this last term is i1 , i2 = id1+N , where i2 is the inclusion N ’ 1 + N ,

’

(’)

since t = i2 —¦ 0, s and we have already shown that 0, s —¦ t (i1 ) is the identity.

To show that 1 is the coequalizer of s and idN , we need to show that given any

f : N ’ X with f —¦ s = f , there is an arrow x: 1 ’ X with f = x(). (As before,

’ ’

() denotes the unique map from something to 1”here the something must be N ).

We de¬ne x = f (0). It is easy to see that both f and x() are PE-morphisms from

N to the PE-structure (X, x, idX ), hence must be the same. Uniqueness follows

because N has a global element 0, so the map N ’ 1 is epic.’

For the converse, let (N, 0, s) satisfy (i) and (ii), so 0, s is an isomorphism and

the coequalizer of idN and s is 1. If (A, a, t) is any PE structure and f, g: N ’ A ’

two PE-morphisms, then the equalizer of f and g would be a PE-substructure

of (N, 0, s), so must be all of N by Proposition 7. Hence (N, 0, s) satis¬es the

uniqueness part of the de¬nition of NNO.

Now suppose (B, b, u) is a PE-structure. Then so is (N — B, 0 — b, s — u). By

Proposition 1, this structure must contain a substructure (A, a, t) with a, t epic.

Moreover, the projection maps composed with inclusion give PE-morphisms A

’ N = A )’ N — B ’ N and A ’ B = A )’ N — B ’ B. Thus if we

’ ’ ’ ’ ’ ’

can show that the map A ’ N is an isomorphism, we will be done.

’

This map A ’ N is epic because its image must be a PE-substructure of

’

(N, 0, s), so must be all of it by the Peano property. To see that it is monic (in

a topos, monic + epic = iso), it is su¬cient to prove:

Proposition 8. If a, t is epi, 0, s is an isomorphism, the coequalizer of idN

and s is 1, and f : A ’ N is a PE-morphism, then f is monic.

’

Proof. The constructions involved in this statement are all preserved by exact

functors, so it is enough to prove it in a well-pointed topos. Let K )’ A — A

’

be the kernel pair of f , K the complement of the diagonal ∆ in K, and N the

image of the map K ’ A ’ N (take either projection for K ’ A”the kernel

’ ’ ’

pair is symmetric). Let M be the complement of N . We must show M = N ,

for then N = 0, so K = 0 (the only maps to an initial object in a topos are

isomorphisms), so K = ∆ and f is then monic.

We show that M = N by using the Peano property.

7.6 Countable Toposes and Separable Toposes 265

If a global element n of N is in N it must lift to at least two distinct global

elements a1 , a2 of A for which f a1 = f a2 . (This is because Hom(1, ’) preserves

epis by Proposition 2 of Section 7.1, so an element of N must lift to an element

of K .) If it is in M it must lift to a unique element of A which f takes to n.

Since any element of N must be in exactly one of N or M , the converse is true

too: An element which lifts uniquely must be in M .

Suppose the global element 0: 1 ’ N lifted to some a1 other than a. (Of

’

course it lifts to a.) Since a, t is epi, a1 = t(a2 ). Thus 0 = f t(a2 ) = sf (a2 ) which

would contradict the fact that 0, s is an isomorphism. Thus by the argument

in the preceding paragraph, a ∈ M . A very similar argument shows that if the

global element n of N has a unique lifting then so does sn. Hence sM ⊆ M , so

by the Peano property, M = N as required.

Corollary 9. An exact functor between toposes takes a NNO to a NNO.

Exercise 7.5

1. (a) Show that Set — Set is a topos with natural number object N — N.

(b) Show more generally that if E1 and E2 are toposes with natural number

objects N1 and N2 , respectively, then E1 — E2 is a topos with natural number

object N1 — N2 .

7.6 Countable Toposes and Separable Toposes

A Grothendieck topos is called separable if it is the category of sheaves on a site

which is countable as a category and which, in addition, has the property that

there is a countable base for the topology. By the latter condition is meant that

there is a countable set of covering sieves such that a presheaf is a sheaf if and

only if it satis¬es the sheaf condition with respect to that set of sieves. Makkai

and Reyes [1977] have generalized Deligne™s theorem to the case of separable

toposes. In the process of proving this, we also derive a theorem on embedding

of countable toposes due to Freyd [1972].

Standard toposes

A topos E is called standard if for any object A of E and any re¬‚exive,

symmetric relation R ⊆ A — A the union of the composition powers of R exists.

That is if R(n) is de¬ned inductively by letting R(1) = R and R(n+1) be the image

266 7 Representation Theorems

in A — A of the pullback R(n) —A R, then we have

R ⊆ R(1) ⊆ R(2) ⊆ · · · ⊆ R(n) ⊆ · · ·

and we are asking that this chain have a union. By Exercise 5 of Section 6.8, this

union, when it exists, is the least equivalence relation containing by R. Such a

least equivalence relation always exists, being the kernel pair of the coequalizer of

the two projections of R, so this condition is equivalent to requiring that {R(n) }

be an epimorphic family over that least equivalence relation. Of course if the

topos has countable sums the union may be formed as the image in A — A of the

sum of those composition powers. Hence we have,

Proposition 1. A countably complete topos is standard.

Proposition 2. Let E be a standard topos and u: E ’ F be a near exact

’

functor that preserves countable epimorphic families. Then u is exact.

Proof. It is su¬cient to show that u preserves coequalizers. In any regular cat-

egory the coequalizer of a parallel pair of maps is the same as the coequalizer of

the smallest equivalence relation it generates. The re¬‚exive, symmetric closure

of a relation R ⊆ B — B is R ∨ ∆ ∨ Rop , a construction which is preserved by near

exact functors. Thus it is su¬cient to show that such a functor u preserves the

coequalizer of a re¬‚exive, symmetric relation.

“endcomment

So let R be a re¬‚exive, symmetric relation and E be its transitive closure.

Then by hypothesis the composition powers, R(n) of R, are dense in E. Hence

the images uR(n) ∼ (uR)(n) are dense in uE. The isomorphism comes from

=

the fact that all constructions used in the building the composition powers are

preserved by near exact functors. Moreover, uE is an equivalence relation for

similar reasons: the transitivity comes from a map E —B E ’ E and this arrow

’

is simply transported to F . The least equivalence relation on uB generated by

uR contains every composition power of uR, hence their union which is uE. Since

uE is an equivalence relation, this least equivalence relation is exactly uE.

To ¬nish the argument, we observe that near exact functors preserve coequal-

izers of e¬ective equivalence relations. This is a consequence of the facts that

they preserve regular epis, that they preserve kernel pairs and that every regular

epi is the coequalizer of its kernel pair.

Proposition 3. If u: E ’ F is an exact embedding (not necessarily full)

’

between toposes and F is standard, so is E .

Proof. Let R be a re¬‚exive, symmetric relation and E be the least equivalence

relation containing it. If the composition powers of R do not form an epimorphic

7.6 Countable Toposes and Separable Toposes 267

family over E, there is a proper subobject D ⊆ E which contains every R(n) .

Applying u and using the fact that it is faithful, we ¬nd that uD is a proper

subobject of uE that contains every uR(n) . But the construction of E as the

kernel pair of a coequalizer is preserved by exact functors, so the uR(n) must

cover uE in the standard topos F . Thus E must be standard as well.

Proposition 4. A small topos is standard if and only if it has an exact embed-

ding into a complete topos that preserves epimorphic families. If the domain is

Boolean, resp. 2-valued, the codomain may be taken to be Boolean, resp. 2-valued.

Proof. The “only if” part is a consequence of Propositions 1 and 3. As for the

converse, it su¬ces to take the category of sheaves for the topology of epimorphic

families. The functor y of Section 6.8 is an embedding that preserves epimorphic

families, and Proposition 2 gives the conclusion.

If B is a Boolean topos, this embedding may be followed by the associated

sheaf functor into the category of double negation sheaves. An exact functor on

a Boolean topos is faithful if and only if it identi¬es no non-zero object to zero

(Exercise 4 of Section 7.1). But an object B is identi¬ed to 0 if and only if 0

’ B is dense, which is impossible for B = 0 as 0 certainly has a complement.

’

If B is 2-valued, every map to 1 with a non-0 domain is a cover. If F = 0 is a

presheaf and B ’ F is an arbitrary element of F , then B ’ F ’ 1 is epi,

’ ’ ’

whence so is F ’ 1. Thus 1 has no proper subobjects except 0 and so the topos

’

is 2-valued.

A topos with an NNO is called N-standard if the ordinary natural numbers

(that is, 0, 1, 2, 3, · · ·) form an epimorphic family over N. It follows from Theo-

rem 6 of Section 7.5 that an exact functor preserves the NNO, if any. It is clear

that any countably complete topos is N-standard since N is then the sum of the

ordinary natural numbers. If E is a standard topos with an NNO, then from

Proposition 4 it follows that E has an exact embedding into a complete topos

that preserves epimorphic families. As in the proof of Proposition 3, a faithful

exact functor re¬‚ects epimorphic families. Thus we have,

Proposition 5. A standard topos has an exact embedding into an N-standard

topos that preserves epimorphic families; moreover a standard topos with an NNO

is N-standard.

Proposition 6. An N-standard topos has an exact embedding into an N-standard

Boolean topos that preserves epimorphic families.

Proof. Apply Theorem 3 of Section 7.1. The embedding preserves N and pre-

serves epimorphic families.

268 7 Representation Theorems

Proposition 7. A countable N-standard Boolean topos has a logical functor to

a 2-valued N-standard Boolean topos.

Proof. We begin by observing that if U is a subobject of 1 in a topos E , then

the induced maps from subobject lattices in E to those of E /U are surjective.

Moreover a slice functor has a right adjoint and so preserves epimorphic families.

Now let B be a Boolean topos with a standard NNO and let U1 , U2 , · · · enumerate

the subobjects of N. Having constructed the sequence

B ’ B1 ’ B2 ’ · · · ’ Bn

’ ’ ’ ’

of toposes and logical functors gotten by slicing by subobjects of 1, we continue

as follows. Let m be the least integer for which the image of Um in Bn is non-0.

Since the natural numbers are an epimorphic family over N, there is at least one

natural number, say p: 1 ’ N for which the pullback

’

E1

P

c c

EN

Um

is non-0. The process can even be made constructive by choosing the least such.

Then let Bn+1 = Bn /P . In the limit topos, every non-0 subobject of N has a

global section which is a natural number. There are two conclusions from this.

First, the natural numbers cover and second, since 1 is subobject of N, every

non-0 subobject of 1 also has a global section which implies that the topos is

2-valued.

It is worth mentioning that the trans¬nite generalization of this argument

breaks down because at the limit ordinals you will lose the property of being

N-standard; the epimorphic families may cease being so at the limits (where the

transition functors are not faithful; see Lemma 9 below). The proof above uses

an explicit argument to get around that.

Corollary 8. Let B be a countable N-standard Boolean topos. Then for every

non-0 object A of B, there is a logical functor from B into a countable 2-valued

N-standard topos in which A has a global section.

Proof. Just apply the above construction to B/A and replace, if necessary, the

resultant topos by a countable subtopos that contains A, N and the requisite

global sections.

7.6 Countable Toposes and Separable Toposes 269

Lemma 9. Let E± be a directed diagram of toposes and faithful logical morphisms

which preserve epimorphic families. Let E = colim E± . Then for any ± the

canonical functor E± ’ E is faithful, logical and preserves epimorphic families.

’

Proof. We use the notation Tβ,± : E± ’ Eβ for ± ¤ β and T± : E± ’ E for the

’ ’

element of the cocone. Let fi : Ei ’ E be an epimorphic family in E± . Let

’

g, h: T± E ’ E be distinct maps in E . Directedness implies the existence of

’

β ≥ ±, an object E of Eβ and (necessarily distinct) maps

g , h : Tβ,± E ’ E

’

such that Tβ (g ) = g and Tβ (h ) = h. Since {Tβ,± fi } is also an epimorphic family,

there is an index i for which

g Tβ,± fi = h Tβ,± fi

—¦ —¦

Since for all γ ≥ β, Tγ,β is faithful, it follows that

Tβ g T± fi = Tβ h T± fi

—¦ —¦

which shows that the {T± fi } are an epimorphic family. The fact that the T± are

faithful and logical is implicit in what we have done.

Proposition 10. Every countable N-standard Boolean topos has a logical em-

bedding into a product of N-standard well-pointed toposes.

Proof. For a non-zero object A of the topos there is, by Corollary 9, a logical

functor into a countable 2-valued N-standard topos B in which A is not sent to

zero (in fact has a global section). Enumerate the elements of B and de¬ne a

sequence of toposes B = B0 ⊆ B1 ⊆ B2 ⊆ · · · in which Bi+1 is obtained from

Bi by applying that Corollary to the ith object in the enumeration. If Bω is

the direct limit of this process, then every object of B has a global section in

Bω . Moreover, it follows from Exercise 4 of Section 7.1 and Lemma 9 that the

resultant functor B ’ Bω is logical, faithful and preserves epimorphic families

’