Subj: Stable functors
Date: Tue, 03 Mar 92 13:58:08 EST
From: Walter Tholen
Here are some more names for stable functors, in addition to those
provided by Paul Taylor. I believe that they first appeared in a paper
by J.J. Kaput (Ill.J. Math. 16 (1972) 86-94) under the name "locally
(left) adjunctable functor". I used "locally right adjoint functor"
in my paper with Borger (Manuscripta Math. 19 (1976) 19-45) and in the
more comprehensive paper (Comment. Math. Univ. St. Pauli 28 (1979) 179-
202). Both papers deal with the particular case of "locally reflective
subcategories" for which there are new results to be found in a recent
paper by Adamek and Volger ("On locally reflective categories of struct-
ures").
Walter Tholen
=====================================================================
Subj: re: Stable functors
Date: Thu, 5 Mar 92 10:26:01 EST
From: barr@triples.Math.McGill.CA (Michael Barr)
I don't much like the locally as suggested by Walter, but it is probably
too late to do much about it. I prefer multi-adjoint. Locally P means that
P holds in every slice.
Mike
=====================================================================
Subj: re: stable functors
Date: Thu, 5 Mar 92 18:05+0000
From: cbj@dcs.edinburgh.ac.UK
Here is another contribution to the baptism of "stable functors".
When a functor F represents a datatype construction, such as lists,
trees or matrices, then it typically preserves pullbacks (in fact, all
connected limits) and when applied to the terminal object 1 yields the
"basic shape" F1 whose "elements" are the shapes of general data. For
example, the list functor applied to 1 is a NNO since the shape of a
list is its length. In this setting it is attractive to call
pullback-preserving functors "shapely".
Similarly, the natural transformations representing the generic
operations on the datatypes (e.g. the appending of lists or flattening
of trees) often have the property that the commuting squares arising
in their definition are actually pullbacks. Such natural
transformations are commonly known as cartesian natural
transformations, but in this setting could also be called "shapely
natural transformations". Thus there is a 2-category consisting of
categories with finite (connected?) limits, shapely functors and
shapely natural transformations, which is convenient for studying the
general theory of datatypes.
Barry Jay
=====================================================================
Subj: Stable functors
Date: Mon, 09 Mar 92 12:32:46 EST
From: Walter
No problem with Mike's remark that "locally P" should mean "P holds in
every slice". This is for a property of a category. When using "locally
right adjoint" almost two decades ago I asked myself whether the func-
tor A/a --> B/Fa induced by F:A-->B (and an A-object a) is an accep-
table notion of "slice of the functor F", decided that would be okay,
and therefore used the name. Diers' notion of multi-adjointness gives
more than just right adjointness of the slices A/a --> B/Fa : there is
a smallness condition on the number of non-isomorphic "local units",
and these are F-epic. Hence it would be confusing to use the name in a
more general sense now.
I may be wrong in assuming that the notion of "slice of a functor"
as above is acceptable. Comments welcome.
Walter Tholen.
=====================================================================
Subj: Re: Stable functors
Date: Tue, 10 Mar 92 07:39:22 EST
From: barr@triples.Math.McGill.CA (Michael Barr)
I guess Walter is right. At least in the case of an initial object, it is
the case that having a multi-initial object is having an initial object
in each slice. What I hadn't thought through was the fact that if a
category has a multi-initial object and has a terminal object, then it has
an initial object. So having an initial object in each slice does not
imply having an initial object (whereas for most properties P, locally P
implies P). There is a minor problem with duality. While it is true
that a category with a multi-terminal object has a terminal object in
each slice, that is also true of a category without a multi-terminal
object. So you want that for every co-slice.
Michael
=====================================================================
Subj: Latest corrections to TTT
Date: Tue, 10 Mar 92 10:12:18 EST
From: barr@triples.Math.McGill.CA (Michael Barr)
\documentstyle{article}
\input diagram
\textheight9in \headsep 0in \headheight0in \topmargin0in
\textwidth 6.5in \oddsidemargin0in
\long\def\ig#1{\relax}
\def\pf{\par\addvspace{\medskipamount}\noindent Proof.\enskip}
\mathchardef\Bsc="0242
\let\imp=\Rightarrow
\let\meet=\wedge
\font\tensfb=cmssbx10
\makeatletter
\def\@xpt{%
\textfont11=\tensfb \scriptfont11=\tensfb \scriptscriptfont11=\tensfb
} \makeatother
\mathchardef\T="0B54
\mathchardef\P="0B50
\def\lnm#1{Lecture Notes in Mathematics {\bf#1}}
\def\o{\circ}
\def\op{^{\rm op}}
\def\mathrm#1{\expandafter\def\csname#1\endcsname{\mathop{\rm#1}\nolimits}}
\def\mathbf#1{\expandafter\def\csname#1\endcsname{\mathop{\rm\bf#1}\nolimits}}
\def\x{\times}
\mathrm{id}
\mathrm{Hom}
\mathrm{Set}
\mathrm{Sh}
\mathrm{Sub}
\mathbf{Cat}
\begin{document}
\begin{center}{\Large\bf Corrections to {\it Toposes, Triples and
Theories}}\\
Michael Barr and Charles Wells\\ \today\end{center}
The corrections are listed by page number. The name in parentheses
after the page number shows who told us of the error.
\begin{trivlist}
\item[GENERAL COMMENT] Our text is intended primarily as an exposition
of the mathematics, not a historical treatment of it. In particular, if
we state a theorem without attribution we do not in any way intend to
claim that it is original with this book. We note specifically that
most of the material in Chapters 4 and 8 is an extensive reformulation
of ideas and theorems due to C. Ehresmann, J. B\'enabou, C. Lair and
their students, to Y. Diers, and to A. Grothendieck and his students.
We learned most of this material second hand or recreated it, and so
generally do not know who did it first. We will happily correct
mistaken attributions when they come to our attention.
\item[p. 9] (Peter Johnstone). Exercise (SGRPOID) is incorrect as it
stands;
a semilattice without identity satisfies (i) through (iii) but is not a
category. Condition (iii) must be strengthened to read:
Say an element $e$ has the {\bf identity property} if $e\o f= f$
whenever $e\o f$ is defined and $g\o e= g$ whenever $g\o e$ is
defined. Then we require that for any
element $f$, there is an element $e$ with the identity property
for which $e\o f$ is defined and an element $e'$ with the identity
property for which $f\o e'$ is defined.
\item[p. 26] (D. \v{C}ubri\'c). Property (ii) of Exercise (SUBF)
should read ``If $f:A\to B$, then $F(f)$ restricted to $G(A)$
is equal to $G(f)$.''
\item[p. 27] (Dwight Spencer), second line from bottom: $T:S\to T$
should be $t:S\to T$.
\item[pp. 39-40] (Peter Johnstone). It should be noted that the product
of an empty collection of objects in a category must be a terminal
object. Then the phrase after the comma on line 4 of p. 40 should read,
``which by an obvious inductive argument is equivalent to requiring that
the category have a terminal object and that any two objects have a
product.''
\item[p. 43] (Peter Johnstone). Exercise (PROD)(b) should read: ``Show
that if a category has a terminal object and all products of pairs of
objects, then it has all finite products.''
\item[p. 49] (Peter Johnstone). Exercise (FCR) uses the concept of
small category without defining it. It is used in the main body of the
text on page 66 and later, and ``small sketch''{} occurs on p. 146. A
graph or a category is {\bf small} if its arrows constitute a set. A
sketch is small if its graph is small and its cones and cocones
constitute a set. In connection with the discussion of foundations on
page ix of the Preface, no matter what set theory is used, one is going
to have to deal with categories and graphs whose arrows do not
constitute sets.
\item[p. 49] Closing parenthesis missing at end of Exercise (EAPL)(a).
\item[p. 53] (Dwight Spencer) The display in the middle of the page
should be: $i(T,LA)(L(f\o h)) = \eta A\o f\o h = RLf\o \eta D\o h =
RLf\o i(T,LD)(Lh) = i(T,LA)(Lf\o Lh)$
In diagram (7), just below, the vertical arrows should be pointing
upward.
\item[p. 54] lines 5 from the bottom: (Dwight Spencer) change ``arrow
for'' to ``element of the functor''. Add to the last sentence ``(A
universal element of $\Hom(A,R(-))$ is called a {\bf universal arrow}
for $R$ and $A$.)''
\item[p. 55] line 4: (Dwight Spencer) change $RLA$ to $RWA$.
\item[p. 55] line 14: (Dwight Spencer) Change $Ry$ to $y$.
\item [p. 64] (Dwight Spencer) The diagram at the bottom should be
labeled (1). (I don't think it is actually referred to, but the diagram
numbering in this section begins with (2).)
\item[p. 68] (D. \v{C}ubri\'c). The end of line 5 should be
$\Sub(F\x E)$.
\item[p. 69] (V. Pratt) The reference to Section 1.4 (line 13) should be
to Subsection, ``Global elements'' on page 24, more precisely the second
paragraph.
\item[p. 72] (D. \v{C}ubri\'c). In the next to last line,
$p:LF\to X$.
\item[p. 75] Geometric morphisms are discussed in Chapter 6, not
Chapter 5.
\item[p. 90] (D. \v{C}ubri\'c). In diagram (1), the leftmost
arrow should be labeled $T\mu$.
\item[p. 94] (D. \v{C}ubri\'c). In the next to last line,
$R:\Set/|X|\to\Sh(X)$.
\item[p. 95] (D. \v{C}ubri\'c). The end of Proposition 2
should say, ``is a cotriple on $\cal B$''.
\item[p. 100] (D. \v{C}ubri\'c). Line 3 should have
$U^{\sf T}:{\cal C}^{\sf T}\to{\cal C}$,
$F^{\sf T}:{\cal C}^{\sf T}\to{\cal C}$.
\item[p. 110] (D. \v{C}ubri\'c). In Diagram (19), the arrow
$\eta C:TC\to T^2C$ should be $T\eta C:TC\to T^2C$.
\item [p. 125] Third line from bottom. The word ``morphism'' is
repeated.
\item[p. 126] (Felipe Gago-Couso). Proposition 1 has an omitted
hypothesis. We include here a complete restatement of the proposition
and its proof:
\item[]The following proposition gives one method of constructing
morphisms of triples. We are indebted to Felipe Gago-Couso for finding
the gap in the statement and proof in the first edition and for finding
the correct statement.
\noindent{\bf Proposition 1.} {\em In the notation of the preceding
paragraphs, let
$\sigma:TT'\to T'$ be a natural transformation for which
\begin{center}
\qtriangle[T'`TT'`T';\eta T'`\id`\sigma]
\end{center}
%\ig{\bfig
% \eta%T'
% T'----------\>TT'
% \ |
% \ |
% \ |
% \ |
% \ |
% (3) \ |
% \id \ |\sigma\l
% \ |
% \ |
% \ |
% \ |
% \ |
% \ |
% \vvb
% T'
%\efig}
and
\begin{center}
\xext=1500 \yext=700
\adjust[`\mu T';`T\sigma;`\sigma;`\mu']
\bfig
\putsquare(0,200)[TTT'`TT'`TT'`T';\mu
T'`T\sigma`\sigma`\sigma]
\putsquare(1000,200)[TT'T'`TT'`T'T'`T';T'\mu%
`\sigma T'`\sigma`\mu']
\put(250,0){\makebox(0,0){{\rm(a)}}}
\put(1250,0){\makebox(0,0){{\rm(b)}}}
\efig
\end{center}
% \ig{\bfig
% \mu%T' T\mu'
% TTT'------\>TT' TT'T'------\>TT'
% | | | |
% | | | |
% | | | |
% (4) T\sigma| \sigma| \sigma%T'| \sigma|
% | | | |
% | | | |
% \v \v \v \v
% TT'-------\>T' T'T'-------\>T'
% \sigma \mu'
%
% $(a)$ $(b)$
% \efig
% }
commute. Let $\alpha = \sigma\o T\eta':T\to T'$. Then
$\alpha$ is a morphism of triples.}
\pf That (1) commutes follows from the commutativity of
\begin{center}
\xext=500 \yext=1000
\adjust[`\eta;`\eta';`T\eta';T'`]
\bfig
\resetparms
\putsquare(0,500)[\id`T`T'`TT';\eta`T'`T\eta'`\eta']
\settriparms[0`1`1;500]
\putqtriangle(0,0)[``T';`\id`\sigma]
\efig
\end{center}
% \ig{\bfig
% \eta
% \id------------\>T
% | |
% | |
% | |
% | |
% \r \eta'| \r T\eta'|
% | |
% | |
% \v \eta' \v
% T'----------\>TT'
% (5) \ |
% \ |
% \ |
% \ |
% \ |
% \id \ |\l\sigma
% \ |
% \ |
% \ |
% \ |
% \ |
% \ |
% \ |
% \vvb
% T'
% \efig
% }
In this diagram, the square commutes because $\eta$ is a natural
transformation and the triangle commutes by (3).
The following diagram shows that (2) commutes.
\begin{center}
\bfig
\putmorphism(0,2100)(0,-1)[``T\eta'T]{1400}1l
\putmorphism(0,2100)(1,0)[TT`T`\mu]{700}1a
\putmorphism(0,2100)(1,-1)[`TTT'`TT\eta']{700}1l
\putmorphism(700,2100)(1,-1)[`TT'`T\eta]{700}1r
\put(700,1750){\makebox(0,0){1}}
\putmorphism(700,1420)(1,0)[\phantom{TTT'}`\phantom{TT'}`\mu
T']{700}1a
\putmorphism(700,1380)(1,0)[\phantom{TTT'}`%
\phantom{TT'}`T\sigma]{700}1b
\putsquare<0`1`1`1;700`700>(700,700)[TTT'`TT'`TT'TT'`TT'T';`T\eta'TT'``]
\putmorphism(700,700)(1,0)[\phantom{TT'TT'}`%
\phantom{TT'T'}`TT'\sigma]{700}1a
\put(300,1400){\makebox(0,0){2}}
\put(950,1050){\makebox(0,0){3}}
\settriparms[0`1`0;700]
\putbtriangle(1400,700)[``TT';T\eta'T'`id`]
\putmorphism(1400,700)(1,0)[\phantom{TT'T'}`%
\phantom{TT'}`T\mu']{700}1a
\put(1600,1050){\makebox(0,0){6}}
\putsquare<1`1`0`1;700`700>(0,0)[TT'T`\phantom{TT'TT'}`T'T`T'TT';%
TT'T\eta'`\sigma T``T'T\eta']
\putmorphism(700,0)(1,0)[\phantom{T'TT'}`%
\phantom{T'T'}`T'\sigma]{700}1b
\putsquare<0`0`1`1;700`700>(1400,0)[``T'T'`T';``\sigma`\mu']
\putmorphism(700,700)(0,-1)[``\sigma TT']{700}1m
\putmorphism(1400,700)(0,-1)[``\sigma T']{700}1m
\put(300,350){\makebox(0,0){4}}
\put(1050,350){\makebox(0,0){5}}
\put(1750,350){\makebox(0,0){7}}
\efig
\end{center}
% \ig{\bfig
% \mu
% TT-------------\>T
% |\ \
% | \ \
% | \ \
% | \ \
% | \ \
% | \ \
% | \ \
% | \ 1 \
% | TT\eta'\ T\eta'\
% | \ \
% | \ \
% | \ \
% | \ \
% | \lr \mu%T' \lr
% | TTT'-----------\>TT'
% T\eta'T| 2 | -----------\>| \
% | | T\sigma | \
% | | | \
% | | | \
% | T\eta'TT'| 3 T\eta'T'| 6 \\$id$\l
% (6) | | | \
% | | | \
% \v TT'T\eta' \v TT'\sigma \v T\mu' \lr\l
% TT'T---------\>TT'TT'-------\>TT'T'----\>TT'
% | | | |
% | | | |
% | | | |
% | | | |
% \sigma%T| 4 \sigma%TT'| 5 \sigma%T'| 7 |\sigma\l
% | | | |
% | | | |
% \v \v \v \v
% T'T---------\>T'TT'---------\>T'T'-----\>T'
% T'T\eta' T'\sigma \mu'
% \efig
% }
In this diagram, square 1 commutes because $\mu$ is a natural
transformation, squares 2 and 3 because $T\mu'$ is and squares 4 and 5
because $\sigma$ is. The commutativity of square 6 is a triple identity
and square 7 is diagram 4(b). Finally, diagram 4(a) above says that
$\sigma\o\mu T'=\sigma\o T\sigma$ which means that although the two
arrows between $TTT'$ and $TT'$ are not the same, they are when followed
by $\sigma$, which makes the whole diagram commute.
Squares 1 through 5 of diagram (6) are all examples of part (a) of
Exercise (GOD), Section 1.3. For example, to see how square 1 fits,
take ${\cal B}$, ${\cal C}$ and ${\cal D}$ of the exercise to be
${\cal C}$, $F=\id$, $G=T'$, $H=T^2$ and $K=T$, and
$\kappa=\eta'$, $\mu=\mu$. Then square 1
is $\eta'\mu$.
\noindent{\bf Corollary 2.} {\em With $T$ and $T'$ as in Proposition
1, suppose $\sigma:T' T \to T'$ is such that $\sigma\o T'\eta =\id$,
$\sigma\o\sigma T' = \sigma\o \eta T:T\to T'$ is a morphism of triples.}
\pf This is Proposition 1 stated in $\Cat\op$ (which means: reverse the
functors but not the natural transformations).
\item[p. 134] (Colin McLarty). In the second through fourth paragraphs
of the proof of (a), every occurrence of ``$L$'' should be ``$W$''.
\item[p. 137] (Jim Otto). Theorem 5 has too few hypotheses and
Proposition 4 too many to apply the latter in the proof of the former.
There are various possibilities of getting it right, including adding
the finite limits and colimits to the hypotheses of Theorem 5.
Nevertheless, Theorem 5 is true as it stands. The problem occurs with
the last sentence of Theorem 5. Probably the best approach is to point
out first that only equalizers and coequalizers are needed and then only
the $U$-contractible ones. Then, if we suppose only the
$U$-contractible equalizers exist (any that exist will be preserved by a
functor that has a left adjoint), that is enough to do Theorem 5
(Exercise, using the fact that the underlying functor of a tripleable
functor creates limits) and from that will follow that the
$U$-contractible equalizers exist.
As for Proposition 4, if we suppose that $\Bsc$ has $U$-contractible
equalizers, the dual of Theorem 5 would imply that $U$-contractible
equalizers exist. Hence sufficient for Proposition 4 is that {\em
either\/} $U$-contractible equalizers or $U$-contractible coequalizers
exist. Does anyone want to find an example to show that any
completeness hypothesis is necessary?
\item[p. 139] (Samuel Eilenberg) The story told at the end of the second
paragraph is not exact. In fact the word was chosen as the manuscript
was in final preparation. Nonetheless, the main point of the story,
the care that went into choosing the name of an important concept,
remains.
\item[p. 139] (F-J de Vries) l. -3: ``subststantially'' should read like
``substantially''
\item[p. 140] (F-J de Vries) l. 9: ``Kiesler'' should be ``Keisler''
General comment about chapters 4 and 8 (C. Lair). In many places we
state that some extension of a functor is unique, when in fact it is
only unique up to isomorphism of functors in the functor category.
These occur on p. 153 (Theorem 4), p. 156 (Theorem 2), and implicitly in
p. 293, Theorem 2 and p. 294, Theorem 1.
\item[p. 146.] C. Lair has told us that Ehresmann proved a more general form
of Kennison's Theorem in Ehresmann [1967a], [1967b].
\item[p. 162] (C. Lair). The sketch for LE categories constructed here
has LE categories with specified limits of finite diagrams as models,
and morphisms of models are functors which preserve the specified
limits. A similar remark should be made about the sketch for toposes on
p. 165.
\item[p. 168] (F-J de Vries) l. -15: ``Kiesler'' should be ``Keisler''
\item[p. 172] Second sentence: $\P$ having a left adjoint does not
imply $T$ does. The sentence and following one should be combined as
follows: ``Since $T$ is the composite of a functor and its right
adjoint, it is the functor part of a triple $(T,\eta:1\to T,\mu:T^2\to
T)$.''
\item[p. 110] (D. \v{C}ubri\'c). Second line in the proof of
Theorem 1 should begin ``map ${\cal E}/A\to {\cal E}$.
\item[p. 179], Proposition 2 (D. \v{C}ubri\'c). This
proposition should say that ${\bf P}'\o L$ is naturally
isomorphic to $L^{\rm op}\o \bf P$.
\item[p. 183] (F-J de Vries) l. -7: Kock [1982] should be Kock [1981]
(SDG)
\item[p. 197] Lemma 3 (Francisco Marmolejo). Dropping the subscript on
the arrows leaves it too ambiguous. Part (a) should read,
``$D\meet(B\imp_AC)=D\meet B\imp_DD\meet C$.''
\item[p. 200], line $-4$ (Francisco Marmolejo). The sentence should be
expanded to, ``Observe that any sheaf is $\j$-closed inside any
separated presheaf. ({\bf Separated} isn't defined until page 233, but
it simply means that in the definition of sheaf in the middle of page
69, the unique existence is replaced by the assumption that there is at
most one element $x$ such that $X|U_i=x_i$.)''
\item[p. 205] (Francisco Marmolejo). In the last line of Exercise TPPB,
change ``induce'' to ``constitutes''.
\item[p. 213], last line (Francisco Marmolejo). Should read, ``products
commute with reflexive coequalizers.'' In fact, a product of a fixed
object with any coequalizer is a coequalizer. This fact follows from
Lemma 6 on page 158-159.
\item[p. 214] The reference, third line from bottom, to section 6.4
should be to section 7.3.
\item[p. 215] (D. \v{C}ubri\'c). In Corollary 7, both
occurrences of ``$E$'' should be ``${\cal E}$''.
\item[p. 225] (D. \v{C}ubri\'c). In Exercise (SEP), ``given''
should be ``give''.
\item[p. 233] ``Epimorphic family'' should be boldface and indexed.
\item[p. 234] second paragraph (J\"urgen Koslowski): Change Corollary 5
of Section 5.4 to Corollary 8 of Section 5.3. Also, Exercise CANON
doesn't exist; delete the reference.
\item[p. 236] (D. \v{C}ubri\'c). In Proposition 4, we should
have noted that (a) and (b) are equivalent by definition. The
last sentence of the proof should read "Hence (b), and therefore
(a), is true.''
\item[p. 238] (B. Howard).
Sums in a category are {\bf disjoint} if for any objects $A$ and $B$,
the commutative diagram
$$
\bfig
\settriparms[1`1`0;400]
\putAtriangle(0,400)[0`A`B;``]
\settriparms[0`1`1;400]
\putVtriangle(0,0)[``A+B;``] \efig
$$
(in which the arrows to $A+B$ are the canonical injections) is a
pullback, and the canonical injections are monic.
\item[p. 242] ``Cocontinuous'', in Theorem 12, was not defined. A
cocontinuous functor is one which preserves all colimits.
\item[p. 250] Fourth line is broken.
\item[p. 250] Theorem 7 is referred to several times elsewhere as
Freyd's embedding theorem, and should be named as such here.
\item[p. 261] second line from bottom: Freyd's Theorem is Theorem 7 of
7.1, not Theorem 5 of 7.2.
\item[p. 267] (F-J de Vries) l. 267: ``Mikkelson'' should be ``Mikkelsen''
\item[p. 293] (Peter Johnstone). In Exercise (TOTO), the maps should be
strictly increasing rather than nondecreasing.
\item[p. 294] We should point out the connections between Theorem 1
here and Theorem 12, p. 242 and Theorem 2, p. 263.
\item[p. 295] second line before exercises. ``Function'' misspelled.
\item[p. 295] (Peter Johnstone). The description of the realizability
topos is completely incorrect; in particular, the realizability topos is
not a classifying topos, so the reference does not belong here at all.
The reference which {\it does} belong here is to Mulry [1982].
\item[p. 296] Same change for Exercise (DLO) as for Exercise (TOTO)
above.
\item[p. 297] (Peter Johnstone and many others). Theorem 1 omits the
very important fact that models of geometric theories have filtered
colimits.
\item[p. 300] The statement on line 6 that filtered colimits of regular
functors are regular deserves some discussion, or at least should be
made an exercise!
\item[p. 301] In connection with the first sentence beginning on this
page, we now know that the category of orthodox semigroups and their
morphisms is the category of models of an LE-sketch and is regular, but
is not the category of models of an FP-sketch. (An orthodox semigroup
is one in which the product of idempotents is an idempotent.)
\item[p. 302] (Peter Johnstone). Because models of geometric theories
preserve filtered colimits (see correction to p. 297), the answer to
Exercise (CYCGRP)(c) is easily seen to be: No.
\item[p. 307] diagram (5). The two rightmost arrows lack labels. The
one from $UB$ to $C$ is $c$ and the one from $C$ to $UB$ is $s$.
\item[p. 318] (Colin McLarty). Exercise (DL) should say that all
composites {\it of length three} are the identity.
\item[p. 325] (Peter Johnstone). In line 15, $(R:C)$ is not a full
subcategory of the comma category $(R,C)$.
\item[p. 337] (F-J de Vries) ``Mikkelson'' should be ``Mikkelsen''
\item[p. 338] (F-J de Vries) ``J.Shonfield'' should read as ``J.R.
Shoenfield''
\end{trivlist}
INDEX, pp. 342ff. Some omissions:
{\obeylines
Beck's Tripleability Theorem, 112.
Butler's Theorem, 135.
epimorphic family, 233.
Freyd's Representation Theorem, 246ff.
Freyd's characterization of natural number objects, 273.}\vskip1ex
\subsection*{Supplemental Bibliography}
\noindent C. Ehresmann, Introduction to the theory of structured
categories. Charles Ehresmann, \oe uvres compl\`etes et
comment\'ees III, 2, 591-676. (Noted by V. Topencharov.)
\vskip1ex\noindent C. Ehresmann, Probl\`emes universels relatifs aux
cat\'egories n-aires. C.R.A.S. 264 (273-276), 1967a.\vskip1ex
\vskip1ex\noindent C. Ehresmann, Sur les structures alg\'ebriques.
C.R.A.S. 264 (840-843), 1967b.
\vskip1ex\noindent C. Ehresmann, Esquisses et types de
structures alg\'ebriques. Bul. Inst. Polit. Ia\c{s}i t.
XIV(XVIII), Fasc. 1-2 (1968), 1-14. Reprinted in
\OE uvres compl\`etes et
comment\'ees IV, 1, 19-33. (Noted by V. Topencharov.)
\vskip1ex\noindent H. Cartan and S. Eilenberg, {\bf Homological
Algebra}. Princeton University Press, 1952. (Noted by Fer-Jan de
Vries.)
\vskip1ex\noindent Anders Kock, {\bf Synthetic Differential Geometry}.
London Mathematical Society Lecture Note Series 51. Cambridge
University Press, 1981. (Noted by Fer-Jan de Vries.)
\vskip1ex\noindent
P. Mulry, Generalized Banach-Mazur functionals in the topos of recursive
sets. J. Pure Applied Algebra, 26 (1982), 71-83.
\vskip1ex\noindent G. Osius, Categorial set theory: a characterization
of the category of sets. J. Pure Applied Algebra, {\bf 4} (1974),
79--119. (Noted by J\"urgen Kozlowski.)
\vskip1ex\noindent G. Osius, Logical and set theoretical tools in
elementary topoi. Model Theory and Topoi, \lnm{445} (1975), 297--346.
(Noted by J\"urgen Kozlowski.)
\end{document}
=====================================================================
Subj: Latest ctcs corrections
Date: Tue, 10 Mar 92 10:20:59 EST
From: barr@triples.Math.McGill.CA (Michael Barr)
\documentstyle[12pt]{article}
\input diagram
\newcounter{lister}
\newenvironment{labeledlist}[1]
{\begin{list}{{\rm#1\arabic{lister}. }}{\usecounter{lister}
}}%begin text
{\end{list}}%
\def\blist#1{\begin{labeledlist}{#1}}
\def\elist{\end{labeledlist}}
\newcommand{\afour}{\oddsidemargin 18pt\evensidemargin 18pt
\textwidth 420pt\textheight 45\baselineskip\advance\textheight by \topskip}
%% Kludge to make article.sty width correct for A4
%% This works only for article.sty using the standard margin given
\textheight8in \headsep 0in \headheight0in \topmargin0in
\textwidth 6.5in \oddsidemargin0in
\mathchardef\Csc="0243
\mathchardef\Dsc="0244
\mathchardef\Esc="0245
\mathchardef\Gsc="0247
\mathchardef\Ssc="0253
\def\lncs#1{Lecture Notes in Computer Science {\bf#1}}
\def\springer{Sprin\-ger-Ver\-lag}
\def\mathrm#1{\expandafter\def\csname#1\endcsname{\mathop{\rm#1}\nolimits}}
\def\mathbf#1{\expandafter\def\csname#1\endcsname{\mathop{\rm\bf#1}\nolimits}}
\mathrm{id}
\mathrm{eval}
\mathrm{mult}
\mathrm{proj}
\mathbf{R}
\mathbf{Set}
\mathbf{Cat}
\mathbf{Mod}
\mathbf{Rel}
\mathrm{Hom}
\def\op{{}^{\rm op}}
\let\x=\times
\def\o{\mathop{\raise.3ex\hbox{$\scriptscriptstyle\circ$}}}
\mathcode`\<="4268 %left delimiter
\mathcode`\>="5269 %right delimiter
\def\inc{\subseteq}
\def\iso{\cong}
\def\[{[\kern-1.3pt [}
\def\]{]\kern-1.3pt ]}
\begin{document}
%\afour
\title{Category Theory for Computing Science: \\ Update}
\author{Michael Barr and Charles Wells}
\maketitle
We intend to maintain
our text, {\bf Category Theory for Computing Science}, Prentice Hall,
1990 (ISBN 0-13-120486-6),
% Our text, {\bf Category Theory for Computing Science}, Prentice Hall,
% 1990 (ISBN 0-13-120486-6) has just been published.
% We intend to maintain the text
in the sense that programmers maintain their programs,
by keeping a list of known errors and also of additions to the text that
we think might be useful. (The latter will probably come in spurts as
we go to meetings and find out about wonderful new applications of
category theory to computing science.)
We will periodically
announce new errata and addenda on the category theory bulletin board.
The latest TeX version of the complete list is available by e-mail or
p-mail from either author.
The update consists of three parts: \ref{errors}: A list of errors discovered
so far. \ref{newtext}: Additional examples, problems and pointers to the
literature. \ref{refs}: Additions and updates
to the list of references, pp. 417ff. of
the text. Page references refer to the text.
Any further corrections or suggestions for additional text will be welcome.
{\footnotesize
\begin{center}\begin{tabular}{ll}
Michael Barr & Charles Wells \\
Department of Mathematics & Department of Mathematics \\
Burnside Hall & Case Western Reserve University \\
McGill University & University Circle \\
805 Sherbrooke St. West & Cleveland, OH 44106-7058, USA \\
Montr\'eal, P. Q., Canada H3A 2K6 & cfw2@po.cwru.edu \\
barr@triples.math.mcgill.ca & \end{tabular}\end{center}
}
\newpage
\section{Errors}\label{errors}
\begin{description}
\item[p. xv] In the Chapter Dependency Chart, there should be a diagonal
line from Chapter 5 to Chapter 7.
\item[p. 23] (Jean-Pierre Marquis). SM--2 should read, ``If $m$,
$n\in S$, then $mn\in S$''.
\item[p. 31] (Jean-Pierre Marquis). S--1 should say
$\Dsc_0\inc\Csc_0$ and $\Dsc_1\inc\Csc_1$.
\item[p. 34] (Nils Andersen). l. 16 ``$f\neq f'$ or $g\neq g'$ should
be ``$f\neq g$ or $f'\neq g'$
\item[p. 34] (Nils Andersen). Third line above 2.6.10:
``a {\bf indexed}'' should be ``an {\bf indexed}''.
\item[p. 43] (Nils Andersen). Lines 3 through 5 are nonsense.
Replace them by the statement: ``The relation $\sim$ is
symmetric by definition.''
\item[p. 47] (Nils Andersen). l. -5 ``The left inverse'' should
be ``This arrow $f$''.
\item[p. 52] (Nils Andersen). Line 3 of Example 3.1.2: ``object
to $M$'' should read ``object
of $M$''.
\item[p. 54] (Andrew Malton). Line 8: read ``$g \o h = f$'' for ``$h \o
g = f$''
\item[p. 56] (Han Yan). Line 7: $g:C\to C$ should be $g:B\to C$.
\item[p. 57] (Han Yan). Line 1: $f:A\to A$ should be $f:C\to A$.
\item[p. 57] (Han Yan). Line 2: $g:B\to C$ should be $g:B\to D$.
\item[p. 63] (Jean-Pierre Marquis). Last line: $TF(S)$ should
be $FT(S)$.
\item[p. 64] (Jean-Pierre Marquis). Definition 3.3.2, line 4:
$G(f)$ should be $F(g)$.
\item[p. 66] (Jean-Pierre Marquis). Section 3.3.10, line 2: ``is
to said'' should be ``is said''.
\item[p. 73] (Jean-Pierre Marquis). The reference to Wells [1989]
should be deleted.
\item[p. 74] (Jean-Pierre Marquis). The reference to Wells [1989]
should be to Wells [1990] (see updated reference
in Section~\ref{refs} of this document).
\item[p. 83] (Andrew Malton). Line --7: change ``of shape $U$'' to ``of
shape ${\cal U}$''.
\item[p. 79] (Al Vilcius). Line 7: replace ``$\id_i$'' by $\id_{D_i}$.
\item[p. 79] Line 3: ``diagram'' should be capitalized.
\item[p. 87] (Al Vilcius). In Theorem 4.2.20, line 2 replace ``$\Csc$''
by ``$\Gsc$'. In the last line replace ``$\Mod(\Gsc,\Csc)$'' by
``$\Mod(\Gsc,\Dsc)$''.
\item[p. 90] (Andrew Malton). Line 5: change ``$f: {\cal E}\to V{\cal
G}_1$'' to ``$f: {\cal E} \to {\cal G}_1$''
\item[p. 92] In Proposition 4.3.12 and its proof, the letter $C$ (not
the script $\Csc$) is
used with two different meanings. This can be corrected by changing $C$
to $S$ in the first line of the proposition, third line (first occurrence
only), fourth line (last occurrence only) and in the first line of the
proof (second occurrence only).
\item[p. 96] The reference to Seely should be [1987] (the entry in the
list of references, p. 425, was incomplete and is updated in the
list of references below.)
\item[p. 101] (Jean-Pierre Marquis, Han Yan).
In the figure, $\Hom(f,C)$ should be
$\Hom(C,f)$.
\item[p. 102] ``The'' not ``the'' in line 7.
\item[p. 103] (Al Vilcius). Change ``set'' to ``collection'' in the
second line of 4.6.2 and the sixth line of 4.6.3. [We are using
``collection'' as an informal synonym for ``class'', without getting
into set theory.]
\item[p. 103] Between the fourth and fifth lines of 4.6.3, add the following:
``We write $M:\Ssc\to\Csc$ for such a model. This use of the same
symbol to denote both the sketch homomoprhism and the graph homomorphism
is a bit of notational overloading that in practice is always
disambiguated by context.''
\item[p. 104] (Nils Andersen). The second sentence of Example
4.6.6 should be deleted.
\item[p. 105] (Nils Andersen). l. 4, ``with an arrow
$s:N\to A$'' should be ``with arrows
$s:N\to A$ and $\id_N:N\to N$''
\item[p. 105] (Nils Andersen). The first sentence of the second
paragraph should read:
``The surprise is that a homomorphism $\alpha:M\to M'$ of models of
this sketch must take the particular loop $M(s)(n)$ to $M'(s)(\alpha
N(n))$.''
\item[p. 105] The sentence before 4.6.9 has a misplaced parenthesis. It
should read
"If you want a sketch for graphs which have a loop on every node, but not
a distinguished loop (so that a homomorphism takes the loop on $n$ to
some loop on $\alpha N(n)$, but it does not matter which one), you will
have to wait until we can study regular sketches in 9.4.5."
\item[p. 105] (Jean-Pierre Marquis). LT--1, second line: $a$
should be $f$.
\item[p. 108] (Al Vilcius). Change ``set'' to ``collection'' in line 3
of 4.7.2.
\item[p. 108] (Nils Andersen). In the second line of Definition
4.7.3, ``$\Csc$'' should be ``${\rm\bf Set}$''.
\item[p. 109] (Nils Andersen). The heading for 4.7.6 should be
``Term models''.
\item[p. 131] (Nils Andersen). In line 8 of 5.3.12,
``the property that $P.A\o$'' should read
``the property that $P.A\o=f$ and
$P.B\o=g$''.
\item[p. 137] (Jean-Pierre Marquis). Line 3 of proof of Theorem
5.5.5: $u_i\o s$ should be $s\o u_i$.
\item[p. 165] (Nils Andersen). In Diagram (a), the left arrow from
$1$ to $n$ should go from $n$ to $1$.
\item[p. 166] (Nils Andersen). In Diagram (f), $\id\x\succ$
should be $\id_n\x\succ$.
\item[p. 173] (Jean-Pierre Marquis). The second line of N--5
should be
$$f_1\x f_2\x\cdots\x f_n:a_1\x a_2\x\dots\x a_n\to
b_1\x b_2\x\cdots\x b_n$$
(no angle brackets around the arrow).
\item[p. 184] (Jean-Pierre Marquis). In the next to last line of
Example 7.7.3, ``sort $\tau$'' should be ``sort $\sigma$''.
\item[p. 186] (Jean-Pierre Marquis). Line 4 of Example 7.7.7:
``Let $u$ be the term $x$ of arity $\sigma$ and sort
`$\sigma$' '' should
be changed to
``Let $u$ be the term $x$ of arity `$\sigma$' and sort
$\sigma$''.
\item[p. 186] (Jean-Pierre Marquis). In line 8 of Example 7.7.7,
the path of $u$ is $\id:\sigma\to\sigma$.
\item[p. 190] (Nico Verwer).There is a series of errors in FE--5 to
FE--8. The correct versions are as follows:
\blist{FE--}\setcounter{lister}{4}
\item$ + \o < {\id} , 0 \o <> > =
+ \o < 0 \o <> , {\id} > =
\id : f \to f$
\item
$ * \o < j , {j} \o 1 \o <> > =
* \o < {j} \o 1 \o <> , j > =
j : u \to f$
\item
$ + \o {< \id , - >} =
+ \o {< - , \id >} =
0 \o <> : f \to f$
\item
$ * \o (j \times j) \o {< \id , ()^{-1} >} =
* \o (j \times j) \o {< ()^{-1} , \id >} =
1 \o <> : u \to u$
\elist
\item[p. 201] (Nils Andersen). Line 3 of Definition 8.1.2.
In addition to the property mentioned here, an
equalizer $j:A\to A$ of $f,g:A\to B$ must also have the property that
$j$ equalizes $f$ and $g$. This will follow from the rest of
the definition if there is {\it some\/} arrow that equalizes $f$
and $g$, but there needn't be such a thing.
\item[p. 205] (Nils Andersen). The fourth sentence of 8.2.6
should read:
``An object of this category is a commutative cone $\{p_i:C\to Di\}$ and
an arrow to $\{p'_i:C'\to Di\}$ is an arrow $f:C\to C'$ such that
$p'_i\o f=p_i$ for all $i$.''
The sixth sentence should read:
``A terminal object in ${\rm cone}(D)$, if one exists, is a commutative
cone over $D$ to which every other commutative cone over $D$ has a
unique arrow.''
\item[p. 208] (Al Vilcius). Top diagram should have a $B$, not $C$ in
the SE corner. The fourth line should say that $p_2$, not $p_1$ is the
pullback of $f$ along $g$.
\item[p. 208] (Nils Andersen). Fourth line under top diagram:
``that $p_1$ is'' should be ``that $p_2$ is''.
\item[p. 211] (Nils Andersen). l. -6: $p_1$ should be $p_2$.
\item[p. 227] (Jean-Pierre Marquis). Line 2 of Exercise 2 should
have $B_i$ for $B$ and $C_i$ for $C$.
\item[p. 228] (Al Vilcius). Last line: Word ``be'' is missing.
\item[p. 229] (Nils Andersen). In the diagram in N-8, $p$
should be $a\x_c b$.
\item[p. 232] (Jean-Pierre Marquis). The first line of the second
paragraph of section 9.1.5 has a font error (it is not
mathematically wrong): the second parenthesized expression
should read $(D,\mult_D,{\rm unit}_D)$
\item[p. 235] (Nils Andersen). In the first figure, $d$ should
be $n$.
\item[p. 235] (Nils Andersen). The left diagram near the bottom
of the page, the one containing the arrow labeled ``false'', is
redundant and should be omitted. The phrase ``be diagrams''
directly underneath that diagram should become ``be a diagram''.
\item[p. 244] (Nils Andersen). In line 6 of 10.2.3, the
sentence
``We use nodes $t^+,\ t$ and $d$'' should read
``We use nodes $1, t^+,\ t$ and $d$''.
\item[p. 244] (Nils Andersen). In the diagram at the bottom of
the page, {\bf Stack} should be {\bf BinTree} and $G$ should be
$H$.
\item[p. 249] (Nils Andersen). l. 7 should read
``For any sketch $\Ssc$, let ${\rm\bf Mod}_{\Csc}(\Ssc)$ be
the category of models of $\Ssc$ in $\Csc$ (we called this
${\rm\bf Mod}(\Ssc,\Csc)$ in Section 9.1).''
\item[p. 255] (Al Vilcius). Line --5: Replace ``cleavage'' by
``opcleavage''.
\item[p. 256] (Al Vilcius). Line --8: the expression has misplaced
brackets. Should be $$Fg[Ff(u)] \o\kappa(g,Ff(X))\o\kappa(f,X)$$
\item[p. 256] (Al Vilcius) Line --2 should be ``functors $\Csc\op\to\Cat$.''
\item[p. 258] (Al Vilcius). Definition 11.2.3: GS--1 should be ``object
of $G_0(\Csc,F)$''.
\item[p. 259] (Al Vilcius). Line 8 should read ``$x'=Ff(x)$''.
In paragraph starting line 11, orientation of $G_0(\Csc,F)$ requires the
functor $G_0(F)$ to be the projection on the second coordinate, not
first.
\item[p. 261] (Al Vilcius). In Theorem 11.2.9, first projection should
be second as above.
\item[p. 263] (Jean-Pierre Marquis and Han Yan).
Line 15: Change ``then $F(C)$ and
$G(C)$'' to ``then $F(C)$ and $F(D)$''.
\item[p. 264] (Al Vilcius). In Definition 11.3.4, FI--1, replace
``$P:\Esc\to\Cat$'' by ``$P:\Esc\to\Csc$''.
\item[p. 271] (Nils Andersen). l. -3 ``monoid to be'' should be
``monoid $M$ to be''.
\item[p. 272] (Jean-Pierre Marquis). Line --4: The reference to
12.1.2 should be to 12.1.1.
\item[p. 279] (Nils Andersen). In the diagram, the diagonal
arrow should be labeled $$.
\item[p. 281] (Jean-Pierre Marquis). In Exercise 1,
$f(S_0)\inc T_0$ should be $f_{*}(S_0)\inc T_0$.
\item[p. 287] (Jean-Pierre Marquis). The second line should read
$$\Hom_{\Csc/A}(u\x v,w) =\Hom_{\Csc/A}(\Sigma_u(u^*(v)),w)$$
\item[p. 302] Line --4ff should say, `` In particular, ${\rm\bf Cat}$
is enriched over ${\rm\bf Cat}$ itself, since its hom sets are
themselves categories (with the arrows as objects and the natural
transformations as arrows) and the hom functors preserve the extra
structure.''
\item[p. 303] (Jean-Pierre Marquis). In the second line of SP--4,
the $E$ should be $A$.
\item[p. 307] (Jean-Pierre Marquis). In line 5 of the second
paragraph, $(a_0, a_1, a_2, a_4\ldots)$ should be
$(a_0, a_1, a_2, a_3\ldots)$.
\item[p. 310] (Nils Andersen). In the first diagram,
$\Sub(k'\o k)$ should be
$\Sub(k\o k')$.
\item[p. 311] (Nils Andersen). In Example 14.1.3, $\chi$ should
be defined by
$$\chi(x)=\left\{
\begin{array}{ll}
{\rm true}&\hbox{\rm if $x\in S_0$}\\
{\rm false}&\hbox{\rm if $x\notin S_0$}
\end{array}
\right.$$
\item[p. 319] (Jean-Pierre Marquis). $G_0$ and $G$ in the diagram
should be $\Gsc_0$ and $\Gsc$.
\item[p. 331] (Jean-Pierre Marquis). Line 2: ``That of (C)''
should be ``That of (c)''.
\item[p. 333] (Jean-Pierre Marquis). In line 4 of the paragraph
after REAL--2, $\[fa_1=fa_2\]$ should be $\[\phi a_1=\phi
a_2\]$.
\item[p. 334] (Nils Andersen). l. 11 $Q(A)$ should be $Q(a)$.
\item[p. 335] In the fourth paragraph of the discussion of the
internal category of modest sets, the sentence, ``We want to describe
this subset as consisting of those relations that are symmetric and
transitive'', should have the following phrase added:
``and double negation closed''.
\item[p. 345] Line 2 of the answer to exercise 12.a: the last letter
should be ``B'', not ``b''.
\item[p. 357] (Jean-Pierre Marquis) In the top diagram, one of
the arrows from BOOLEAN to BOOLEAN should be reversed.
\item[p. 358] (Jean-Pierre Marquis) In the answer to Exercise 5,
delete the phrase ``$\beta$ satisfies''.
\item[p. 365] In the answer to problem 8, $\beta C:\Hom(C,C)\to F(C)$.
\item[p. 368] (Jean-Pierre Marquis) In the second line of the
answer to Exercise 3, the $B$'s should be $C$'s.
\item[p. 370] (Jean-Pierre Marquis) Line --2: Both occurrences
of $f$ should be $F$.
\item[p. 372] (Jean-Pierre Marquis) In the answer to Exercise 1,
the arguments to $f$ are reversed. The end of the sentence
should read:
``$\ldots$by letting $f(b,0)=f_0(b)$ and having
defined $f(b,i)$ for $i\le n$, define $f(b,n+1)=t(f(b,n))$''.
\item[p. 373] (Jean-Pierre Marquis) In the answer to Exercise 1
of Section 6.1, every occurrence of $(\lambda\o\eval)$ should be
$\lambda(\eval)$.
\item[p. 380] (Jean-Pierre Marquis) In the diagram in the answer
to Exercise 2, the upper right arrow (labeled $<\id,e\o<>>$)
should go in the opposite direction.
\item[p. 381] (Jean-Pierre Marquis) The answer to number 3 is
confused. Here is the entire answer rewritten:
We give the answer for the case of real vector spaces; the other is
similar. We assume the real number field $\R$ as a given structure. We
suppose, for each $r\in R$, a unary operation we will denote $r^*:s\to
s$. We require a unit element $z:1\to s$ for the operation $c$
and a diagram similar to the previous exercise to say that $z$ is the
unit element. The following diagram says that $c$ is
commutative:
$$
\Atriangle[s\x s`s\x s`s;<\proj_2,\proj_1>`c`c]
$$
We have to add a unary negation operator $n:s\to s$ together with a
diagram to say it is the negation operator:
$$\bfig
\setsqparms[0`1`1`1;1500`500]
\putsquare(0,0)[s`s\x s`1`s;`<>`c`z]
\putmorphism(0,500)(1,0)[\phantom{s}`s\x s`<\id,\id>]{750}1a
\putmorphism(750,500)(1,0)[\phantom{s\x s}`\phantom{s\x s}`\id\x
n]{750}1a
\efig$$
In addition, we need diagrams that express the following identities:
\begin{eqnarray*}
0^*(x)&=&z\\
r^*(c(x,y))&=&c(r^*(x),r^*(y))\\
(r+s)^*(x)&=&c(r^*(x),s^*(x))\\
1^*(x)&=&x\\
r^*(s^*(x))&=&(rs)^*(x)
\end{eqnarray*}
We give, for example,
the diagram required to express the third of the equations above:
$$
\settriparms[1`1`1;600]
\qtriangle[s`s\x s`s;`(r+s)^*`c]
$$
\item[p. 386] (Jean-Pierre Marquis) Line 4 of answer to 3b:
$D_m$ should be $Dm$.
\item[p. 388] (Nils Andersen). After the change is made on p.208,
the answer to number 6 should read:
``In ${\rm\bf Set}$, the pullback is
$$P=\{(a,b)\mid f(a)=g(b)\}$$
Since $f$ is surjective, for any $b\in B$, there is a $a\in A$
such that $f(a)=g(b)$. Then $p_2(a,b)=b$. Thus $p_2$ is
surjective.''
\item[p. 402] (Jean-Pierre Marquis). The answer to Exercise 6 of
12.2 (page 281) uses Theorem 12.3.6, which comes in a later
section. Here is an answer using only the definition of
adjoint: If the functor defined in 12.2.4 has a left adjoint
$F$, then by definition of left adjoint there is for any set $X$
an arrow $\eta X:X\to FX\x A$ with the property that for any
function $f:X\to Y\x A$ there is a unique function $g:FX\to Y$
for which $(g\x A)\o \eta X=f$. Now take $Y=1$, the terminal
object (any one element set). There is only one function
$g:FX\to 1$, so there can be only one function $f:X\to 1\x A\iso
A$. If $A$ has more than one element, this is a contradiction.
\item[p. 431] The word ``relation'' should also be indexed on p. 21.
\end{description}
\section{Additional text}\label{newtext}
\begin{description}
\item[p. xiii] (First paragraph). Another book that develops
most of the topics further, except sketches, is [Freyd-Scedrov,
1990]. (Additional comment). The reader may find the following
discussions of the uses of category theory in computing science
useful: The tutorials in [Pitt, Abramsky, Poign\'e and
Rydeheard, 1986], and [Goguen, 1991].
\item[p. xiii] (Second paragraph).Another collection of papers is
[Pitt, Rydeheard, Dybjer, Pitts and Poign\'e, 1989].
\item[p. 17] [Additional example of category.]
Let $\alpha$ be a relation from a set $A$ to a set $B$
and $\beta$ a relation\index{relation}
from $B$ to $C$ (see 1.3.4). The {\bf
composite} $\beta\o\alpha$ is the relation from $A$ to $C$ defined
as follows: If $x\in A$ and $z\in C$, $(x,z)\in\beta\o\alpha$ if and
only if there is an element $y\in B$ for which $(x,y)\in\alpha$ and
$(y,z)\in\beta$. With this definition of composition, the {\bf
category of sets and relations} has sets as objects and relations
as arrows.
\item[p. 53] Add to third paragraph of 3.1.7: Freyd-Scedrov
[1990], pages 9 and 19, give a formal definition of forgetful functor.
\item[p. 71] [New exercise] Show that the category of sets and relations
is equivalent, in fact isomorphic, to its own dual (see 2.6.7).
Answer: Let $\Rel$ denote the category of sets and relations.
For a relation $\alpha$ from $A$ to $B$, that is, a subset of
$A\x B$, let $\alpha\op$ denote the subset $\{(b,a)\mid (a,b)\in A\x B\}$
of $B\x A$.
Let $F:\Rel\to\Rel\op$ be the identity on objects and
for a relation $\alpha:A\to B$,
let $F(\alpha)=\alpha\op$. $F(\alpha)$ is a relation from $B$ to
$A$ in $\Rel$, hence a relation from $F(A)=A$ to $F(B)=B$ in $\Rel\op$.
It is easy to check that if $\beta:B\to C$, then $F(\beta\o\alpha)=
\alpha\op\o\beta\op$ in $\Rel$, so $(\beta\o\alpha)\op=\beta\op\o\alpha\op$
in $\Rel\op$. This says $F(\beta\o\alpha)=F(\beta)\o F(\alpha)$, so
$F$ preserves composition. The identity relation on $A$ is $\Delta_A=
\{(a,a)\mid a\in A\}$, so $\Delta=\Delta\op$ and $F$ preserves
identities. Since for any relation $\alpha$, $(\alpha\op)\op=\alpha$,
we have $F\o F$ is the identity functor on $\Rel$, so is its own inverse.
Hence $F$ is an isomorphism. By Exercise 1, it is therefore an
equivalence of categories.
\item[p. 96]
The applications of 2-categories have mushroomed and include
[Ji-Feng and Hoare, 1990], [Moggi, 1989] and [Power, 1989] in
addition to the papers already listed.
\item[p. 97] Second paragraph of Section 4.5: In addition to generalizing
the Cayley Theorem, the Yoneda Lemma also has as a special case the
embedding of a poset into its down-closed subsets.
Also: set-valued functors are studied further in Sections 11.2 and 14.4.
\item[p. 158] The assumption that every object in a cartesian
closed category has fixed points is inconsistent with other
desirable assumptions on the category. See [Huwig-Poign\'e,
1990].
\item[p. 213] Freyd-Scedrov [1990] have a different but closely
related definition of ``regular''. If a category is regular in
our sense it is regular in theirs, and if it is regular in their
sense and has coequalizers, then it is regular in our sense.
\item[p. 257] Besides [Coquand, 1988], Moggi [1989] also uses
the Grothendieck construction in modeling polymorphism.
\item[p. 283] Another reference for the Adjoint Functor Theorem
(with a different point of view) is [Freyd-Scedrov, 1990], pages
144-146.
\item[p. 287] Just before the exercise: See also [Ehrhard, 1989].
\item[p. 301] Some applications of triples (monads) in computing
science are in [Moggi, 1991], [Power, 1990]
\item[p. 318] Add comment: We considered presheaves as actions in Section
3.2. They occur in other guises in the categorical and computer science
literature, too. For example,
a functor $F:A\to\Set$, where $A$ is a set treated as a
discrete category, is
a ``bag'' of elements of $A$. If $a\in A$, the set $F(a)$ denotes the
multiplicity to which $a$ occurs in $A$. See [Taylor, 1989] for
an application in computing science.
\item[p. 325] Goguen [1990] has developed a sheaf semantics for object
oriented programs.
\end{description}
\section{Additional references}\label{refs}
\fontdimen2\twlrm=4.3pt% space instead of 3.91663
\fontdimen3\twlrm=4.2pt%stretch instead of 1.95831
\fontdimen4\twlrm=1.7pt%shrink instead of 1.30554
\begin{list}{}{\leftmargin 8mm \itemindent -8mm
\parsep 0pt \itemsep 0pt plus 1pt}
\def\itm{\item[]}
\itm \mbox{T. Ehrhard}, {\it Dictoses}. In {\bf Category theory and
computer science}, D. H. Pitt, D. E. Rydeheard, P. Dybjer, A. M. Pitts
and A. Poign\'e, editors. \lncs{389}, \springer, 1989.
\itm \mbox{P. Freyd and A. Scedrov}, {\bf Categories,
Allegories}. North-Holland Mathematical Library {\bf39},
North-Holland, 1990.
\itm \mbox{J.\ Goguen}, {\it Semantics of concurrent interacting
objects}. Preprint, Programming Research Group, Computing Laboratory,
Oxford University, Oxford OX1 3QD, England.
\itm \mbox{J. Goguen}, {\it A categorical manifesto}.
Mathematical Structures in Computer Science {\bf 1}, 1991,
49--68.
\itm \mbox{C.\ A.\ R.\ Hoare}, He Jifeng and C. Martin, {\it
Pre-adjunctions in order-enriched categories}. Preprint, Programming
Research Group, Computing Laboratory, Oxford University, Oxford OX1 3QD,
England.
\itm \mbox{He Ji-Feng and C. A. R. Hoare},
{\it Categorical semantics for programming languages}.
In M.\ Main {\it et al.}, eds., {\bf Mathematical
Foundations of Programming Semantics}. \lncs{442},
\springer, 1990, 402--417.
\itm\mbox{H. Huwig} and A. Poign\'e, {\it A note on
inconsistencies caused by fixpoints in a cartesian closed
category}. Theoretical Computer Science {\bf73}, 1990,
101--112.
\itm \mbox{E. Moggi}, {\it A category-theoretic account of program
modules}.
Mathematical Structures in Computer Science {\bf 1}, 1991,
103--139.
% In {\bf Category theory and computer science}, D. H. Pitt, D.
% E. Rydeheard, P. Dybjer, A. M. Pitts and A. Poign\'e, editors.
% \lncs{389}, \springer, 1989.
\itm \mbox{D.\ Pitt}, D. Rydeheard, P. Dybjer, A. Pitts and A. Poign\'e,
eds. {\bf Category theory and computer science}. \lncs{389},
\springer, 1989.
\itm \mbox{A.\ J.\ Power}, {\it An abstract formulation for rewrite
systems}. In {\bf Category theory and computer science}, D. H. Pitt, D.
E. Rydeheard, P. Dybjer, A. M. Pitts and A. Poign\'e, editors.
\lncs{389}, \springer, 1989.
\itm \mbox{A. J. Power},
{\it An algebraic formulation for data refinement}.
In M.\ Main {\it et al.}, eds., {\bf Mathematical
Foundations of Programming Semantics}. \lncs{442},
\springer, 1990, 390--401.
\itm \mbox{R.\ Seely}, {\it Modelling computations: a $2$-categorical
framework.} In {\bf Proceedings of the Conference on Logic in Computer
Science}, IEEE, 1987. [Corrected reference].
\itm \mbox{P.\ Taylor}, {\it Quantitative domains, groupoids and linear
logic}. In {\bf Category theory and computer science}, D. H. Pitt, D.
E. Rydeheard, P. Dybjer, A. M. Pitts and A. Poign\'e, editors.
\lncs{389}, \springer, 1989.
\item \mbox{C.\ Wells}, {\it A generalization of the concept of
sketch}. Theoretical Computer Science {\bf 70} (1990), 159-178.
[Updated reference].
\pagebreak[3]
\end{list}
\end{document}
=====================================================================
Subj: Regular epis, revisited
Date: Tue, 10 Mar 92 10:01:14 EST
From: barr@triples.Math.McGill.CA (Michael Barr)
I thought some of the people on the net might be interested in the
outcome of the correspondence I've been having with Paul Taylor on
regepis. Basically, he wanted the definition extended further so that
if there were a multi-coequalizer, then every candidate should also be
considered a regepi. It seems that that all works too. One thing was
that I also wanted to be able to define stable in the absence of
pullbacks and show that the composite of regepis is regepi if they are
stable.
A couple of loose ends. Does anyone know of a natural example of a
category with multicoequalizers that does have pullbacks (or at least
kernel pairs) and a candidate for a multicoequalizer that is not itself
the coequalizer of its kernel pair?
I could have sworn that Joyal once claimed to have shown that if you
have an E/M factorization system and if E is stable under pullbacks,
then E = regepis (and M = monos). Maybe it was assumed that E incin
epis and M incin monos. Why isn't posets with E = surjective on objects
and M = full inclusions a counter-example? In fact, why isn't Cat, with
the same two classes, a counter-example?
Follows, with minor changes, is the letter I wrote to PT:
Paul:
With help from Dusko Pavlovic at a crucial point, here is the proof that
if regular epis in my sense are stable, in my sense, then they are also
closed under composition. Dusko also claims that this can even be made
to work for candidates in the way you want it to work. I haven't
checked, but I guess if he says it works I believe him.
First the simple case. For an arrow q: A --> Q, let Kerp(q) (in
contrast with kerp(q), the usual kernel pair) denote the class of all
pairs of arrows such that f.x0=f.x1. (Here and later, I will
let the domain/codomain requirements be inferred from the composites and
equations written down, so that from the above, x0 and x1 have to be
parallel and their codomain has to be the domain of q.) Then my defn of
regular epi is that q is regular epi iff Kerp(q) incin Kerp(f)
==> E! g such that g.q = f. I will say that regular epis are stable
iff given a regepi q and a map f: Q' --> Q, there is a commutative
square f.q' = q.g and q' is a regepi.
Prop. If regepis are stable, they are closed under composition.
Proof. Suppose q: A --> Q and p: Q --> P are regepi. Suppose Kerp(p.q)
incin Kerp(f). Then Kerp(q) incin Kerp(p.q) incin Kerp(f) so E! g such
that f = g.q. Now suppose that in Kerp(p). Begin by choosing
squares
q'0 q'1
A'0 -------> Q' A'1 -------> Q'
| | | |
| | | |
u'0| |u0 u'1| |u1
| | | |
| | | |
v q v v q v
A --------> Q A --------> Q
with q'0 and q'1 regepic. Then find a square
t0
A' --------> A'0
| |
| |
t1| |q'0
| |
| |
v q'1 v
A'1 ---------> Q'
with t0, and therefore q' = q'0.t0 = q'1.t1 epic. Then we have q.u'0.t0
= u0.q'0.t0 = u0.q and similarly q.u'1.t1 = u1.q. From p.u0 = p.u1, we
conclude that p.q.u'0.t0 = p.u0.q = p.u1.q = p.q.u'1.t1 and thus g.u0.q' =
g.q.u'0.t0 = f.u'0.t0 = f.u'1.t1 = g.q.u'1.t1 = g.u1.q'. But q' is epi
and so g.u0 = g.u1 and so E! h such that h.p = g.
Now for the multi-coequalizer case, Dusko suggest the following. Let
Coeq(Kerp(q)) be the set of candidates for thhe multicoequalizer,
assuming it exists. Define a predicate Z(q;f,g) that is true whenever
Kerp(q) incin Kerp(f) & Kerp(g) and f and g are in the same component
of the cocone of all arrows with that property. Then by sprinkling Zs
at appropriate places in the above, he says that it all works. I
haven't tried it, but I see no reason it wouldn't work.
Michael
=====================================================================
Subj: corrections to corrections
Date: Wed, 11 Mar 92 15:03:49 EST
From: barr@triples.Math.McGill.CA (Michael Barr)
corrections to corrections
There is an omission in the corrections to ctcs. The definition
\mathrm{Sub} has to be added. A couple of people have written me that
it wouldn't tex with their version of the diagram macros. I can suppose
only that they have old or small versions of tex. However, it has far fewer
macros than the book itself and we did that with a 1989 or so version that
was considerably smaller than the one I have today. There may also be
a problem with the new font selection scheme that I have not yet adopted.
I will see that the latest version of the diagram macros are in the
ftp/pub/texmacros directory.
Michael
=====================================================================
Subj: regepis, stablefunctors...
Date: Thu, 12 Mar 92 10:41:13 EST
From: Michel Hebert
Ref.: The last message of M. Barr on regepis, etc..., and the one of P. Taylor
The claim of Joyal is probably the one mentioned on p.292 of [Cassidy-Hebert-
Kelly; J.Austr. Mat.Soc.38 (1985)], where it is assumed that (E,M) = (Strong
Epis, Monos) (it is Kelly who reported that). Certainly it is not true for all
E: to be more precise, Th. 3.3 and 4.7 of the paper imply that factorization
systems (E,M) with E stable under pullbacks (in a finitely complete and well-
powered category A) are exactly those couples (E,E*) with
E = { f ; r(f) iso }for some left-exact reflection functor r from A and
E* obtained by the diagonalproperty (Hence in particular all localisation
morphisms a-->r(a) are in such an E, and classical cases give counterexamples).
About a previous message about slices, it seems to me that the existence of a
multi-initial object (in the sense of Diers) does not imply the existence of an
initial object in each slice, unless you assume the existence of equalizers (A
counterexample being the algebraically closed fields).(Am I using a different
definition of multi-initial object?).In fact, at least for axiomatic categories
of finitary models, the existence and preservation of equalizers by the
forgetful functor is precisely what makes the difference between multi-
adjointness and "local adjointness" (in the sense of [Kaput] and [Adamek-
Volger] mentioned by Tholen).
About preservation of pullbacks only, note that in axiomatic categories of
finitary models, the existence and preservation by the forg.funct. of
pullbacks imply the one of wide pullbacks (and filtered colimits)
(This follows from results of [Pare, Can. J. Math 42 (1990), 731-746]
and Volger: see [Volger, Initial and quasi-initial models of theories,
manuscript, 1991]). Doesn't this permit to simplify the definition of a
locally-finitely poly-presentable category (as an accessible category
with pullbacks)?
=====================================================================
Subj: Re: regepis, stablefunctors...
Date: Thu, 12 Mar 92 14:46:05 EST
From: barr@triples.Math.McGill.CA (Michael Barr)
Diers' notion of multi-adjoint includes a uniqueness so that algebraically
closed fields^op is not an example. Essentially, it is that there is an
initial object in each component, so it follows by definition.
You are probably right about Joyal's claim, but it is even easier to see
that if regepis are closed under composition (implied by pullback
stability), then every strong epi is regular. Oh well, I guess my
memory was faulty.
What are wide pullbacks? How can pullback preservation imply anything
about filtered colimits? In any case, it is easy to find limit preserving
underlying functors that don't preserve filtered colimits.
Michael
=====================================================================
Subj: Hopf algebras
Date: Thu, 12 Mar 92 17:27:21 -0500
From: James Stasheff
Bill Schmitt asks:
From SCHMITTW@hermes.msci.memst.edu Thu Mar 12 16:58:24 1992
Message-Id:
To: jds@charlie.math.unc.edu
From: SCHMITTW@hermes.msci.memst.edu
Date: 8 Mar 92 15:59:24 CDT
Subject: question
X-Mailer: Pegasus Mail v2.1c R5.
Status: R
Dear Jim,
Do you know to whom the following theorem should be attributed?
If H is a cocommutative, connected (i.e., pointed and irreducible)
Hopf algebra over a field K of char. 0, then H is isom. to the
universal enveloping algebra of the Lie algebra of primitives P(H).
Milnor and Moore prove this for H graded, is this more general result
due to Kostant? Or is Kostant's theorem the statement that a general
cocommutative H is a product of a univ. env. algebra and a group
algebra?
Milnor and Moore also extend this to the case when char K=p. Do you
know of any extension for K a general commutative ring with unit?
I think the theorem holds for K a comm. ring exactly as stated above
except with the following added condition on H:
Let I be the identity map and 1 be the convolution identity in the
convolution algebra of all linear maps Hom(H,H). Then for all
n>0, and all x in H, (I-1)^{n}(x) is divisible by n in H.
I've proved this for H also commutative, but would like to know if
it would be an interesting extension of the above result (or if it's
already been done) before trying to prove it in general.
I greatly appreciate any help you can give.
Yours,
Bill
=====================================================================
Subj: commutative Ext
Date: Thu, 12 Mar 92 17:28:43 -0500
From: James Stasheff
If A is Hopf, then Ext_A(k,k) is graded commutative
what is the earliest or best PUBLISHED proof?
=====================================================================
Subj: Congratulations
Date: Fri, 13 Mar 92 11:38+0000
From: mxh@dcs.edinburgh.ac.UK
...to Gordon Plotkin, on becoming a Fellow of the Royal Society.
=====================================================================
Subj: multi, poly, stable, etc.
From: Paul Taylor
Date: Fri, 13 Mar 92 17:34:06 GMT
In reply to Michel Hebert:
> ...it seems to me that the existence of a multi-initial object (in the sense
> of Diers) does not imply the existence of an initial object in each slice,
> unless you assume the existence of equalizers.
No, the other way round. The category of algebraically closed fields does have
an initial object in each slice, alias initial candidates, alias a polyinitial
family. The "poly" initial (etc) family is "multi" iff the relevant functor
preserves equalisers.
As I have said, all of these things become much simpler if you consider
slices instead of these confusing collections (multiple-valued adjoints).
> Doesn't this permit to simplify the definition of a locally-finitely
> poly-presentable category (as an accessible category with pullbacks)?
Indeed it does. I'm afraid my own work on this never got beyond the "notes"
stage, but those notes are available by anonymous ftp
from theory.doc.ic.ac.uk as /theory/papers/Taylor/LFPP.dvi
Probably Pierre Ageron or Francois Lamarche has an account of the same thing.
I don't like the term "locally finitely presentable", but given that after
twenty years there's no changing it, "locally finitely multi- or poly-
presentable" describes the corresponding categories with multi- or poly-
(finite) colimits. There is a characterisation of the connections between
how "poly" the colimits are in terms of finite limits in the same notes.
Paul
=====================================================================
Subj: stable, multi, poly and slice things
From: Paul Taylor
Date: Wed, 11 Mar 92 18:02:54 GMT
Perhaps I should make more effort to share with the community what I know
about stable functors. I am grateful to Walter Tholen for pointing out some
old work of his about which I knew nothing.
I started writing a much longer survey to send to "categories" but decided
it was getting too technical, so I shall just point out one thing.
Diers had quite a lot of results about adjoining formal products or coproducts,
to get a multiple-valued adjoint. Mike Barr seems to have those results in
mind. In my view they make matters far more complicated than they really are.
The point in quite simply this:
(1) A functor is stable (in my sense) iff it has a left adjoint on each slice.
(2) The candidates are the universal maps in the slices.
There may be many of them, but they're all as good as each other at being
universal maps, coequalisers or whatever.
(3) Each object (slice, cocone) only gets to see one candidate.
As far as that slice is concerned, that candidate is the real thing.
If you can draw a diagram entirely within one slice (for example if it
is the square expressing the orthogonality property of a factorisation
system) then a coequaliser (or whatever) candidate behaves in exactly
the same way as a universal coequaliser would.
(4) So long as whatever structure you're interested in (colimits, say) is
preserved by pullbacks (as colimits are in a locally cartesian closed
category) then yes, the slices are guaranteed to fit together nicely.
Hence my word "laminated". I could use "locally", and I'd like a
"cartesian" category to be one with pullbacks, but these words are too
sullied with overuse.
(5) The interesting cases arise when the categories do not have terminal
objects. If Max Kelly had dropped this assumption when he investigated
"shape transformations" he would have discovered a lot of beautiful
results.
What's the difference between Diers' "multi" and Lamarche's "poly"?
Answer: "poly" is what's true in each slice; this becomes "multi" if the
functor preserves equalisers (and hence all connected limits) instead of
just wide pullbacks. Of course this is automatic in preorders.
Why don't I know of any examples of genuinely multi or poly coequalisers?
Because most (all?) of Diers' examples from generalised algebraic theories
are full subcategories of the monomorphisms in an equational underlying
theory.
The inclusion of the formal monos in any factorisation system is a stable
functor, whose candidates are the formal epis. If you want to find an example
with nontrivial behaviour vis-a-vis coequalisers, you'll have to start with
a factorisation system which is completely different from epi-mono.
I suggest the final/discrete-fibration factorisation.
Alternatively, you can paste slices together.
A discussion of multi/poly adjoints, stable functors and candidates will be
found in my unpublished paper
"The trace factorisation of stable functors".
in theory.doc.ic.ac.uk /theory/papers/Taylor/trace.dvi
The third section (of three) of this paper discusses adjunctions in the
2-category of stable functors and cartesian transformations. Amongst other
things it shows that all such adjunctions are comonadic, and that an ordinary
left adjoint belongs to such an adjunction iff it is a discrete fibration.
The paper didn't get published because the referee considered this
irrelevant technicality, even though it also served as the proof of something
the alleged absence of the proof of which he described as "scandalous".
It will will never now be published because, as is the nature of research,
I can now prove many of the results more easily.
Paul Taylor
PS I have reverted to magnified computer modern fonts as the default for our
latex, even though design size fonts look better.
=====================================================================
Subj: Pfn
Date: Thu, 26 Mar 92 10:57:52 +0100
From: Lars Birkedal
Does there exist a comprehensive treatment of the category Pfn, objects are
sets and morphisms are partial functions - specifically I`m interested to know
if someone has proven the existence of colimits and other such concepts in Pfn.
Thanks,
Lars Birkedal (birkedal@diku.dk)
=====================================================================
Subj: Re: Pfn (times 2)
Date: Fri, 27 Mar 1992 09:51 ADT
From: RDAWSON@HUSKY1.STMARYS.CA
Maybe I'm being naive here, but isn't Pfn isomorphic in a rather
natural way to Set*, the category of pointed sets? Everything that doesn't
get mapped anywhere by a partial function P:X-->Y gets mapped to *(Y) by
the corresponding function P*: X* --> Y*: so * acts as a sort of 'wastebasket'.
So it would seem that coproducts, etc., would follow from that.
-Robert Dawson
++++++++++++++++++++++
Date: Fri, 27 Mar 92 09:35:12 EST
From: barr@triples.Math.McGill.CA (Michael Barr)
The category of sets and partial functions is equivalent to that of
pointed sets and base point preserving morphisms, the algebras for the
triple X |---> 1 + X with obvious structural maps, and, as such, is as
complete and cocomplete as one could wish.
Michael Barr
=====================================================================
Subj: Omega completeness of retraction categories.
Date: 30 Mar 92 11:48:05 EST
From:
-------------
Asperti and Longo say it is an open question whether there are
non-trivial cartesian closed categories with omega complete retraction
categories. (Their book, p.249.) Here I show that any category _C_
with binary coproducts has omega complete retraction category iff
_C_ is a preorder. The theorem does not even use all binary coproducts.
It is constructive so it applies to categories over any topos.
To define the terms: a "chain" in _C_ is an infinite sequence
of objects, with an initial member, each with a map to the next.
A category is "omega complete" if every chain in it has a colimit.
Given any category _C_ the "retraction category" is called _C_^Ret
and has the same objects as _C_. An arrow in _C_^Ret from A to A'
is a retraction pair making A a retract of A'.
If _C_ is a preorder then _C_^Ret is a groupoid and trivially
omega complete. To connect this with the converse notice that _C_ is
a preorder iff every object of _C_ is subinitial (i.e. it has at most
one map to any object).
Theorem: Suppose a category _C_ has an object A which is not subinitial
but which does have a coproduct with every object of _C_. Then _C_^Ret
is not omega complete.
Proof: Define a sequence of objects An this way: A0=A and for every
n we let A(n+1) be the coproduct (An)+A. "The map of A onto the last
summand of An" means the coproduct injection of A into A(n-1)+A if n
is not 0, and the identity if n=0. Each An is a retract of A(n+1) in
a canonical way where the monic is the coproduct injection and the
splitting epic from An+A to A acts as the identity on An and maps A onto
the last summand of An. These retractions give a chain in _C_^Ret.
Suppose the chain has a colimit B. Then there is a map from A to B so
B is a retract of B+A. Define a cone over the chain this way: The vertex
is B+A. For each An in the chain the monic to B+A is the colimit monic to
B followed by the inclusion into B+A. The splitting epic from B+A to An
acts as the colimit epic on B and maps A to the last summand in An.
But since A is not subinitial the map of A onto the last summand in
A(n+1) does not factor through the inclusion of An. Thus no splitting epic
from B+A to B to commutes with the cone projections, and so B is NOT a
colimit. Our chain has no colimit.
Colin McLarty
=====================================================================
Subj: Re: Pfn (times 2)
From: Paul Taylor
Date: Mon, 30 Mar 92 11:51:40 BST
Robert Dawson says "am I being naive?". Well, Robert, you asked for it, but
yes you are, because you're assuming excluded middle.
Pfn is the Kleisli category (of *free* algebras) for the partial element
(lift) monad. Classically, every (Eilenberg-Moore) algebra is free,
and so what Robert & Mike say is true.
Intuitionistically, lift(1) is the object of truth values. Every algebra
carries a partial order, which, for free algebras, is a powerset in each slice.
In general it need not be distributive, because the category of algebras
is closed under retracts (splitting idempotents).
Indeed any algebra for a monad is a coequaliser of a pair of maps between
free algebras, so colimits naturally take you outside the Kleisli category.
The diagram may nevertheless still have a (different) colimit inside.
This makes the question of colimits a little more complicated than Mike
suggests, but then he's probably still the best person to say exactly how
complete and cocomplete the category is.
Here is an example of computer science interest, and a counterexample to what
I claimed (privately) at the recent Manchester PSSL.
David Rydeheard's book discusses unification (as used in logic and functional
programming) as a coequaliser in the Kleisli category for the monad for an
algebraic theory with no equations.
A very simple example shows that this is *not* the coequaliser in the
category of algebras.
Take one unary operation f and two variables x,y. Then as a unification
problem the equation f(x)=f(y) implies x=y, but the coequaliser as an algebra
is essentially "N with two zeroes".
Paul Taylor