victor@vivaldi.itg.ti.com (Brian Victor) (08/16/90)
[Sorry if this was recently asked!] I have been starting to get into Category Theory, but find some of the books rather dense. Are there any good intro books out there? My backround is CS with some moderate mathematics (more enthusiasm than ability, I fear!). It doesn't matter to me whether the texts are oriented towards math or CS. Thanks! - Brian victor@itg.ti.com
baxter@zola.ICS.UCI.EDU (Ira Baxter) (08/17/90)
In comp.theory you write: >I have been starting to get into Category Theory, but find some of the books >rather dense. Are there any good intro books out there? My backround is CS >with some moderate mathematics (more enthusiasm than ability, I fear!). It >doesn't matter to me whether the texts are oriented towards math or CS. I recently went through this myself, with only moderate success. I feel like I know have "survival category theory" understanding. Call me "the reluctant mathematician". Here are some references and my remarks on them: @book(Arbib75a, author = "Michael A. Arbib and Ernest G. Manes", title = "{Arrows, Structures, and Functors: The Categorical Imperative}", publisher = "Academic Press", address = "New York", year = 1975, note = "", annotation = {An attempt to simplify the presentation of category theory to make it more widely accessible. Unfortunately, the authors do not succeed, as they fail to make it clear to the poor reader when the discussion is about specific instances of categories, and when the discussion is about categories in general, and the switching back and forth is very rapid. Such a consequence is not a surprise; it must be extremely difficult for a CT to come "down out of the clouds". One must give the authors credit for a heroic attempt at a nearly impossible task anyway. The determined reader can make some headway; this book is useful as one of several references simultaneously necessary to really learn category theory. \cite{Goldblatt84a} is much better. The book shows some application of category theory to finite state automata.} ) @book(Rydeheard:computational-category-theory, author = "D. E. Rydeheard and R. M. Burstall", title = "{Computational Category Theory}", publisher = "Prentice-Hall", address = "New York", year = 1988, note = "ISBN 0-13-162736-8", annotation = {Contains an introduction to category theory with emphasis on defining computations in categories. The language in which the computations are defined is ML, but it appears that any functional language would do (I coded some of the examples in Common Lisp). Not really valuable to learn category theory; \cite{Goldblatt84a} is better, but is a good way to solidify one's understanding of category theory by working with concrete, programmable examples. I particularly liked the computation of pushouts.} ) @techreport(Srinivas90a:category-theory-summary, author = "Yellamraju V. Srinivas", title = "Category Theory: {D}efinitions and Examples", institution= "Dept. of ICS, University of California, Irvine", number = "90-14", month = feb, year = 1990 ) @book(Goldblatt84a, author = "R. Goldblatt", title = "{Topoi: The Categorial Analysis of Logic}", publisher = "North-Holland", address = "New York", year = 1984, annotation = {This book defines Logic using Category Theory as a basis. The real value of this book is that its first 5 chapters are the most readable introduction to category theory that this reader has encountered.} ) @book(Pitt85a:category-theory-and-computer-programming-workshop, editor = "David Pitt and Samson Abramsky and Axel Poigne and David Rydeheard", title = "{Category Theory and Computer Programming}", publisher = "Springer-Verlag, New York", year = 1985, note = "Lecture Notes in Computer Science 240", annotation = {Workshop proceedings. Contains category theory tutorial focused on computer science topics so the example domains are easier for us poor computer scientists to comprehend. Also contains a number of research papers on category theory applied to semantics of programming languages, program specification, categorical logic and categorical programming.} ) Good luck. -- Ira Baxter
srinivas@madeleine.ics.uci.edu (Yellamraju Srinivas) (08/18/90)
To complement the references listed by Ira Baxter
(<9008161733.aa29977@PARIS.ICS.UCI.EDU> baxter@zola.ICS.UCI.EDU), here
are some more.
An excellent introduction to category theory for computer scientists
is the following report from CMU. Much of the material follows
Golblatt (1984). The author has done a good job of culling
definitions, concepts, and examples from several sources. In addition,
the report contains case studies of concrete applications of category
theory in computer science, such as type theory and solving recursive
domain equations.
@techreport(pierce:ct,
author = "Benjamin C. Pierce",
title = "A Taste of Category Theory for Computer Scientists",
institution= "Computer Science Dept, Carnegie Mellon University",
address = "Pittsburgh",
number = "CMU-CS-88-203",
year = 1988
)
There is also a paper by Hoare which uses an example-based approach to
introducing category theory to computer scientists. The paper contains
three sections describing sets, pre-orders, and monoids. This is a
good way to learn the abstract language of category theory. It's a
good idea to read this paper before attempting any other.
@incollection(hoare:ct,
author = "C. A. R. Hoare",
title = "Notes on an Approach to Category Theory for Computer
Scientists",
booktitle = "Constructive Methods in Computing Science",
series = "NATO ASI Series",
volume = "F55",
editor = "Manfred Broy",
publisher = sp,
address = "Berlin",
pages = "245-305",
year = 1989
)
Finally, if you are a serious student of category theory, the best
book on this subject is by Mac Lane, one of the founders of category
theory. The precision, succinctness, and clarity of exposition far
surpasses that in any other book. The author stresses the fundamental
unity of various categorical concepts such as universal arrows,
limits, adjoints, and representable functors.
However, as the title implies, this book presumes a fair amount of
mathematical background.
@book(maclane:categories,
author = "Saunders {Mac~Lane}",
title = "Categories for the Working Mathematician",
publisher = "Springer-Verlag",
address = "New York",
year = 1971
)
====
Y. V. Srinivas
Dept. of Information and Computer Science
University of California
Irvine, CA 92717
--
Y V Srinivaspierre@Autodesk.COM (Pierre Malraison) (08/18/90)
I've been out of the business ( of research category theoretician) for quite a while, but sometime in the mid to late 70's arbib and manes did some papers and a book on computer theory and catergory theory For general intro, I cut my teeth on Mitchell , but that's out of print. Saunders MacLane's book in the Springer series is probably ok -- i haven't seen it but almost anything Saunders does is good.
banerjee@ksuvax1 (Anindya Banerjee) (08/18/90)
In article <VICTOR.90Aug16142815@vivaldi.itg.ti.com> victor@vivaldi.itg.ti.com (Brian Victor) writes: >[Sorry if this was recently asked!] > >I have been starting to get into Category Theory, but find some of the books >rather dense. Are there any good intro books out there? My backround is CS >with some moderate mathematics (more enthusiasm than ability, I fear!). It >doesn't matter to me whether the texts are oriented towards math or CS. > >Thanks! > > >- Brian > victor@itg.ti.com A very recent (April-May 1990) book on Category Theory is: Abstract and Concrete Categories, by Jiri Adamek, Horst Herrlich and George Strecker. Published by John Wiley. I took a year-long course on Category Theory from George Strecker and we used drafts of the above-mentioned book. Since the class was introductory and consisted of a lot of computing scientists, George especially stressed the category of sets and the category of posets. The book is eminently readable (both for computing scientists and mathematicians), has excellent exercises and some new results. Wishing you a lot of fun, Categorically, --anindya
knighten@pinocchio (Bob Knighten) (08/18/90)
There is a quite new book by Mike Barr and Charles Wells with the title "Category Theory for Computer Scientists" and published by Prentice-Hall. I've looked at it briefly and it looks good, besides Mike Barr is a friend. Buy it.
Victoria_Beth_Berdon@cup.portal.com (08/18/90)
August 17, 1990
I, too, am starting to study category theory. But I was afraid to post
anything on the net. So you have done it for me, just as I would have
wanted. I found several good ('tho still dense, but less so) references to
recommend, as well as several articles:
Books:
*The Logical Foundations of Mathematics*, William S. Hatcher, Pergamon Press,
1982. Chapter 8:Categorical Algebra. (A good overview)
*Topoi: The Categorial Analysis of Logic* , Studies in Logic and the
Foundations of Mathematics, by R. Goldblatt, North-Holland, 1984.
Particularly the first three chapters.
*A Course in Homological Algebra*, P.J. Hilton and U. Stammbach, Springer-
Verlag, 1970. Chapter II. (This is quite dense.)
*Introduction to Higher Order Categorical Logic*, J. Lambek and P.J. Scott,
Cambridge University Press, 1986.
I've been told that F. W. Lawvere is one of the early developers, too.
Solomon Feferman is mentioned much.
Saunders MacLane (one of the founders of Cat. Theory, 1945) is
probably the best place to start. Try some articles.
Articles:
*Categorical Algebra and Set Theorectic Foundations*, Saunders MacLane.
(Sorry, I have no further reference...just an old copy)
J.L. Bell, from the London School of Economics, is writing furiously in the
topic now. See journals such as Synthese and The British Journal for the
Philosophy of Science.
*Category Theory and the Foundations of Mathematics*, J.L. Bell, Brit. J.Phil.
Sci. 32 (1981), 349-358.
*From Absolute to Local Mathematics*, J.L. Bell, Synthese 69 (1986) 409-426.
*Categories, Toposes and Sets*, J.L. Bell, Synthese 51 (1982) 293-337.
For some general flavor:
*Working Foundations*, Solomon Feferman, Synthese 62 (1985) 229-254.
For an interesting application:
*Infinitesimals*, J.L. Bell, Synthese 75 (1988) 285-315.
*Category Theory and Concrete Universals*, David P. Ellerman, Erkenntnis 28,
409-429, May 1988.
AVOID Michal Tempczyk's *Categories and Elementary Particle Physics*,
Dialectics and Humanism 9, 119-130, Winter 1982. He does not understand even
the most elementary notions, such as initial objects and terminal objects, or
morphism. Nice idea he had (to model E.P.P. with Category Theory...after all,
they have had such good results with algebra. But he hasn't managed it.)
You might try looking in the Philosopher's Index (in the reference section of
the library) for further, and more recent references of a less technical
nature than the usual math refs. That's where I got most of these article
references.
Enough.
What are you doing with Category Theory? Are you a math student? Other?
Where? I am a philosophy grad student writing a master's thesis in
foundations of, and phil. of mathematics. Category theory is all that my
advisor is interested in. Possible topics under consideration: the internal
logic of topoi (categories of sets that vary) -- it seems to be of an
intuitionistic flavor, in that the law of excluded middle fails. Perhaps a
compare and contrast of well-known math reinterpretted in category-theoretic
language? (see the Infinitesimals paper by Bell for an example)
I'm in San Francisco, and will be away 8/21-9/4, but would very much like to
correspond with someone on category theory, itself, or its implications. I
hope to hear from you! Good luck, and don't be discouraged. Two minds work
(at least) three times better!dbc@bushido.uucp (Dave Caswell) (08/20/90)
>Finally, if you are a serious student of category theory, the best >book on this subject is by Mac Lane, one of the founders of category >theory. The precision, succinctness, and clarity of exposition far >surpasses that in any other book. The author stresses the fundamental >unity of various categorical concepts such as universal arrows, >limits, adjoints, and representable functors. >However, as the title implies, this book presumes a fair amount of >mathematical background. A good book, but not particularly readable. The best simple introduction I've seen is Mathematical Physics, by Robert Gerock, it is part of the Chicago Lecture in Physics. It is math that is "good" for physics, and doesn't have much directly to do with physics. After this book I suggest Abelian Categories by Peter Freyd part of the Harper's Series in Modern Mathematics.
Victoria_Beth_Berdon@cup.portal.com (08/20/90)
August 19, 1990 Michael -- Thank you for your response, and examples of topoi. I need some definitional clarification. You said: >One kind of topos comes from a fixed set T in the following way: the topos is >the category of pairs (S,f: S --> T) of sets endowed with a structured map to >T. You could think of this as a category fibred over T. I need to understand *fibred*. In Goldblatt ("Topoi: The Categorial Analysis of Logic"), p.89-90, he develops the concept as follows: (paraphrasing) Start with a collection of pairwise disjoint sets, indexed by integers, i in I, such that the sets are A-sub-i (Sorry, no fancy character set). Let A be the union of all A-sub-i's. Then there's a map, p:A --> I. If x is in A, then there's exactly one A-sub-i s.t. x is an element of A-sub-i. Here Goldblatt says, "We put p(x)=i." (I'm not sure what he means -- we write it so?) "Thus all the members of A-sub-i get mapped to i", etc. And we can "re-capture A-sub-i as the inverse image under p of {i}. The set A-sub-i is called the stalk, or the fibre over i. The members of A-sub-i are the germs at i. ANd the whole structure is called a bundle of sets over the base space. Is this your understanding of a fibre? You asked for a definition of an elementary topos. Let me quote from a couple of sources: Goldblatt, p. 84: Definition. An elementary topos is a category E s.t. (1) E is finitely complete, (2) E is finitely co-complete, (3) E has exponentiation, (4) E has a subobject classifier. Since (1) and (3) constitute "Cartesian closed", so (1) can be replaced by (1') E has a terminal object and pull-backs, and (2) can be replaced by, (2') E has an initial object 0, and pushouts. Goldblatt says this is from the definition by Lawvere and Tierney "in terms of which they started topos theory in 1969. Hatcher (*The Logical Foundations of MAthematics*, Pergamon Press, 1982) p.279) I add: The category in question is a category of sets, CS. Let M be any model for the category of sets which is complete. "By 'complete' we mean that, in addition to satisfying the axioms of CS, M has the further property that sums and products exist in M on any indexing set..." -- I guess I think of this as closure under + and * (is this ok to do?) (I suppose initial/terminal objects, pull-back, pushout need definition. Later?) From J.L. Bell (*Category Theory and the Foundations of MAthematics*, Brit.J.Phil.Sci. 32 (1981)), p.357: "A topos is a category E which has the following features in common with the category Set of sets. (1) E has a terminal object and all finite products. (2) There is in E a "truth-value" object sigma which plays the same role in E as the truth-value set 2={0,1} plays in Set, i.e., for each object X there is a natural correspondence between subobjects of X and arrows from X to sigma ('characteristic functions' on X) (3) For each object X of E there is a 'power object' PX in E which plays the formal role of a power set of X in E. These conditions can all be formulated in the first-order language of category theory: hence the use of the term 'elementary'." (I guess this definition itself opens up a a need for a whole list of other underlying category theoretic definitions. At least for me. ) From J.L. Bell (*From Absolute to Local Mathematics*, Synthese 69 (1986)) another wording: "To arrive at the concept of a topos, we start with the familiar category S of sets whose objects are all sets (in a given model M of set theory) and whose arrows are all mappings (in M) between sets in M. ...S has the following properties. (i) There is a 'terminal object' 1 such that, for any object X, there is a unique arrow X --> 1 (for 1 we may take any one-element set, in particular {0}). (ii) Any pair of objects A,B has a Cartesian product AxB. (iii) For any pair of objects A,B one can form the 'exponential' object B^A of all mappings A --> B. (iv) There is an 'object of truth values' sigma such that for each object X there is a natural correspondence between subobjects (subsets) of X and arrows X --> sigma. (For sigma we may take the set {0,1}; arrows X --> sigma are then the characteristic functions on X, and the exponential object sigma^X corresponds to the power set of X.) All four of the above conditions can be formulated in purely category- theoretic (arrows only) language: a (small) category satisfying them is called a topos." As Bell puts it, a topos is a more general model of set theory. p.415: "A theory T may be regarded as a generalized set theory and a topos which is a model of T as a local universe of discourse within which the mathematical assertions made by T are true and the constructions sanctioned by T can be carried out." I realize that in my attempt to provide a definition, I have introduced more questions than I can handle at this time. But this is a start, no? I'm embarrassed, but I must ask, what is the reference to Avernus? (Humility seems to be the word of the day. No, make that month.) -- Victoria _ :
jack@cs.glasgow.ac.uk (Jack Campin) (08/21/90)
banerjee@ksuvax1 (Anindya Banerjee) wrote: > Abstract and Concrete Categories, by Jiri Adamek, Horst Herrlich and > George Strecker. Published by John Wiley. The Herrlich and Strecker text that used to be published by Allyn and Bacon is my favourite - lots of good examples of a much less arcane kind than in Mac Lane's book. Is this one a superset of it? Is the old one still available from anywhere? -- -- Jack Campin Computing Science Department, Glasgow University, 17 Lilybank Gardens, Glasgow G12 8QQ, Scotland 041 339 8855 x6044 work 041 556 1878 home JANET: jack@cs.glasgow.ac.uk BANG!net: via mcsun and ukc FAX: 041 330 4913 INTERNET: via nsfnet-relay.ac.uk BITNET: via UKACRL UUCP: jack@glasgow.uucp
banerjee@ksuvax1 (Anindya Banerjee) (08/22/90)
In article <6119@vanuata.cs.glasgow.ac.uk> jack@cs.glasgow.ac.uk (Jack Campin) writes: > >banerjee@ksuvax1 (Anindya Banerjee) wrote: > >> Abstract and Concrete Categories, by Jiri Adamek, Horst Herrlich and >> George Strecker. Published by John Wiley. > >The Herrlich and Strecker text that used to be published by Allyn and >Bacon is my favourite - lots of good examples of a much less arcane >kind than in Mac Lane's book. Is this one a superset of it? Is the >old one still available from anywhere? > >-- >-- Jack Campin Computing Science Department, Glasgow University, 17 Lilybank >Gardens, Glasgow G12 8QQ, Scotland 041 339 8855 x6044 work 041 556 1878 home >JANET: jack@cs.glasgow.ac.uk BANG!net: via mcsun and ukc FAX: 041 330 4913 >INTERNET: via nsfnet-relay.ac.uk BITNET: via UKACRL UUCP: jack@glasgow.uucp If you liked Herrlich and Strecker, you will like the new book much more! It is really a sort of compendium, (hence, a superset of the Herrlich and Strecker original) and the explanations are excellent. Added to that are the illustrations from the book CAT E GOR Y by Edward Gorey. You would absolutely love it! There are some interesting examples of Duality, among which the following is my favourite: Live Dual, Laud Evil. I am listing the chapters here for everybody's benefit: Introduction Categories, Functors and Natural Transformations Objects and Morphisms Sources and Sinks Factorization Structures Adjoints and Monads Topological and Algebraic Categories Cartesian Closedness and Partial Morphisms In the course that George Strecker offered the past year, we covered a substantial portion of the first six topics and a little of Cartesian Closed Categories. On a related note, does anybody know whether the book "Applied Category Theory" by Andrea Asperti and Giusseppe (sp?) Longo has been published yet? I have seen a draft of it as a technical report from Pisa, and have heard rumours that it is going to be published by MIT press. --anindya