Find the co-units and adjoint transformations of the
examples in Section 7.1.
Define the Cauchy and Dedekind completions as functors
on suitable categories and prove their universal properties.
Show that the functor which assigns the set of components
to a graph (Example 7.1.6(c)) preserves
finite products but not equalisers or pullbacks. Explain why the axiom
of choice is needed to extend this to infinite products.
Let T:Set® Set
be a functor coding an infinitary free theory as in Chapter
VI. What is the categorical structure
-Cat which corresponds to this fragment of logic ()? [Hint: restrict
the arity to k and consider k-ary products.] Describe
the classifying category CnT. Find a
category C of languages (whose objects are functors such as
T) so that this classifying category is the universal map from the object
T to the forgetful functor
U:-Cat® C .
Explain how naturality of l and e
defines postcomposition and the effect of the functor (-)X on maps.
Show that any adjunction between groups must be a strong
equivalence, the two functors being isomorphisms whose composition
is a conjugacy (inner automorphism) ( cf Exercise
U = S(1,-):S® Set be the global sections functor of a topos
S = SetÁop. Show that U calculates limits of presheaves
considered as diagrams in Set, and that
\constfunct \dashv U , where \constfunct X(I) = X for
X Î obSet and I Î obÁ. The functor \constfunct
itself has a left adjoint: what is it?
Let S be the monoid of parades in the Lineland
Army (Example 1.2.7). Show that the operation
Sop\hookrightarrow S which reverses a parade
and promotes everyone by one grade is a monoid homomorphism which is
symmetrically adjoint to itself on the right. Show that this is the free
Given ``F\dashv U'' with
e:F·U º \idD naturally, and a family of isomorphisms hX:X º U(FX),
show that U is full and faithful iff h is natural ( cf
the proof of Theorem 7.6.9).
Let A be a cartesian closed category and
F:A® S a functor which preserves binary
products and has a right adjoint U. Show that
[X\typearrowSUA] º U[FX\typearrowAA] for
X Î obS and A Î obA ( cf Exercise
Deduce that any reflective subcategory
A Ì S of a cartesian closed category is an exponential
ideal ( [X\typearrowSUA] Î obA
and is the exponential there) iff the reflection preserves products.
In this case A is also cartesian closed.
Let U:A Ì S be a full replete
subcategory. Show that there exists a functor
F:S® A such that both F\dashv U and U\dashv F iff each object
X Î obS carries a natural split idempotent aX:X® X
(Definition 1.3.12) such that
X Î obAÛ aX = \idX.
Let F:C® D be a (co)limit-
preserving functor and a:F® F a natural idempotent. Suppose
that each aX:FX® FX has a splitting GX in D.
Show that G:C® D is also a (co)limit-preserving
Treating diagrams as functors, explain how (co)cone
s are natural transformations.
Construct finite wide pullbacks from binary pullbacks
Construct (finite) connected limits from equalisers
and (finite) wide pullbacks.
\colimÁ\colimJ\typeX(I,J ) º \colimJ\colimÁ\typeX(I,J). (For
joins, see Lemma 3.5.4.)
Suppose that S has (co)limits of shape Á
, and let C be any (small) category. Show that
[C® S] º SC also has (co)limits of shape
Á, and that they are constructed pointwise, cf
Let Á be a filtered category and
U:Á ® J a final functor. Show that J is also
filtered. [Hint: use filteredness to simplify the definition of finality
first.] Show that if U is also full and faithful then filteredness of
J implies that of Á ( cf Exercise
3.15). In this case show that, to test finality,
it suffices that the object class be ``cofinal'' (Proposition
"X:obS. $A:obA. $f:X® UA.
Prove the converse of Proposition
7.3.11. [Hint: consider the Yoneda embedding
\typeX(-):Á® C = Set Áop and let
Q = \HI.]
Show that any set X is finitely presentable iff
(-)X preserves filtered colimits, and that every set is a filtered
colimit of finitely presented sets, cf Proposition
6.6.13ff. [Hint: consider
Á = §fp¯ X.]
Collect and compare properties (such as Definition
6.6.14) of the form ``(-)X preserves
colimits of shape Á'' for various classes of diagrams Á.
We say that X is finitely related ( cfstable in [Joh77, p. 233]) if,
in any pullback of the form
omitted diagram environment
with A and B finitely generated, K is also finitely generated.
In other words, for any two lists of elements, there is (in the internal
sense) some list of coincidences between them. Show that
X Î obSet is finitely related iff it has decidable equality.
Formulate the definitions of finitely presentable,
generable and related for objects of Mod(L),
where L is a finitary algebraic theory. Show that X is finitely
generated iff C(X,-) preserves directed unions, finitely
related iff this functor preserves filtered colimits of surjections,
and finitely presented iff all filtered colimits are preserved. Hence
show that it is finitely presented iff it is finitely generated and finitely
Let L be a disjunctive theory such
as trichotomous orders, coherence spaces or fields (Section
5.5). Show that the forgetful functor
Mod (L)® SetS creates connected
limits. For the theory of fields having roots of specified polynomials,
show that the forgetful functor creates wide pullbacks but not equalisers
Let F:C® A,
U:A ® C, B:A® K and
Y:C ® K be functors. Show that F\dashv U if there
is a natural bijection
for all B and Y, ie in the ``opposite'' sense to Theorem
omitted diagram environment
\RightAdjoint2·\RightAdjoint1\dashv \LeftAdjoint1 ·\LeftAdjoint2 with unit
h2;(\RightAdjoint2·h1 ·\LeftAdjoint2), co-unit
(\LeftAdjoint1·e2· \RightAdjoint1);e1 and adjoint transposition
l1o l2. Show also that this notion of composition is associative
(up to equality) and has a unit.
(\LeftAdjoint1,\RightAdjoint1,h1, e1) and (\LeftAdjoint2,\RightAdjoint2,h2,e2)
be adjunctions with the same source and target categories. Find a natural
bijection between natural transformations
u:\RightAdjoint1® \RightAdjoint2 and f:\LeftAdjoint2® \LeftAdjoint1.
Show that it respects identities and (vertical) composition of u
and f, and is preserved by composition on either side with another
adjunction, as in Exercise 7.27.
Deduce that if a diagram of left adjoints commutes
up to isomorphism then so does the corresponding diagram of right adjoints.
Explain how the triangle laws (Definition
7.2.1) give a meaning to the notion of adjunction
within any 2-category C (Definition
4.8.15). Show how to define the 2-category
C\dashv which has
the same objects (0-cells) as C;
as 1-cells, adjunctions, composition being given by Exercise
as 2-cells, natural transformations as in Exercise
Show that the forgetful 2-functor
C\dashv ® C which extracts the left (or right) part of the
adjunction and natural transformations is full and faithful at the 2-level.
Deduce that the 2-category of left adjoints is equivalent to that of right
adjoints, in the weakest sense of Definition
4.8.9(d). Explain why they are not directly
For any 2-category C, (C\dashv)\dashv
has the same objects (0-cells), but the 1-cells
E® F consist of four 1-cells A:E® F,
\typeB1,\typeB2:F\rightrightarrows E and
C:E ® F and eight 2-cells of C with
A\dashv \typeB1 and \typeB2\dashv C. By looking at various adjoint
transpositions, show that \typeB1 º \typeB2 canonically
and hence that (C\dashv)\dashv is strongly 2-equivalent
to the 2-category whose 1-cells are adjoint triples in C. Describe
the 2-cells. By applying the result for C to C\dashv,
show that ((C\dashv)\dashv)\dashv is strongly 2-equivalent
to the 2-category of adjoint sequences of length 4 and so on. (
Arbitrarily long chains of adjunctions exist by Exercise
3.61 and its categorical analogue.)
What does the solution-set condition in the General
Adjoint Functor Theorem 7.3.12 mean in
the case of Proposition 6.1.11, and how
do the conjunctive interpretation and equationally free algebras show
that it is satisfied?
Formulate a solution-set condition for a pre
factorisation system (E,M) in which M-maps
need not be mono, and use it to factorise maps ( cf Proposition
5.7.11). [Hint: consider the category
whose objects are factorisations of the given map into an E
and an arbitrary map.]
Let F:CopxC® C
be a mixed variance functor and G Î obC.
A wedge from G toF is a dinatural
transformation (Exercises 4.44ff), and
the end òXF(X,X) is the final wedge, just as a cone
is a natural transformation from an object to a diagram and its limit
is the final cone. Show that A = òX[[A® X]® X]
for any object A of a cartesian closed category. Deduce the other
parts of Remark 2.8.11.
Let U:A® C be a functor.
A C-map e:G® UA is called a
candidate if, in any commutative square of the form on the left,
omitted diagram environment
there is a uniquep:A® B such that both triangles
commute (without U, iep;m = z and
not just Up;Um = Uz). Suppose that every
map G® TX in C factors uniquely as e;Um,
with e a candidate. Show that U preserves wide pullbacks.
( Cf factorisation systems, Definition
Show that any functor
T:Set® Set of the form \coprodn Î N\argcnxXn
satisfies the conditions of the previous exercise, where the candidates
G = 1 and A = n correspond bijectively
to elements of \argcn. André Joyal has called such a functor
Describe the left adjoint of
mor: Cat® Set. [Hint: notList.]
Show that IPO Ì Dcpo
is the full subcategory of objects which are able to support an algebra
structure for the lift monad, and that this is what the co-Kleisli category
on the category of algebras is always like.
Show that an adjunction F\dashv U is of Kleisli
type (Proposition 7.5.3(a)) iff F is
essentially surjective and every eA is a self-presentation
( cf Theorem 7.5.9).
(Robert Seely) Let A be a symmetric monoidal
closed category (so it has a tensor product Ä and a mixed-variance
functor \multimap satisfying
(-)ÄX\dashv X\multimap ( = ) ) which also has finite products and is equipped with a comonad ! such
that !(AxB) º !AÄ!B and !1 = I (the tensor
unit). Show that the co-Kleisli category is cartesian closed, with
[A® B] = !A\multimap B. (Exercises 4.27ff give
a concrete example.)
A function f:A\multimap B between L-domains is
called linear if it preserves locally least upper bounds
ie if a is a locally least upper bound of \arga1 and \arga2
in A then so is f(a) of f(\arga1) and f(\arga2) in B. In particular
f is Scott-continuous, but this is weaker than the condition needed
for a right adjoint unless A is a complete semilattice ( cf
Exercise 3.33ff). Let A\multimap B be
the dcpo of linear functions, with the pointwise order, which agrees
with Exercise 4.27 for complete semilattices.
There we found (-)ÄA\dashv A\multimap ( = ). Use the
fact that A = ÈaA¯ a for any L-domain A (Exercise
3.34), to deduce the existence of AÄB
for L-domains from the interaction of colimits and left adjoints.
Describe AÄB for boundedly complete domains (Exercise
Show that \Monad0 in Remark
7.5.2 is the free monad on the functor
T, formulating a suitable 2-category in which this is so.
By analogy with Exercise 3.36
and Proposition 7.5.11, explain how any
(infinitary) monad can be seen as an infinitary single-sorted algebraic
theory with a proper class of operation-symbols and laws.
Let (M,h,m) be a monad on S and
suppose that ev:X® MX is a final coalgebra
for the functorM. Show that for each
G Î obS there is a unique map f:G® X such that
f;hX = f; ev. [Hint: hG .]
Formulate the results of Section 7.6
as a reflection of the 2-category of categories with -structure
as a property and functors preserving it (and natural
transformations) into the 2-subcategory where this structure is canonical
and preserved on the nose.
Investigate the effect of a natural transformation
f:U® U¢ on S¯ U. Consider in particular
the case where f is cartesian, ie its naturality
squares are pullbacks [Tay88].
Describe the effect of the functor Q in Notation
7.7.3(b) on morphisms.
Let U:A® S be a functor
between categories, each equipped with a factorisation system, such
that U takes ``monos'' of one kind to ``monos'' of the other. (For example
all maps in S could be called ``monos.'') Define a
factorisation system on S¯ U which is preserved
by p0 and p1. Show that if the given factorisation systems
are stable, then so is the resulting one, so long as U preserves pullbacks.
Let U:A® S be a functor
between toposes that preserves finite limits. In particular it
preserves monos, so there is a semilattice homomorphism
omitted diagram environment
Show that (\twomS¯ p,\twomA,p1)
is the subobject classifier of S¯ U.