<<

. 49
( 60 .)



>>

A and A , respectively. Since colimits commute with colimits, the coequalizer of
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

<<

. 49
( 60 .)



>>