Practical Foundations of Mathematics

Paul Taylor

7.8  Exercises VII

1. Find the co-units and adjoint transformations of the examples in Section 7.1.

2. Define the Cauchy and Dedekind completions as functors on suitable categories and prove their universal properties.

3. 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.

4. 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 Cn^[]_T. 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 .

5. Explain how naturality of l and e defines postcomposition and the effect of the functor (-)^X on maps.

6. 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  4.36).

7. Let 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?

8. Let S be the monoid of parades in the Lineland Army (Example 1.2.7). Show that the operation S^op\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 monoid-with-a-monad.

9. Given ``F\dashv U'' with e:F·U º \id_D naturally, and a family of isomorphisms h_X:X º U(F X), show that U is full and faithful iff h is natural ( cf the proof of Theorem 7.6.9).

10. 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\typearrow_SU A] º U[FX\typearrow_AA] for X Î obS and A Î obA ( cf Exercise  3.69).

11. Deduce that any reflective subcategory A Ì S of a cartesian closed category is an exponential ideal ( [X\typearrow_SUA] Î obA and is the exponential there) iff the reflection preserves products. In this case A is also cartesian closed.

12. 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 a_X:X® X (Definition 1.3.12) such that X Î obAÛ a_X = \id_X.

13. Let F:C® D be a (co)limit- preserving functor and a:F® F a natural idempotent. Suppose that each a_X:FX® FX has a splitting GX in D. Show that G:C® D is also a (co)limit-preserving functor.

14. Treating diagrams as functors, explain how (co)cone s are natural transformations.

15. Construct finite wide pullbacks from binary pullbacks .

16. Construct (finite) connected limits from equalisers and (finite) wide pullbacks.

17. Show that \colim_Á\colim_J\typeX_{(I,J )} º \colim_J\colim_Á\typeX_(I,J). (For joins, see Lemma 3.5.4.)

18. Suppose that S has (co)limits of shape Á , and let C be any (small) category. Show that [C® S] º S^C also has (co)limits of shape Á, and that they are constructed pointwise, cf Lemma 3.5.7.

19. 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  3.2.10): "X:obS. $A:obA. $f:X® UA.

20. Prove the converse of Proposition  7.3.11. [Hint: consider the Yoneda embedding \typeX_(-):Á® C = Set ^Áop and let Q = \H_I.]

21. 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.]

22. Collect and compare properties (such as Definition 6.6.14) of the form ``(-)^X preserves colimits of shape Á'' for various classes of diagrams Á.

23. We say that X is finitely related ( cf stable 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 Î ob Set is finitely related iff it has decidable equality.

24. 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 related.

25. Let L be a disjunctive theory such as trichotomous orders, coherence spaces or fields (Section  5.5). Show that the forgetful functor Mod (L)® Set^S creates connected limits. For the theory of fields having roots of specified polynomials, show that the forgetful functor creates wide pullbacks but not equalisers .

26. 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

    omitted prooftree environment

    for all B and Y, ie in the ``opposite'' sense to Theorem  7.2.2.

27. Given adjunctions omitted diagram environment show that \RightAdjoint₂·\RightAdjoint₁\dashv \LeftAdjoint₁ ·\LeftAdjoint₂ with unit h₂;(\RightAdjoint₂·h₁ ·\LeftAdjoint₂), co-unit (\LeftAdjoint₁·e₂· \RightAdjoint₁);e₁ and adjoint transposition l₁o l₂. Show also that this notion of composition is associative (up to equality) and has a unit.

28. Let (\LeftAdjoint₁,\RightAdjoint₁,h₁, e₁) and (\LeftAdjoint₂,\RightAdjoint₂,h₂,e₂) be adjunctions with the same source and target categories. Find a natural bijection between natural transformations u:\RightAdjoint₁® \RightAdjoint₂ and f:\LeftAdjoint₂® \LeftAdjoint₁. 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.

29. Deduce that if a diagram of left adjoints commutes up to isomorphism then so does the corresponding diagram of right adjoints.

30. 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

    (a)

    the same objects (0-cells) as C;

    (b)

    as 1-cells, adjunctions, composition being given by Exercise  7.27;

    (c)

    as 2-cells, natural transformations as in Exercise  7.28.

31. 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 related.

32. 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, \typeB₁,\typeB₂:F\rightrightarrows E and C:E ® F and eight 2-cells of C with A\dashv \typeB₁ and \typeB₂\dashv C. By looking at various adjoint transpositions, show that \typeB₁ º \typeB₂ 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.)

33. 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?

34. 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.]

35. Let F:C^opxC® C be a mixed variance functor and G Î obC. A wedge from G to F 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.

36. 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 unique p:A® B such that both triangles commute (without U, ie p;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  5.7.1.)

37. Show that any functor T:Set® Set of the form \coprod_{n Î N}\argc_nx Xⁿ satisfies the conditions of the previous exercise, where the candidates with G = 1 and A = n correspond bijectively to elements of \argc_n. André Joyal has called such a functor analytic [Joy87,Tay89 ].

38. Describe the left adjoint of mor: Cat® Set. [Hint: not List.]

39. 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.

40. Show that an adjunction F\dashv U is of Kleisli type (Proposition 7.5.3(a)) iff F is essentially surjective and every e_A is a self-presentation ( cf Theorem 7.5.9).

41. (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.)

42. 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 \arga₁ and \arga₂ in A then so is f(a) of f(\arga₁) and f(\arga₂) 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  3.21).

43. Show that \Monad₀ in Remark  7.5.2 is the free monad on the functor T, formulating a suitable 2-category in which this is so.

44. 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.

45. Let (M,h,m) be a monad on S and suppose that ev:X® MX is a final coalgebra for the functor M. Show that for each G Î ob S there is a unique map f:G® X such that f;h_X = f; ev. [Hint: h_G .]

46. 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.

47. Prove Proposition 7.7.1.

48. 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].

49. Describe the effect of the functor Q in Notation  7.7.3(b) on morphisms.

50. 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 p₀ and p₁. Show that if the given factorisation systems are stable, then so is the resulting one, so long as U preserves pullbacks.

51. Let U:A® S be a functor between toposes that preserves finite limits. In particular it preserves monos, so there is a semilattice homomorphism p:U\twom_A ® \twom_S. omitted diagram environment Show that (\twom_S¯ p,\twom_A,p₁) is the subobject classifier of S¯ U.