Practical Foundations of Mathematics

Paul Taylor

5.9 Exercises V

Show that any group or groupoid, considered as a category, has pullbacks, cf Exercise 4.17. [Hint: division.]
(Bob Paré) In the diagram on the left, suppose that \;\nearrow = \id_Y and
\nearrow ;\;| = | ;\;|. Show that (\;|) is idempotent (Definition 1.3.12), so (assuming that idempotents split in the category, cf Exercise 4.16) we may let
\;| = q; m with m;q = \id_Q. Show that \nearrow ;q = | ;q and q is the coequaliser of \nearrow and |. It is an absolute coequaliser in the sense that (being equationally defined) it is preserved by any functor.
Barry Jay observed that (\nearrow ,|):X\rightrightarrows Y describes a binary ``reduction'' relation on Y with a normal form (defined by \). omitted diagram environment
Similarly, in the diagram on the right, suppose that the four pairs are split ( \;\nearrow = \id_W, etc ) and that the four squares NŽ S, SŽ N, WŽ E and EŽ W commute. Show that S is the pushout of \nearrow and \nearrow ˘. In fact S is the absolute coequaliser of \nearrow and | = \nearrow ˘ ;\˘;\nearrow .
Some of these conditions are redundant. Let e and e˘ be idempotents on any object N such that e;e˘; e = e˘;e. Then in the Karoubi completion (Exercise 4.16), the objects e˘; e and e˘;e;e˘ are isomorphic quotients (but not isomorphic subobjects) of N and provide the absolute pushout.
Show that if S has a terminal object then there is an isomorphism SŻ 1 ş S, and conversely that \id_X is the terminal object of SŻ X.
Show that products in SŻ X are exactly pullbacks in S over X.
Suppose that a;\nearrow = \id_Z, b;q = \id_X, a˘;\nearrow ˘ = \id_Y and the two lower squares are pullbacks: omitted diagram environment Show that the upper square commutes, and is also a pullback. [Hint: show that a;b;\nearrow ˘;q˘ = id and use Lemma 5.1.2.]
Investigate pullbacks and equalisers in the categories Pfn, IPO, Pos^\dashv and Rel.
Let C be a category with pullbacks (equalisers), and Á any small category. Show that the functor category C^Á also has pullbacks (equalisers), constructed pointwise. [Hint: cf Lemma 3.5.7.]
Let Pbk be the category whose objects are small categories with binary pullbacks and whose morphisms are pullback-preserving functors. Show that Pbk is cartesian closed, the morphisms of the functor category being cartesian transformations, ie those natural transformations such that the square in Definition 4.8.1 is a pullback ( cf Exercise 4.51).
(Giuseppe Rosolini) A PER (partial equivalence relation) is a symmetric transitive binary relation on N. A PER R names an object, which we may think of more concretely as the set N/R of equivalence classes under R; these are disjoint, but their union need not be N, as we have not required R to be reflexive.

(a)

Considering f,g Î N as Gödel numbers for partial recursive programs N\rightharpoonup N, write f[RŽ S]g if f and g induce the same function N/RŽ N /S, and this is total. Formulate this condition directly in terms of the binary relations R and S and show how to define a cartesian closed category with exponential [RŽ S].

(b)

