
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
pullbackpreserving 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 PERmaps, 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^{ Cop}. 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^{Cop}.

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_{0} º \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 LaneKelly laws for associativity and commutativity
of x, is known as a pcategory. 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^{n} 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} º N^{m} in
CMon then n = m.

Let C be a CMonenriched
category, ie each homset 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_{0};n_{0}, p_{1};n_{1} ]:Xx Y º X+Y. Show that the category is CMonenriched
.

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 CMonenriched structures.

Use van Kampen's theorem to show that the fundamental
group of the circle S^{1} is Z. [Hint: U and V are open intervals
and W is the disjoint union of two open intervals.]

Let \typeM_{0} and \typeM_{1} be modules for the
commutative rings \typeR_{0} and \typeR_{1} respectively. Show
that their coproduct in the category of ringswithmodules is the module
(\typeM_{0}Ä\typeR_{1})Å(\typeR_{0}Ä\typeM_{1})
for the ring \typeR_{0}Ä\typeR_{1}.

(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^{Y}x 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Úba Î 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 twoelement 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^{2} = a, b^{2} = 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 ^{s0}Y+N \rightharpoonup ^{s1}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_{0}(n) and n_{1}(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 singlesorted 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 socalled 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 ^{ e}N\twoheadrightarrow ^{f}Z/(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 diagramchasing 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 zigzags that b is surjective.
 (d)
 For general c, deduce that
Y\twoheadrightarrow X×_{Q} S in the righthand 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.