July 2000 - Categories - categories.org.au

Reality check
by Peter Freyd 01 Aug '00

01 Aug '00

In an earlier posting I showed how to define co-inductively the closed interval, in particular I showed that its elements are named by sequences of 0s and 1s with the usual binary-expansion equivalence relation. There is a well-known computational problem with this approach, already in the definition of the midpoint operation: at what point can you determine the first digit of the midpoint of .0000... and .1111...? At the Como meeting I learned from Andrej Bauer about a better approach. Take the elements of [-1,1] to be named by infinite sequences of _signed_ binary digits, that is -1, 0, +1. [Just to confuse matters, Scedrov and I once used signed _ternary_ digits (n Cats and Allegators for the "Freyd curve"). The signed binary expansions .+1 -1 and .0 +1 describe the same number, to wit, 1/4.] Using signed binary expansions one can compute midpoints with a little 3-state machine that takes as input the sequence of pairs of signed binary digits of the given numbers x and y, and produces as output a sequence of signed binary digits for the midpoint x|y. (There may, indeed, be momentary delays in the output, but there will not be an indefinite delay -- indeed, the number of output digits will never be more than one less than the number of pairs of input digits). The challenge is to revise the co-induction so that it is this better version that emerges. In the previous version I worked in the category of posets with _distinct_ top and bottom, that is, those posets for which not[(B = x) and (x = T)]. In the revised version I'll strengthen the condition by working in the category of posets with _separated_ top and bottom: [(B < x) or (x < T)]. (The conditions are equivalent in the presence of De Morgan's law. In a topos the top and bottom of omega are always distinct but they are separated only when De Morgan's law is satisfied throughout.) In the previous setting I defined what I'll now call the _thin_ version of the ordered-wedge of X and Y, to wit, the set of pairs, <x,y> satisfying the condition: (x = T) or (B = y). The _thick_ version is the set of pairs, <x,y> satisfying the two weaker conditions: (x < T) => (B = y) (B < y) => (x = T) (each of which is classically equivalent to the single condition used in the thin version). Easy exercise: if top and bottom are separated in X and Y, then they are separated in the thick version of the ordered-wedge XvY. (Indeed, it's enough for top and bottom to be separated in just one of X and Y . No, it is not enough to assume just that they are distinct in each.) A map X -> XvX is thus given by a pair d,u: X -> X such that for all x: (dx < T) => (B = ux) (B < ux) => (dx = T) The final coalgebra for XvX is still the closed interval, but now in the better computational sense. Let me explain. Given an arbitrary coalgebra d,u : X -> X, I need to describe a coalgebra homomorphism f: X -> I. where I is the set of equivalence types of infinite sequences of signed binary digits. The first step is to work not with elements of X but elements of XvX. Consider a machine that given <x,y>:XvX asks in parallel the questions: "B < y?" "B < ux and dy < T?" "x < T?" Exercise: If the top and bottom of X are separated and d,u describe a map to the thick ordered-wedge XvX, then at least one of these questions has a positive answer. Given z:X obtain a sequence of signed binary digits by starting with the pair <x,y> = <dz,uz> and iterating the non-deterministic procedure: If B < y then emit +1 as output and replace <x,y> with <dy,uy>; If B < ux and dy < T then emit 0 as output and replace <x,y> with <ux,dy>; If x with <dx,ux>. Not-so-easy exercises: regardless of the non-determinism, the element fz:[-1,+1] named by the resulting sequence is determined. Moreover, f(uz) = u(fz) and f(dz) = df(z). PS. There is some geometry behind this stuff. Let me here mention just this: given a pair <x,y> in XvX map it into the four-fold ordered-wedge XvXvXvX. Think of each of the four copies of X as one "quarter" of the whole. If B < y then the point lies inside the "top half" (the 3rd and 4th quarters). If B < ux and dy < T then the point lies inside the "middle half" (the 2nd and 3rd quarters). If x < B then the point lies inside the bottom half" (the 1st and 2nd quarters). Clearly any point is inside at least one of these three halves. The output-digit registers which of the three halves is moved to and the corresponding pair-replacement effects that move. PPS. On 22 Dec I gave a Dedekind-cut proof that the interval [0,1] constructed in the standard fashion from (unsigned) binary sequences is the final coalgebra for the functor that sends X (with distinct top and bottom) to the thin version of XvX. That proof should be replaced. First note that the midpoint-algebra homomorphism from [0,1] to [-1,1] can be effected simply by replacing each 0 with -1 and keeping each 1 as +1. Given d,u:X -> X such that for all x it is the case that either dx = T or ux = B , consider a machine that upon given x:X asks in parallel the questions "dx = T?" and "ux = B?". If dx = T then emit +1 as output and replace x with ux, If ux = B then emit -1 as output and replace x with dx. Given x:X one may iterate this (non-deterministic) procedure to obtain a sequence of +1s and -1s. Pretty-easy exercises: regardless of the non-determinism, the element fx:[-1,+1] named by the resulting sequence is determined; f(ux) = u(fx); f(dx) = df(x).

2 1

Como Meeting
by F W Lawvere 31 Jul '00

31 Jul '00

Last week's CT 2000 meeting in Como, Italy had two quite notable features, which augur well for the future of category theory: - the significant number of young people who are actively learning and developing category theory and who presented their new results; - the unusual number of senior researchers in other fields whose essential use of category theory was demonstrated in their interesting lectures. Congratulations to the organizers, as well as to the scientific committee, and thanks for their hard work which successfully brought us all together. ***************************************************************** F. William Lawvere Mathematics Dept. SUNY Buffalo, Buffalo, NY 14214, USA 716-829-2144 ext. 117 HOMEPAGE: http://www.acsu.buffalo.edu/~wlawvere *****************************************************************

1 0

query: presheaf construction
by Todd H. Trimble 29 Jul '00

29 Jul '00

At the Como meeting last week, I asked various people a question which I view as having foundational significance: is there a setting in which one can iterate the presheaf construction (as free cocompletion) without ever having to use the word "small" or worry about size? Here is a more precise formulation of what I am after. I want an example of a compact closed bicategory B [think: bicategory of profunctors] with the following very strong property: the inclusion i: Ladj(B) --> B, of the bicategory of left adjoints in B, has a right biadjoint p such that, calling y: 1 --> pi the unit and e: ip -|-> 1 the counit, the isomorphisms which fill in the triangles iy yp i --> ipi p --> pip \ | \ | \ | ei \ | pe \| \| i p furnish the unit and counit, respectively, of adjunctions iy --| ei in B and pe --| yp in Ladj(B). (These structures should also be compatible with the symmetric monoidal bicategory structures on B and Ladj(B).) By exploiting compact closure, it's easy to see that p(b) is equivalent to an exponential (p1)^(b^op) in Ladj(B), where b^op denotes the dual of b in the sense of compact closure. So the unit y: 1 --> pi takes the yoneda-like form b --> v^(b^op); the axioms imply it is the fully faithful unit of a KZ-monad. The reactions I got were varied and interesting. As filtered through me, here are some (abbreviated) responses: (1) "No, I don't think there are any examples except the obvious locally posetal ones." (2) "The notion looks essentially algebraic, so I see no obstacle in principle to producing examples; it should even be easy for the right (2-categorically minded) people." (3) [From experts in domain theory] "Good question! Hmmmmmmmm....." (4) "It seems to me there is no reason in the world why examples should not exist, but the techniques developed for dealing with things like modest sets are probably not sufficient for dealing with your question, and may be misleading here." The various responses suggest *to me* that the question may be quite interesting and quite hard. My own sense, based on playing around with the axioms on a purely formal level, is that there is probably no inconsistency in the sense that any two 2-cells with common source and target are provably equal. My only vague idea on producing an example would be to proceed as Church and Rosser did in the old days: work purely syntactically, and consider the possibility of strong normalization for terms. Perhaps one could then show that the term model is not locally posetal. Todd

2 2

blackboards at Como
by Peter Freyd 28 Jul '00

28 Jul '00

[NOTE FROM MODERATOR: This message should be the last of the discussion on this issue, regards to all, Bob Rosebrugh] The posts from Mike and Colin prompt me to go on record. In my talk at Como I did not use projectors. I used the two blackboards that were provided by the organizers.

1 0

AMS SS J1 (Applied Categorical Structures) in Toronto
by Walter Tholen 28 Jul '00

28 Jul '00

Below you will find the final schedule for the Special Session on "Applied Categorical Structures" at the up-coming AMS Meeting in Toronto, Sept. 23&24. There will be a Welcome Party on Friday evening (Sept. 22) - details to be communicated in early September. Note specifically that the program on Sunday afternoon continues until 5 pm rather than until 4pm as previously announced. For comprehensive and continually updated meeting and program information, including accommodation in Toronto, see http://www.ams.org/meetings/ Hotel accomodation in Toronto during the month of September can be very tight. In fact, the deadlines for making bookings in the two AMS-recommended hotels in Toronto are approaching rapidly. These are: "Courtyard by Marriott", 475 Yonge St., (416) 924-0611, $182 (Can.) for single or double by August 1; "Days Inn", 30 Carlton St., (416) 977-6655 or (800) 325-2525, $139 (Can.) for single or double by August 23. As an alternative to the Days Inn (same price or lower, 15 min walk to conference site) you may want to try the following smaller downtown hotel, which we have used for vistors in the past: Howard Johnson Inn, 89 Avenue Road, (416) 964-1220 or (800) 446 4656. We look forward to seeing you in Toronto. Joan Wick Pelletier Walter Tholen Saturday, Sept. 23: 9:00 Andre Joyal 3:00 Stephen Awodey 9:30 Myles Tierney 3:30 Lars Birkedal 10:00 Jack Duskin 4:00 David Benson 10:30 Marco Grandis 4:30 John MacDonald 11:00 Enrico Vitale 5:00 Richard Wood Sunday, Sept. 24: 9:00 Marta Bunge 2:00 Joachim Lambek 9:30 Michael Makkai 2:30 James Madden 10:00 Robin Cockett 3:00 Gloria Tashjian 10:30 M. M. Mawanda 3:30 Robert Pare 11:00 F. William Lawvere 4:00 Jiri Rosicky 4:30 F. J. O. Souza All talks are 25 minutes long. The titles follow. The full abstracts may be seen at the web site cited above. Abstract # Title Authors Date Received 957-18-265 On the pivotal, symmetric case of involutory Hopf 13-jul-2000 objects. Fernando J. O. Souza*, fernando(a)math.uic.edu 957-18-235 Higher category theory. 12-jul-2000 Andre Joyal*, joyal(a)math.uqam.ca 957-06-218 Injective hulls of partially ordered monoids. 12-jul-2000 J. Lambek* 957-18-214 Modelling a sketch in an object in a 2-category. 11-jul-2000 Michael Johnson, mike(a)ics.mq.edu.au Robert Rosebrugh, rrosebru(a)mta.ca R. J. Wood*, rjwood(a)mathstat.dal.ca 957-18-204 Open problems on finiteness and their counting 11-jul-2000 measures. Mbila-Mambu Mawanda*, mm.mawanda(a)nul.ls 957-18-199 Monoreflections in categories of ordered rings. 10-jul-2000 James J Madden*, madden(a)math.lsu.edu 957-18-198 Nerves of Bicategories: Morphisms and Simplicial 10-jul-2000 Maps. John W Duskin*, duskin(a)math.buffalo.edu 957-18-157 A summary report on the state of our knowledge of 05-jul-2000 weak higher dimensional categories. Michael Makkai*, makkai(a)math.mcgill.ca 957-18-140 Dominances and Spread Completions. 04-jul-2000 Marta C Bunge*, bunge(a)math.mcgill.ca 957-18-132 Finitely productive classes of uniform spaces 03-jul-2000 which generate cartesian-closed categories. Gloria Tashjian* 957-68-123 Certain spans of sketches model problems of 29-jun-2000 complexity NP. David B Benson*, dbenson(a)eecs.wsu.edu 957-18-107 Flat covers and factorizations. 27-jun-2000 Jiri Rosicky*, rosicky(a)math.muni.cz 957-18-90 Free Double Categories and the Word Problem for 25-jun-2000 Groups. Robert Par\'e*, pare(a)mscs.dal.ca Robert MacG. Dawson, rdawson(a)husky1.stmarys.ca 957-18-77 A higher dimensional homotopy sequence. 22-jun-2000 Marco Grandis, grandis(a)dima.unige.it Enrico Vitale*, vitale(a)agel.ucl.ac.be 957-18-76 Some absolute pullbacks and pushouts in 22-jun-2000 $\boldsymbol{\Delta}$. Myles Tierney*, tierney(a)math.rutgers.edu 957-18-61 Monads and Structure. 16-jun-2000 John L. MacDonald*, johnm(a)math.ubc.ca 957-18-59 Relating realizability using sheaves. 16-jun-2000 Steve Awodey*, awodey(a)cmu.edu Andrej Bauer Dana S Scott 957-03-51 Relative and Modified Relative Realizability. 13-jun-2000 Lars Birkedal*, birkedal(a)itu.dk Jaap van Oosten, jvoosten(a)math.uu.nl 957-18-39 Higher fundamental functors in some categories of 07-jun-2000 presheaves. Marco Grandis*, grandis(a)dima.unige.it 957-18-30 Game theory revisited: categorical proof theories 31-may-2000 for games. J. Robin B. Cockett*, robin(a)cpsc.ucalgary.ca 957-18-19 Toposes and Continuum Microphysics. 22-may-2000 F. William Lawvere*, wlawvere(a)acsu.buffalo.

1 0

"free" poset question
by Bill Halchin 27 Jul '00

27 Jul '00

Hello Category Community, N (P, <=) ---------------------> (P/E, <=) \ | \ | \ | \ | \ | \ | g \ | f \ | \ | \ | \ | \ | \ | \ v (Q, <=) - This is a problem from Arbib's book on category theory - P is a pre-order - (P/E) and Q are posets - N and f are order-preserving functions from a pre-order to a poset. - g is a order-preserving function between posets P/E and G, i.e. a poset homomorphism, that is UNIQUE. - Question 1: we are building category where the objects are the collection of order-preserving functions from P to posets and morphisms are order-preserving functions between posets that make a diagram like the following commute, i.e. h.g = f Is the above statement true? h (P, <=) ---------------------> (R, <=) \ | \ | \ | \ | \ | \ | g \ | f \ | \ | \ | \ | \ | \ | \ v (Q, <=) - Question 2: if indeed this forms a category, then (P/E, N) is an initial object in this category. True?? - Question 3: the whole notion introduced by this Arbib problem is that of "free" poset, i.e. something very akin to a free algebra, free group, etc. I.e. the same kind of categoric construct. Yes???? Thank you, Bill Halchin ________________________________________________________________________ Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com

1 0

Re: Presentation Facilities at Conferences
by Colin McLarty 27 Jul '00

27 Jul '00

I agree with Mike Barr. I think there is a specific reason for using blackboards in math talks: Where most disciplines use graphics and texts to present data and conclusions, mathematicians often write to convey a line of reasoning as it develops. When I talk about math I often put formulas or diagrams on the board, and change them as I go. Slides and powerpoint can handle those changes in various ways, but none are as flexible or as graceful as writing on a board. Colin At 02:02 PM 7/26/00 -0400, Micheal Barr wrote: >I think we should continue to protest the lack of >blackboards. I have used transparencies and I have even used tex to >prepare them. But I don't like it and I don't think it makes good talks >and I don't see why we should acquiesce. > >Michael

1 0

Presentation Facilities at Conferences
by Ronnie Brown 27 Jul '00

27 Jul '00

The following is suggested by Max Kelly's comments and some discussions at Como. We have to be prepared for the worst scenario, that blackboard facilities will get worse, and it may even get to a stage where conference administrators wonder why mathematicians are not using powerpoint and computer presentations like everyone else! People should be aware that Latex facilities for slides are good: just use \documentclass{slides} \begin{document} \raggedright \begin{slide} ......\end{slide} etc. A colleague here also got splendid results using the colour package (I need to investigate this!). I also like to use in the preamble \parindent=0pt \parskip=1ex and to use almost pidgin English, so that the impact is visual, with as few words as possible. What is not so clear is how to use say animated gif files in such a presentation. For this I have used a browser presentation using html files, and converting tex into html using tth http://hutchinson.belmont.ma.us/tth/ I hope this helps people. We could then ask conference centres to provide projection facilities, if these are a requirement of users. Ronnie Brown -- Prof R. Brown, School of Informatics, Mathematics Division, University of Wales, Bangor Dean St., Bangor, Gwynedd LL57 1UT, United Kingdom Tel. direct:+44 1248 382474|office: 382475 fax: +44 1248 361429 World Wide Web: home page: http://www.bangor.ac.uk/~mas010/ (Links to survey articles: Higher dimensional group theory Groupoids and crossed objects in algebraic topology) Symbolic Sculpture and Mathematics: http://www.bangor.ac.uk/SculMath/ Centre for the Popularisation of Mathematics http://www.bangor.ac.uk/cpm/

2 1

Osher Doctorow
by Peter Freyd 26 Jul '00

26 Jul '00

Bob: I've added a description of his dissertation, so use this if you haven't already sent the other out. I thought it might be interesting to find out about Osher Doctorow. Something called "Nupedia" lists him as one of its "very distinguished and active scholars, and all-around interesting people" to be found among its Editors and Peer Reviewers. Nupedia tells us: Osher Doctorow (PR) -- Ph.D. (1982 UCLA). Consultant in mathematics and physics mostly since 1973, Doctorow Consultants, Culver City, California. M.A. Mathematics (USC 1969), M.A. Anthropology (University of London 1961). Over 150 papers presented and publications, about 40 of which abstracted at Instititute for Logic at University of Vienna on the internet, plus (in addition to the 150 or so above) about 40 book reviews on math and physics mostly, at Amazon.com. Taught university mathematics five years; Staff Research Assistant (statistics) UCLA six years; Mathematician U.S. Defense Department 2-1/4 years in artificial satellites (Sustained Superior Performance Award in Mathematics 1984); Statistician at private research institute one year; High School/Middle school mathematics teacher two years. Member Armed Forces Communications and Electronics Association (AFCEA), UCLA Alumni Association (lifetime). Married 30+ years to Dr. Marleen Josie Doctorow (psychologist), one son, Eric. PsycINFO tells us: Author Doctorow, Osher. Institution U California, Los Angeles. Title Modeling cognitive growth by the linear system of linked differential equations (LSDE). Source Dissertation Abstracts International. Vol 43(10-A), Apr 1983, 3267. Key Phrase Identifiers linear system of differential equations, model of cognitive growth in reading & mathematics & language arts, 3rd graders, 4-5 yr longitudinal study Following the Nupedia lead we find that the "Abstract Service for Mathematical Logic" of the Institute for Logic at the University of Vienna lists abstracts for 45 journal publications for Doctorow, Osher. The journals in question turn out to be: 20 Doctorow Consultants Technical Report 5 Philosophy of Education Proceedings 3 HOPOS-L(a)LISTSERV.ND.EDU (History of Philosophy of Science) 3 Humanist Discussion Group, Center for Computing Group in Humanities, 3 Submitted for publication 2 MCRIT-L (Intl. Society on Multiple Criteria Decision Making) 2 Sociology and Social Research Vol. 48 Number 2 pp. 233-234 1 American Anthropologist, April 1963 1 Operations Research Society of America (ORSA) Newsletter 1 Orbis Scientiae Global Foundation Quanum Gravity Conference 17.12.1999 1 Policy Sciences 14 (1981), 31-47 1 Semigroups Archives 1 Socioeconomic Planning Sicences, 15(3), 1981 1 TCC 2000 Teaching in the Community Colleges Online Conference -- 45 Read the abstracts at www.logic.univie.ac.at/cgi-bin/abstract (where you can also find 13 abstracts by Cyrus F. Nourani).

1 0

Preprint: Technical Report by Cattani, Leifer, and Milner
by James Leifer 26 Jul '00

26 Jul '00

The following paper: TITLE: Contexts and Embeddings for a Class of Action Graphs AUTHORS: Gian Luca Cattani, James J. Leifer, and Robin Milner is available as Technical Report 496, University of Cambridge Computer Laboratory. Copies may be obtained by sending email to: tech-reports(a)cl.cam.ac.uk or by downloading directly from these web addresses: http://www.cl.cam.ac.uk/users/glc25 http://www.cl.cam.ac.uk/users/jjl21 An abstract is attached below. -- G.L. Cattani, J.J. Leifer, and R. Milner. ABSTRACT: Action calculi, which have a graphical presentation, were introduced to develop a theory shared among different calculi for interactive systems. The pi-calculus, the lambda-calculus, Petri nets, the Ambient calculus and others may all be represented as action calculi. This paper develops a part of the shared theory. A recent paper by two of the authors was concerned with the notion of reactive system, essentially a category of process contexts whose behaviour is presented as a reduction relation. It was shown that one can, for any reactive system, uniformly derive a labelled transition system whose associated behavioural equivalence relations (e.g., trace equivalence or bisimilarity) will be congruential, under the condition that certain relative pushouts exist in the reactive system. In the present paper we treat closed, shallow action calculi (those with no free names and no nested actions) as a generic application of these results. We define a category of action graphs and embeddings, closely linked to a category of contexts which forms a reactive system. This connection is of independent interest; it also serves our present purpose, as it enables us to demonstrate that appropriate relative pushouts exist. Complemented by work to be reported elsewhere, this demonstration yields labelled transition systems with behavioural congruences for a substantial class of action calculi. We regard this work as a step towards comparable results for the full class.

1 0