ñòð. 24 
go from `in' to itself, `neither' goes from `out' to itself. The arrow `source' goes
from `in' to `out' and `target' from `out' to `in'. The terminal graph, which has
one arrow and one node, is embedded by the function true that takes the arrow
to `all' and the node to `in'.
and a subgraph 0 we deÂ¯ne a function Ã‚ : Â¡  !
Now given a graph
as follows. For a node n of , Ã‚(n) is `in' or `out', according to whether n is in
0 or not. For an arrow a, we let Ã‚(a) be `all' if a 2 0 (whence its source and
5.5 Sheaves 67
target are as well). If not, there are several possibilities. If the source but not the
target of a belongs to 0, then Ã‚(a) =`source'. Similarly, if the target but not the
source is in 0 , it goes to `target'. If both the source and target are in it, then
Ã‚(a) =`both' and if neither is, then it goes to `neither'.
5.4.4 Exercises
1. Show that the graphs No and Ar discussed in 6.1.12 are actually the contravari
Â¡
!
ant setvalued functors on 0 Â¡ 1 represented by the objects 0 and 1, respectively.
!
2. Show that the object  in the category of graphs can be described as follows.
The nodes are the subgraphs of No and the arrows are the subgraphs of Ar and
the source and target are induced by s and t (deÂ¯ned in 6.1.12), respectively.
3. Let be a category, and let M and N be two objects of Psh( ). Use the
Yoneda Lemma and the adjunction deÂ¯ning cartesian closed categories to show
that for any object X of , [M Â¡ N ](X) must be the set of natural transfor
!
mations from Hom(Â¡; X ) Â£ M to N , up to isomorphism. Note that this does not
prove that Psh( ) is cartesian closed. That is true, but requires ideas not given
here (see [Mac Lane and Moerdijk, 1992], page 46).
4. Let be a category and X an object of . Let  be the subobject classiÂ¯er
of Psh( ). Show that (X) is, up to isomorphism, the set of subfunctors (see
Exercise 3 of Section 4.3) of Hom(Â¡; X ).
5.5 Sheaves
The general deÂ¯nition of sheaves requires a structure on the category called
a Grothendieck topology. The most accessible and detailed discussion of
Grothendieck topologies is that of [Mac Lane and Moerdijk, 1992]. Here we will
discuss the special case of sheaves in which the category is a partial order.
5.5.1 Let P be a partially ordered set. From the preceding section, a presheaf
E on P assigns to each element x 2 P a set E(x) and whenever x Â· y assigns a
function we will denote E(x; y) : E(y) Â¡ E(x) (note the order; x precedes y, but
!
the arrow is from E(y) to E(x)). This is subject to two conditions. First, that
E(x; x) be the identity function on E(x) and second that when x Â· y Â· z, that
E(x; y) Â± E(y; z) = E(x; z). The arrows E(x; y) are called restriction functions.
We make the following supposition about P .
5.5.2 Heyting algebras
HA{1 There is a top element, denoted 1, in P .
HA{2 Each pair of elements x; y 2 P has an inÂ¯mum, denoted x ^ y.
W
HA{3 Every subset fxi g of elements of P has a supremum, denoted xi .
68 Toposes
W W
HA{4 For every element x 2 P and every subset fxi g Âµ P , x ^ ( xi ) = (x ^ xi ).
A poset that satisÂ¯es these conditions is called a complete Heyting algebra.
5.5.3 If fxi g is a subset with supremum x, and E is a presheaf, there is given
a restriction function ei : E(x) Â¡ E(xi ) for each i. The universal property of
!
Q
product gives a unique function e : E(x) Â¡ ! i E(xi ) such that pi Â± e = ei . In
addition, for each pair of indices i and j, there are functions cij : E(xi ) Â¡ E(xi ^
!
xj ) and dij : E(xj ) Â¡ E(xi ^ xj ) induced by the relations xi Â¸ xi ^ xj and xj Â¸
!
Q Q
xi ^ xj . This gives two functions c; d : i E(xi ) Â¡ ij E(xi ^ xj ) such that
!

Q Q
c E(xi ^ xj )
E(xi )
i ij
pij
pi
? ?
 E(xi ^ xj )
E(xi ) cij
and

Q Q
d E(xi ^ xj )
i E(xi ) ij
pij
pi
? ?
 E(xi ^ xj )
E(xi )
dij
commute.
5.5.4 DeÂ¯nition A presheaf is called a sheaf if it satisÂ¯es the following addi
tional condition:
_
x = xi
implies
cY
eY
E(x) Â¡! E(xi ) Â¡!
Â¡! E(xi ^ xj )
Â¡
Â¡
d ij
i
is an equalizer.
5.5.5 Theorem The category of sheaves on a Heyting algebra is a topos.
As a matter of fact, the category of sheaves for any Grothendieck topology
is a topos (see any of the texts [Johnstone, 1977], [Barr and Wells, 1985], [Mac
Lane and Moerdijk, 1992], [McLarty, 1992]).
5.5 Sheaves 69
5.5.6 Constant sheaves A presheaf E is called constant if for all x 2 P ,
E(x) is always the same set and for all x Â· y, the function E(y; x) is the identity
function on that set.
The constant presheaf at a oneelement set is always a sheaf. This is because
the sheaf condition comes down to a diagram
1Â¡ 1Â¡ 1
!
!Â¡ !
which is certainly an equalizer. No constant presheaf whose value is a set with
other than one element can be a sheaf. In fact, the 0 (bottom) element of P is
the supremum of the empty set and the product of the empty set of sets is a
oneelement set (see 5.3.6). Hence the sheaf condition on a presheaf E is that
Y Y
Â¡
!
E(0) Â¡
! Â¡
!
; ;
which is
E(0) Â¡ 1 Â¡ 1
!
!Â¡ !
and this is an equalizer if and only if E(0) = 1.
5.5.7 A presheaf is said to be nearly constant if whenever 0 < x Â· y in P ,
the restriction E(y) Â¡ E(x) is an isomorphism. It is interesting to inquire when
ñòð. 24 