Let f S g be the equivalence relation ``f terminates iff g does,'' where these are programs which run without being given any input (they have type 1\rightharpoonup 1). Define partial maps by relaxing the totality requirement on PER-maps, and show that S is a support classifier.
Show that a mono in Pos or Dcpo is regular iff it is full. Find a subdcpo of the lazy natural numbers whose Scott topology (Definition 3.4.7ff) is not the subspace topology.
Construct the map SŽ W in Definition 5.2.10 and explain why it is mono and is a semilattice homomorphism.
Let C be any small category and X Î obC. A class R Ě morC of generalised elements of X, ie maps a:GŽ X, is called a sieve or crible on X if it is closed under precomposition with any u:DŽ G. Show that a sieve on X is exactly a subobject of \H_X in Set^{C^op}. Let W(X) be the set (indeed complete lattice) of sieves on X, and write T_X Î W(X) for the sieve of all generalised elements. Show how to make W:C^op Ž Set into a functor and T:1Ž W a natural transformation, and that this is the subobject classifier of Set^{C^op}.
Formulate what it is to be a category in Gpd (the category of groupoids and homomorphisms). Show how any small category (in the ordinary sense) can be regarded as such an internal category, in such a way that it is skeletal there ( cf Exercise 4.37), in a sense to be defined.
(Giuseppe Rosolini, [RR88]) Given partial maps f:Z\rightharpoonup X and g:Z \rightharpoonup Y, show how to define f,g:Z \rightharpoonup Xx Y and hence x as an endofunctor of P( S,M). [Hint: take the intersection of their supports.] Although the symbol x no longer denotes the categorical product, show that the projection p₀ ş \p_X,Y:Xx YŽ X is natural in X but that the corresponding square for Y need not commute but involves an inequality. The diagonal, \d_X:XŽ Xx X, however, remains natural, and

.75 omitted array environment

A category \nearrow [thick] equipped with a (tensor) ``product'' functor x:\nearrow [thick]x\nearrow [thick] Ž \nearrow [thick] and natural transformations d: idŽ (-x-), \p_-,X:-x XŽ id and \q_X,-:Xx-Ž id, satisfying these laws and the Mac Lane-Kelly laws for associativity and commutativity of x, is known as a p-category. Construct \supp_X,Y:\nearrow [thick](X,Y)Ž \nearrow [thick](X,X) and identify S and M within \nearrow [thick]. Finally, show that (\nearrow [thick],x) has a full embedding \nearrow [thick]\hookrightarrow P(S,M) such that x restricts to the categorical product in S.
Similarly characterise the product structure using the category composed of relations, and, given an allegory satisfying your conditions, show how to embed it in a category of relations (Proposition 5.8.7).
Show how the Floyd rules (Remark 4.3.5) define the category of virtual objects (contexts with midconditions) in Remark 5.3.2 .
By giving the matrices for the (co)projections, (co) diagonals and (co)pairing, show that

(a)

R^n+m is the product of Rⁿ and R^m in Vsp and CRng;

(b)

it is also their coproduct in Vsp;

(c)

