August 1992 - Categories - categories.org.au

4 colours
by pavlovic＠triples.Math.McGill.CA 09 Sep '92

09 Sep '92

A note describing A CATEGORICAL SETTING FOR THE 4-COLOUR THEOREM by Dusko Pavlovic is available by anonymous ftp. Abstract: It is well known that the 4-colouring of maps is equivalent to the 3-colouring of the edges of some graphs. We show that every slice of the category of 3-coloured graphs is a topos. The forgetful functor to the category of graphs is cotripleable; every loop-free graph is covered by a 3-coloured one in a universal way. In this context, the 4-Color Theorem becomes a statement about the existence of coalgebra structure on graphs. The "projective" approach to graphs, described here, is, in a sense, dual to the usual combinatorial treatment, based on induction. I shall try to relate the two approaches in another paper. How to get a copy: >ftp triples.math.mcgill.ca >login: anonymous >password:[your e-mail address] >cd pub/pavlovic >bin >get 4color-US.ps.Z %if your printer has American standards %or >get 4color-A4.ps.Z %otherwise >bye >uncompress 4color-++.ps.Z If you have any problems printing out this PS-file, please let me know. (I am not distributing the DVI or LaTeX versions of the paper because it contains several PS-diagrams.) Regards, Dusko ==============================================================================

2 2

Online LICS bibliography
by dmjones＠theory.lcs.mit.edu 01 Sep '92

01 Sep '92

The online bibliography for the Annual IEEE Symposium on Logic in Computer Science has now been updated to include all of the papers published in the proceedings of the Seventh meeting, which took place in June 1992. The bibliography contains abstracts for all of the papers from the 1992 meeting. The bibliography, which is in BibTeX format, is available via anonymous ftp and mail server from theory.lcs.mit.edu [18.52.0.92] in the file pub/meyer/lics.bib. To retrieve the file via ftp, connect to theory using "anonymous" as the login name and "guest" as the password. To retrieve the file via mail server, send a message to the address archive-server(a)theory.lcs.mit.edu with the following line in the body: send meyer lics.bib An index of other available files can be retrieved with the command send meyer Index More information on the archive-server can be obtained by sending a message with only the word "help" in the body. David M. Jones MIT Lab for Computer Science Administrator, {types,logic,concurrency}(a)theory.lcs.mit.edu

1 0

Yoneda and square brackets
by es＠math.mcgill.ca 01 Sep '92

01 Sep '92

To the best of my knowledge, the observation that every presheaf is a canonical limit of representables first appeared in ``Completions of categories'', Springer LNM 24 (1966). The double square brackets are usually associated with Dana Scott, Jim Lambek ==============================================================================

1 0

Yoneda
by cxm7＠pop.cwru.edu 01 Sep '92

01 Sep '92

------------- While we are asking terminological questions prompted by Mac Lane and Moerdijk, I'd like to know exactly what people mean by the Yoneda lemma. Does Yoneda include the fact that every presheaf is a canonical limit of representables? Does it include (as Johnstone has it, on _Topos Theory_ p.51) the claim that the Yoneda embedding to a presheaf category is left adjoint to the forgetful functor (i.e. the functor that forgets the action of arrows and only remembers the family of sets indexed over the objects of the domain category)? Colin McLarty ==============================================================================

3 2

None
by dbenson＠yoda.eecs.wsu.edu 01 Sep '92

01 Sep '92

The first place I encountered this notation is Joseph E. Stoy Denotational Semanatics: The Scott-Strachey Approach to Programming Langauge theory The MIT Press, 1977 I quote from page 29: The brackets [[ ]], used round an argument of a semantic function, always enclose expressions in the object langauge, possibly including metalanguage variables. There appears to be no discussion of the history, other than Stoy perfers this to Quine's quasi-quotes (Quine's corners) Unfortunately, this book is, I believe, out-of-print. Regards to all, David ==============================================================================

1 0

None
by barr＠triples.Math.McGill.CA 01 Sep '92

01 Sep '92

As far as I am concerned the Yoneda is either the statement that NT(Hom(A,-),F) iso FA (naturally in A and F) of else the special case when F is also representable. The latter is probably the way Yoneda stated it. The rest is the Grothendieck construction or something. Michael ==============================================================================

1 0

None
by pavlovic＠triples.Math.McGill.CA 01 Sep '92

01 Sep '92

Some people call the double square brackets SCOTT BRACKETS. Could it be that Dana Scott first used them in 1967, in his notes on Boolean-valued models of set theory? Dusko Pavlovic +++++++++++++++++++++++++++++++++++++++++++++++++++++

1 0

None
by F.J.de.Vries＠cwi.nl 31 Aug '92

31 Aug '92

At least in 1975 Scott, Strachey and Stoy used such [[..]] notation, but it should be possible to go beyond that, as you do yourself perhaps with the reference to Knuth and APL. The question intrigued me because my reflex was to believe that the notiation should come from good old model theory. But that seems not be the case. Fer-Jan de Vries, CWI, Amsterdam. ++++++++++++++++++++++++++++++++++++++++++++++++++++

1 0

None
by Robert Tennent 31 Aug '92

31 Aug '92

My guess is that logicians used it long before any of these did, and that the origin is that it evolved from parenthesized Quine corners: _ _ (| syntax |) Bob Tennent +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

1 0

Re: square brackets
by Mike Fourman 31 Aug '92

31 Aug '92

> From: Charles Wells <cfw2(a)po.cwru.edu> > Topos theorists and people in denotational semantics use the > notation [[t]] to denote a mathematical object that is the > meaning of t in some semantics. In particular, in the case of a > formula f, [[f]] is the truth value. APL and Donald Knuth use [f] > for the truth value of a formula (or so I have been told). Does > anyone know who used the double square bracket notation first > (topos theorists, denotational semantics people, or whoever), > and whether it was suggested by the APL usage? The first occurrence I know of is in the Scott-Solovay treatment of Boolean-Valued models. I've always called them "Scott-open and Scott-close". Mike Prof. Michael P. Fourman email mikef(a)dcs.ed.ac.uk Dept. of Computer Science 'PHONE (+44) (0)31-650 5198 (sec) JCMB, King's Buildings, Mayfield Road, (+44) (0)31-650 5197 Edinburgh EH9 3JZ, Scotland, UK FAX (+44) (0)31 667 7209 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

1 0