Latest ctcs corrections

10 Mar 1992

      \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<f,g>$'' should read
``the property that $P.A\o<f,g>=f$ and
$P.B\o<f,g>=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 $<q_1,q_2>$.

\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^*>`(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}
=====================================================================

Latest ctcs corrections

barr＠triples.Math.McGill.CA