Practical Foundations of Mathematics

Paul Taylor

4.9  Exercises IV

  1. Formulate and prove the fact that any polygon commutes iff it can be decomposed into commuting polygons.

  2. Using the Cayley-Yoneda action, show that every monoid arises as a submonoid of HH for some set H. For any set X, characterise the constant functions lx.a solely in terms of composition in XX. Describe the Cayley-Yoneda action of any monoid M on its constants.

  3. By choosing some combinatorial structure, such as the cosets of subgroups, show that every group arises up to isomorphism as the group of all automorphisms of some algebraic structure.

  4. Restate Proposition 4.2.9 for categories. Show that C has two faithful regular actions: on HX = ÈQ C(X,Q) (contravariantly by precomposition) and \HX = ÈG C(G,X) (covariantly by postcomposition). Reformulate these as functors HX = C(X,-) and \HX = C(-,X).

  5. Prove the Normal Form Theorem  4.3.9. Note that skip, put and discard each require special treatment. Say where each of the five laws is used, explaining why the last is not redundant.

  6. Let L be a free theory (with no laws). Show that the isomorphisms of \CloneLx are just the variable renamings (open a-equivalences).

  7. Let C be any category and K Ì C a wide subcategory which is an equivalence relation, ie it contains all objects and identities, and there is at most one morphism between any two objects, whose inverse exists and is in K. Construct the category C/K whose objects are K-equivalence classes of C-objects and show that C\twoheadrightarrow C/K is an equivalence functor. Show also that for any functor F:C® Q which takes all K-maps to identities there is a unique mediating functor P:C/K ® Q.

  8. Show that Example 4.3.4 correctly solves the cubic equation; explain where the Floyd rules (Remark 4.3.5) are used.

  9. Formulate the side-conditions on the use of variables which are needed to adapt the Floyd rules to assignment.

  10. Explain Examples 4.4.2, in particular that functors C® Set and Cop® Set are actions.

  11. Prove Example 2.7.6(d), that List(-) is a functor.

  12. Why are forgetful functors between concrete categories usually faithful but not full?

  13. Show that the functor Rel® CSLat of Example 4.4.4(b) is full and faithful.

  14. For a locale (frame) A, define pts(A) = Frm(A,W). Extend this definition to a functor pts:Loc® Sp. When is it faithful? Full?

  15. Let \typeF0, \typeF1 and \typeF2 be the sets of vertices, edges and faces of some polyhedron with triangular faces, for example these sets have respectively 12, 30 and 20 elements in the case of an icosahedron. Using the functions d0n,d1n, ¼,dn-1n:\typeFn® \typeFn-1, describe the boundary of the n-dimensional faces and explain how the data (\typeFn,din) fit together into a functor D ® Set, where D is the opposite of the category of finite sets and injective functors. Such a structure is called a simplicial complex.

  16. Verify that there is a category K(C) , known as the Karoubi completion, whose objects are idempotents ( e;e = e, Definition  1.3.12) and whose morphisms e® d are C-maps f with e;f = f = f;d. Show that every idempotent in K(C) is split, ie expressible as \nearrow ;i where i;\nearrow = id. Let F:C® Q be any functor, where Q has given splittings of idempotents. Show that there is a unique functor K(C)® Q extending it and formulate this as a universal property. Finally, show that functors P:K(C)® Q correspond to semifunctors F:C® Q (Example 4.4.6(d)).

  17. Show that groups and groupoids, considered as categories, have no non-trivial products ( cf Exercise  5.1).

  18. Prove Proposition 4.5.14, that the terminal object and products of pairs suffice to give all finite products.

  19. Justify Example 4.5.8(g), ie that N º NxN in the category composed of primitive recursive functions.

  20. Propositions 2.6.7- 2.6.9 defined three constructions with well founded relations. Are they products? If so, identify the categories.

  21. Characterise products in Pfn, assuming excluded middle.

  22. Show that the Tychonov product (Example  3.9.10(e)) gives the (categorical) product in Sp and also in Dcpo and  IPO.

  23. Let L be the two-sorted algebraic theory of a commutative ring together with a module. Characterise the objects of Cn×L by a pair of natural numbers, and the morphisms by a list of polynomials together with a matrix ( cf Remark 4.6.5).

  24. Let L be a single-sorted algebraic theory. Show that the forgetful functor |-|:Mod(L) ® Set creates products (Definition  4.5.10(c)). What is the analogous result for many-sorted theories?

  25. Let L be an algebraic theory all of whose operation-symbols happen to be unary. Consider its classifying categories \CloneL and Cn×L qua unary and algebraic theories respectively. Show that \CloneL is strongly equivalent to the full subcategory of Cn× L with of one-variable contexts, ie the algebraic theory is a conservative extension of the unary one.

  26. Show that any internal monoid in the category Mon of monoids is commutative. [Hint: consider m(x,ee,y).]

  27. For complete join-semilattices A and B let AÄB , A\PAR B and A\multimap B be respectively the semilattices of Galois connections, co-Galois connections and left adjoints from A to B (Definition 3.6.1). Show that

    (a)
    AÄB satisfies the Mac Lane-Kelly laws with unit W;

    (b)
    CSLat(A,B\multimap C) º CSLat (AÄB,C);

    (c)
    AÄW º A º WÄA;

    (d)
    (A\multimap Wop ) º Aop;

    (e)
    A\PAR B º Aop\multimap B º (Aop ÄBop)op also satisfies the Mac Lane-Kelly laws, with unit Wop ;

    (f)
    negation defines CSLat-maps W® Wop and AÄB® A\PAR B.

    Such a structure is called a *-autonomous category [ Bar79].

  28. Let !A be the lattice of Scott-closed sets (Proposition  3.4.9) of a complete lattice A. Show that !1 = W, !(Ax B) º (!A)Ä(!B) and [A® B] º (!A)\multimap B, the latter being the lattice of Scott-continuous functions. Hence show that the category of complete lattices and Scott- continuous functions is cartesian closed.

  29. (Bill Lawvere) Let L be a single-sorted algebraic theory. Show that Cn×L @ C for a category with obC = N such that addition is the categorical product. Conversely show that every such category C arises in this way.

  30. Show that any group in which "g.g2 = id is Abelian. Express this argument in the various notations we have used.

  31. Show that if f(x,y) is a derived operation in the theory of groups such that f(x,f(y,z)) = f(f(x,y),z) then f(x,y) is one of the forms x y, y x, x, y or  id. [Hint: it is enough to consider Z2.]

  32. Describe the category (analogous to that in Lemma  4.5.16) of which the function-space YX is the terminal object.

  33. Let C be a cartesian closed category. Show that K(C) is too (Exercise  4.16).

  34. Consider the category C whose objects are raw l-terms of type X in a context G, so obC = Cn×L+l(G,X), where the maps of C are reduction paths. What equivalence relation on paths is needed in order to make the diamond in the Church-Rosser Theorem (Lemma 1.2.4) commute in C? A  canonical choice amongst equivalent paths is given by reducing these redexes from left to right; this is called a standard reduction: see [Bar81, Definition 11.4.1].

  35. By considering the action of substitution in the l-calculus, show that the equivalence relation of the previous exercise is needed to make horizontal composition in the 2-category \Frak Cn® of contexts, raw l-terms and bh d-reduction well defined. Use it to characterise normal l- terms, distinguishing them from terms which reduce to themselves.

  36. Show that there is a natural transformation between parallel group homomorphisms iff they are conjugate. Give an example of a strong equivalence (Definition  4.8.9(b)) between groups for which h and e are not determined by the isomorphisms F and U involved.

  37. A category is skeletal if A º BÞ A = B; in particular a preorder is skeletal iff it is antisymmetric, ie a poset. Show that any preorder is weakly equivalent to a poset in a unique way, up to unique isomorphism (Proposition  3.1.10). For any category C show (using Choice) that there are equivalence functors C® D and D® C for some skeletal category  D. By considering the groupoid with exactly two objects and exactly two morphisms in each hom-set, show that these are not unique. Discuss this in the case of the fundamental groupoid of a topological space (Example 4.1.7(i)).

  38. Show how to compose and invert strong equivalences, and how to compose equivalence functors. Show also that equivalence functors are confluent ( cf Exercise  3.27).

  39. Which parts of Definition  4.4.8 are invariant under weak equivalence? What are the invariant versions of those which are not, and also of injectivity and surjectivity on objects?

  40. Let C be a category with finite products. Show that the Yoneda embedding \H(-):C\hookrightarrow SetCop (Theorem  4.8.12(b)) preserves products. [Hint: see Proposition 3.2.7(a) and Remark  4.5.9.]

  41. For any small category C, show that S º SetCop is cartesian closed. [Hint: [F® G](X) = S(\HX,[F® G]) = S(\HXx F,G) by the Yoneda Lemma, Theorem 4.8.12(c).] Deduce that the Yoneda embedding preserves function-spaces. (See Exercise 3.30 for the poset version.)

  42. Find a category C (which need only have two objects) in which the Schröder-Bernstein Theorem (Exercise  3.63) fails. Using the Yoneda embedding, show that it also fails in SetCop. Since this is a topos (model of Zermelo type theory), this theorem relies on excluded middle.

  43. Let X be a topological space. Show how to define the path category C, whose objects are the points of X and whose morphisms x® y are continuous functions f:[0,n]® X from real intervals of length n with f(0) = x and f(n) = y. [Hint: composition of paths adds lengths.]

    A homotopy f® g between paths of the same length n is a function h:[0,n]x[0,1] with h(t,0) = f(t), h(t,1) = g(t), h(0,s) = x and h(n,s) = y. Modify this definition to allow f and g to have different lengths, and in particular so that f;f- and f-;f are homotopic to identities in C, where f-(t) = f(n-t). Define a bi-category of points, paths and homotopies.

    Now show that the existence of a homotopy f® g is an equivalence relation, and that its quotient is a groupoid, the fundamental groupoid p1(X) of X.

  44. Show that evaluation has the dinaturality property on the left.

    omitted diagram environment        omitted diagram environment

  45. Show that the fixed point operator \YYX:XX® X (Proposition 3.3.11) satisfies the dinaturality property on the right, and conversely that any transformation with this property yields fixed points. [Hint: put Y = X and consider id Î XX.]

  46. Formulate the general notion of dinaturality.

  47. Let C be any category. Taking Á to be Æ, {·} , {·® ·}, {·\rightrightarrows ·} and {·® ·® ·}, describe [Á® C].

  48. Taking G to be successively {·} , {·® ·} and {·® ·® ·} use the universal property to show that the exponential [X ® Y] in the cartesian closed 1-category Cat must have as objects the functors X® Y, as morphisms the natural transformations between such functors and as composition vertical composition of natural transformations. Finally, use the diagram with four objects to show that this is associative.

  49. The proof of Theorem 4.8.10 defined the l-abstraction [(P)\tilde] of any functor P:GxX® Y. Show how to define [(y)\tilde] for any natural transformation y:P® Q between such functors. [Hint: replace G by Gx{ ·® ·}]. Show that this is natural in the sense of Definition  4.7.2(c), preserves vertical composition, and defines a bijection between the natural transformations P® Q and [(P)\tilde]® [(Q)\tilde].

  50. Write down the definition of a 3-category, together with its notions of composition and the laws which hold between them. Give some geometrical and categorical examples. [Hint: a ``middle four'' law between any two levels suffices: there is no ``middle eight.'']

  51. By a pullback in a poset is meant the meet of two elements which have a common upper bound (Exercises 3.5, 3.20 and 3.34). Let C be the category of posets with pullbacks and pullback-preserving monotone functions. For X,Y Î obC, write [X® Y] for C(X,Y) with an order relation which is to be determined; show that for ev:[X ® Y]x X® Y to preserve pullbacks (f £ g)Þ "x,x¢.x¢ £ XxÞ fx¢ = fxÙgx¢ is needed. Show that this does in fact make C cartesian closed.

    Let V be the three-point poset {no ³ ^ £ yes}. Show that there is no pullback-preserving function por:VxV® V with por(no, no) = no and por(yes, ^) = yes = por(^,yes).