R^nxm is their coproduct in CRng.
Show that if Nⁿ ş N^m in CMon then n = m.
Let C be a CMon-enriched category, ie each hom-set C(X,Y) is a commutative monoid (written using 0 and +) and the composition (;):C(X, Y)xC(Y,Z)Ž C(X,Z) is a monoid homomorphism. Show that the terminal object (if any) is also initial and any product also carries a coproduct structure.
Conversely, show that in any category with a zero object (Definition 5.4.3), the zero map is preserved by composition on either side with any map. Suppose further that binary products and coproducts exist and [p₀;n₀, p₁;n₁ ]:Xx Y ş X+Y. Show that the category is CMon-enriched .
Show that Rel ş Rel^op and that the product and coproduct are both given by disjoint union. What happens in CSLat and SLat? Describe the CMon-enriched structures.
Use van Kampen's theorem to show that the fundamental group of the circle S¹ is Z. [Hint: U and V are open intervals and W is the disjoint union of two open intervals.]
Let \typeM₀ and \typeM₁ be modules for the commutative rings \typeR₀ and \typeR₁ respectively. Show that their coproduct in the category of rings-with-modules is the module (\typeM₀Ä\typeR₁)Ĺ(\typeR₀Ä\typeM₁) for the ring \typeR₀Ä\typeR₁.
(Only if you know some hyperbolic geometry.) Considering the matrices (( 0 -1 ) || 1 1 ) and ( 0 1 || ( -1 0 )) as elements of PSL(2,Z), show that it is the coproduct of the groups Z/(3) and Z/(2).
Explain how the maps (GxY)+(GxN)Ž G x(Y+N) given in Definition 5.5.1 arise from the universal properties of + and x, and why they are equal. Show that they are invertible in a cartesian closed category. Do the same for X^Y+Z ş X^Yx X^Z and (X^Y)^Z ş X^{Yx Z}. Show that these isomorphisms are natural in all three variables, and relate them to Exercise 1.22, Remark 2.3.11 and Proposition 3.6.14(a).
Show that this square is a pushout in any category which has coproducts, and that it is also a pullback in an extensive category: omitted diagram environment In other words, if two sets Y˘ = X+Y and Z˘ = X+Z have a common decidable subset X then, within their union, they intersect only in X. Deduce Proposition 5.8.10 for decidable subsets. Although all four maps are monos, the mediator from the pushout to a commuting square of monos need not be mono, since it may identify some y Î Y and z Î Z.
The following similar property holds in Pos . Suppose X Ě Y˘ and X Ě Z˘ are full subposets (and the underlying sets are decidable subsets). Then Y˘ and Z˘ are full subposets of the union, intersecting only in X. Deduce that it holds for embeddings (Example 3.6.13(b)).
Let A,B Ě X be ideals of a distributive lattice and f :AŽ Q, g :BŽ Q be Ú- semilattice homomorphisms which agree on AÇB. Show that if aÚb = a˘Úb˘ then f (a)Úg (b) = f (a˘)Úg (b˘), where a,a˘ Î A and b,b˘ Î B. Deduce that, with C = {aÚb|a Î A,b Î B} Ě X, there is a unique Ú-semilattice homomorphism p:CŽ Q which restricts to f and g .
Characterise finite products and coproducts in Loc. [NB: The two-element lattice {^,T} is not complete without excluded middle (Example 3.2.5(h)); Example 3.9.10(e) gave the product in Loc .]
Show that partitions of C Î ob Loc ( ie isomorphism classes of coproduct diagrams AŽ C Ź B) correspond to pairs a,b Î C with
a Ůb = ^ and aÚb = T. Similarly partitions in CRng^op are given by pairs with a² = a, b² = b, ab = 0, a+b = 1. Hence show that Loc and CRng^op are extensive.
Show that binary coproducts commute with wide pullbacks in an extensive category. Does the analogous property hold for distributive lattices? Let L be a disjunctive theory; show that Mod (L) has wide pullbacks.
Show how to swap the values of two variables using the direct declarative language with assignment. Using this and conditionals, write a program to sort three objects with respect to a given trichotomous order relation. How many comparisons are needed in the worst case?
Show that the coproduct in S extends to a functor on P(S,M), where it remains the coproduct. It is not stable disjoint there: explain why we do not want it to be.
Let S be a distributive category with a class M of supports to which yes,no:1 \rightrightarrows 2 belong. Suppose that, for each pair of objects, there are partial maps N\leftharpoonup ^s₀Y+N \rightharpoonup ^s₁Y such that n_i;s_j = id if i = j and ^ otherwise. Show that S is extensive.
Variant records of type Y+N are typically implemented by coding the elements n₀(n) and n₁(y) as 0,0,n,1,y,0 Î 2xYxN respectively, where 0 is a ``dummy value'' of type Y and N. Formulate the midcondition f which defines this subobject ( cf Example 2.1.7). Making clear where extensivity is used, show that the virtual object is indeed the coproduct Y+N, and define the switch, satisfying the rules of Remark 2.3.10. Modify this construction to remove the assumption that the unused field is initialised to the dummy value. Generalise it to the case where the components are themselves (possibly uninhabited) virtual objects; the dummy value now belongs to the underlying real objects but not necessarily to the virtual ones.
Show that the pullback of a split epi against an arbitrary map is another split epi. Conversely, show that every split epi is a pullback of its kernel projection, if the kernel pair exists.
Let L be a single-sorted algebraic theory. Show that f:AŽ B is a mono in Mod(L) iff it is an injective function, and a regular epi iff it is surjective. [Hint: Propositions 5.2.2(a) and 5.6.8.]
Characterise the inverse images of ^ and T under homomorphisms in DLat and of 0 and 1 in CRng.
Let K\hookrightarrow Ax A be a relation in any category. Define when it is a congruence (Definition 5.6.3) without constructing new pullbacks. [Hint: quantify over commutative diagrams with a variable object G in the place of the pullback cube.]
Prove the analogues of Theorem 5.6.9 for CSLat and Frm, and show how to use a closure operator on an object (not its square) to code kernel pairs, analogously to Lemma 5.6.14. [Hint: cf Theorem 3.9.9.]
Let XxXŽ W be the characteristic map of an equivalence relation K on X in Set. What is the image factorisation of its exponential transpose, X\twoheadrightarrow I \hookrightarrow W^X?
How do you recover the kernel pair of e:A \twoheadrightarrow Q from the subset Q Ě A in Lemma 5.6.14?
Explain the relationship between factorisation systems and the so-called isomorphism theorems for groups, rings and vector spaces.
By Proposition 3.8.14, the orthogonality relation e^m in Definition 5.7.1 gives rise to a specialisation order. Investigate its relationship to the category, and what it means to have enough epis or monos.
Suppose that the rectangle is a pullback and contains a mono and a stable surjection as shown. Show that the two squares are pullbacks. omitted diagram environment [Hint: form the pullback of Y\twoheadrightarrow Q against GŽ Q ; this result holds for any stable factorisation, not just the image one.]
Let M be closed under pullback, and m, \ Î M. Prove the following tighter form of Lemma 5.7.6(e), that if e^(m; \) and e^\ with respect to \ then e^m ( cf Exercise 9.27).
Let E be the class of functors which are full and essentially surjective, and M those that are faithful (Definition 4.4.8). Show that this is a factorisation system in Cat.
Let U be a relation. Explain what categorical structure is needed to show that UČD and UČU^op are respectively its reflexive and symmetric closures, and that UČD is confluent if U is functional.
Show that, in a pretopos, the (stable) union UČV Ě X is computed as the image of U+VŽ X.
In a pretopos, show that the pushout of a mono against an arbitrary map is again a mono, and that the square is also a pullback. Deduce that if the opposite category has equalisers then it is regular.
Let (ˇŽ ˇ)\twoheadrightarrow ^eN\twoheadrightarrow ^fZ/(3) in Cat. In Proposition 5.8.3, find L and discuss how K, P and M might be defined, noting that e is neither replete nor full. [Hint: obK ş 2+4xN in Definition 7.3.8.]
In the diagram, omitted diagram environment

(a)

Given f,g,b,s,q,c with the right square a pullback, suppose that f^*b and g^*b exist, a priori with different vertices V and W. Show that a,h,k may be chosen so that the two left squares are pullbacks.

(b)

In a regular category, suppose that the q and s are coequalisers, (h,k) and (f,g) are kernel pairs, and that the two left squares are pullbacks. Show that the right hand square is also a pullback. [You have to be pretty good at diagram-chasing to do this.]

(c)

In Set, suppose again that the left squares are pullbacks and the rows are arbitrary coequalisers. Assume also that c = id, and show by induction on zig-zags that b is surjective.

(d)

For general c, deduce that Y\twoheadrightarrow X×_Q S in the right-hand square.

(e)

With S = Q = 1, U = X = 2, V = Y = 6, find maps in Set satisfying these conditions, so b need not be an isomorphism.

The reason for the difficulty is that the fibres of b are carried isomorphically to one another by the transitions. If these have (unoriented) cycles, these isomorphisms may give an automorphism of a single fibre. This can't happen if b is mono or U\rightrightarrows X is functional and acyclic.