January 2001 - Categories - categories.org.au

Why binary products are ordered
by Charles Wells 14 Feb '01

14 Feb '01

One might say that the ordering of binary products, with a first projection and a second projection, is spurious but inevitable. The two components of a binary product must be distinguished, as Colin McLarty explained, but they must be allowed to be isomorphic. The usual way we handle a situation like this in mathematics is to index them, in this case by a two-element set. One could use {red,blue}. As far as I know, in Western culture, this set has no canonical ordering, but nevertheless one knows that there is a redth component and a blueth component and they might or might not be different objects. However, in practice the index set is {0,1}, {1,2} or {x,y} (the latter in analytic geometry). All of these are canonically totally ordered in our culture, so inevitably binary products do have an order in practice. Charles Wells, 105 South Cedar St., Oberlin, Ohio 44074, USA. email: charles(a)freude.com. home phone: 440 774 1926. professional website: http://www.cwru.edu/artsci/math/wells/home.html personal website: http://www.oberlin.net/~cwells/index.html NE Ohio Sacred Harp website: http://www.oberlin.net/~cwells/sh.htm

8 11

FICS'2001 - CFP
by Anna Labella 31 Jan '01

31 Jan '01

FICS'2001 - CALL FOR PAPERS Fixed Points in Computer Science September 8, 2001, Florence, Italy http://www.dsi.uniroma1.it/~labella/FICS.html A Satellite Workshop to PLI'2001 Principles, Logics and Implementations of High-Level Programming Languages September 3-7, 2001, Florence, Italy http://music.dsi.unifi.it/pli01 Aim: Fixed points play a fundamental role in several areas of computer science and logic by justifying induction and recursive definitions. The construction and properties of fixed points have been investigated in many different frameworks. The aim of the workshop is to provide a forum for researchers to present their results to those members of the computer science and logic communities who study or apply the fixed point operation in the different fields and formalisms. Previous workshops where held in 1998 in Brno and in 2000 in Paris. Topics: Construction and reasoning about properties of fixed points, categorical, metric and ordered fixed point models, continuous algebras, relation algebras, fixed points in process algebras and process calculi, regular algebras of finitary and infinitary languages, formal power series, tree automata and tree languages, infinite trees, the mu-calculus and other programming logics, fixed points in relation to dataflow and circuits, fixed points and the lambda calculus, fixed points in logic programming and data bases. Program Committee: J. Adamek(Braunschweig) R. Backhouse (Nottingham) S. Bloom (Hoboken NJ) R. De Nicola (Florence) Z. 'Esik (Szeged) I. Guessarian (Paris) W. Kuich (Vienna) A. Labella (Rome, chair) M. Mislove (Tulane) D. Niwinski (Warsaw) Invited speakers: J. Adamek (Braunschweig) Z. 'Esik (Szeged) I. Guessarian (Paris) C. Stirling (Edinburgh) R. F. C. Walters (Sydney) Paper submission: Authors are invited to send three copies of an abstract not exceeding three pages to the PC chair. Electronic submissions in the form of uuencoded postscript file are encouraged and can be sent to labella(a)dsi.uniroma1.it. Important Dates: Submission: April 15, 2001 Notification: June 15, 2001 Proceedings: preliminary proceedings containing the abstracts of the talks will be available at the meeting. Publication of final proceedings as a special issue of Theoretical Informatics and Applications depends on the number and quality of the papers. Contact person: Anna Labella dip. Scienze dell'Informazione Universita` La Sapienza via Salaria 113 00198, Rome, Italy labella(a)dsi.uniroma1.it phone: +39 06 49918355 fax: +39 06 8541842 ============================================== Prof. Anna Labella Dipartimento di Scienze dell'Informazione Universita` di Roma "La Sapienza" Via Salaria, 113 - 00198 Roma (ITALY) tel: +39 06 49918355 fax: +39 06 8541842 email: labella(a)dsi.uniroma1.it ==============================================

1 0

Re: Michael Healy's question on math and AI
by Michael Barr 31 Jan '01

31 Jan '01

I mean the initial algebra for the theory with a nullary operation 0:1 --> N and a unary operation s:N --> N. 1 stands for the terminal object (empty product). On Sun, 28 Jan 2001, Bill Halchin wrote: > > > >For another example, consider the traditional definition of Z as the set > >{0,{0},{0,{0}},{0,{0}{0,{0}}},...} > >and contrast that to the categorical specification. > ^^^ Michael, to make things more explicit I take you > mean the category with one object N and two arrows, 0 & S, > such that > > 0:N->N and s:N->N > > Yes? > > Regards, > > Bill Halchin

4 3

Michael Healy's question on math and AI
by F. William Lawvere 27 Jan '01

27 Jan '01

Re : Michael Healy�s question on math and AI This is to answer Mike and also several other people who have contacted me recently asking how I would respond to queries about (1) Artificial Intelligence, cognitive science, linguistic engineering, knowledge representation, and related attempts at creating modern subjects, and (2) the relevance of category theory and of mathematics in general to these. My basic response is strong advice to actually learn some category theory, rather than resting content with slinging back and forth ill-defined epithets like �set theory�, �contingency�, etc.. So much confusion has been accumulated that an opposition of the form �set-theoretical versus non-set-theoretical� has at least seven wholly distinct meanings, hence billions of electrons and drops of ink can be spilled by surreptitiously identifying any two of these. For example, the opposition can concern whether or not large cardinal assumptions are needed for a certain result, which is mathematically meaningful and hence independent of whether or not the ZFvN rigidification of Cantor is being used as a framework. Another example is the opposition habitually used in geometry between properties of spaces which can be explained in terms of arbitrary mappings versus those which depend on the cohesion being studied (e.g. �the underlying abstract group vs. the Lie group�). Obviously these two oppositions are not the same although they may be related. One of the oppositions which I have emphasized since 1964 is the ZFvN rigid hierarchy based on galactically �meaningful� inclusion, requiring the totally arbitrary �singleton� operation of Peano with the resulting chains of mathematically spurious rigidified membership, on the one hand, versus the category of abstract sets, involving many potential universes of discourse and arbitrary specific relations between them, on the other hand. (Abstract sets can CARRY structures of mathematical interest, but precisely because of the need of flexibility in the latter, they themselves have only very few properties, unlike the ZFvN �sets�). Within Cantor�s original conception itself there is a fundamentally important opposition: the abstract sets, which he called �Kardinalzahlen�, versus the cohesive and variable sets which he called �Mengen�. (An additional confusion stems from the use, by nearly all of Cantor�s followers, of the term �cardinal number� to mean (not a Kardinalzahl=abstract set, but) a label for an isomorphism class of abstract sets, an invariant which Cantor of course also studied, but which is too abstract to support the specific relations between abstract sets themselves, the mappings, and hence cannot carry the needed mathematical structures). (A) The real issue is that for purposes of pure AND applied mathematics, we need to be able to represent (without spurious ingredients) these cohesive and variable sets (or �spaces�) and their relationships. The ZFvN rigidification fails so miserably in doing this that even those geometers and analysts who pay lip service to it as a �foundation� never in practice use its formalism. (B) Category theory made explicit some universal features of the relationship between quantity and quality whose fundamental importance had been forced into consciousness by the work of Volterra and Hurewicz (both of whom made basic contributions to both functional analysis and algebraic topology) and of many others. This relationship between quantitative and qualitative aspects concerns cohesive and variable sets and structures built on such spaces. For example, Volterra already recognized that spaces have �elements� other than points, and Hurewicz recognized the need for cartesian-closed categories (even before the lambda-calculus formalism, or category theory, was devised); moreover, the original fiber bundles were explicitly modeling dynamical situations, etc. Many people working in the new fields, striving to realize the dream of a theoretical computer science, do not seem to be aware of points like (A) and (B). It would certainly be a bad strategy for the advancement of science to �hide� the fact that category theory belongs to the background of a new result and thus to help perpetuate that sort of ignorance. The role of mathematics in general (not only of category theory) also seems to be widely misunderstood, even in those fields which definitely need more mathematics in order to mature and make a real contribution. For example, some say that logic is more general than mathematics, partly because of ignoring the strongly qualitative aspect of modern mathematics and partly because of the philosophical tradition of hiding the fact that no logic other than mathematical logic has had any significant real-world applications. Because of the minimal mathematical education required of students of philosophy, the claim is too easily accepted in many philosophical circles that �mathematics is unsuitable� for some given issue of conceptual analysis; this conclusion seems to be based on the syllogism: mathematics is set theory (a misconception which the philosophers themselves have done much to disseminate), set theory is clearly not suitable (actually because of the defects of the ZFvN rigidification, which make it ill-suited for mathematics as well) hence ...... This syllogism serves as an excuse to indefinitely postpone learning mathematics (and category theory in particular). An older sort of excuse is the assertion that the proposed science should concern the REAL WORLD, not pure mathematics. This superficially appealing truism has frequently been used to mask the fact that comparing reality with existing concepts does not alone suffice to produce the level of understanding required to change the world; a capacity for constructing flexible yet reliable SYSTEMS of concepts is needed to guide the process. This realization (not Platonism) was the basis of the supreme respect for mathematics expressed by champions of reality like Galileo, Maxwell, and Heaviside. For example, the differential calculus provides the capacity to construct systems descriptive of celestial motions, fluid interactions, electromagnetic radiation fields, etc., and therefore engineers have learned it. The functorial calculus helps to provide a similar capacity adequate to the requirements, not only of the older sciences, but of the newer would-be sciences as well. Hence my response. Bill Lawvere

5 4

Re: Question
by kiniry＠cs.caltech.edu 26 Jan '01

26 Jan '01

Thanks for your email Peter. I will indeed followup as you suggest in the next day or two so that readers will be well-informed about these exciting new opportunities for category theory. Best, Joe Peter Selinger <selinger(a)dead.stanford.edu> writes: > Dear Joseph, > > I don't presume to speak for everybody on the mailing list, but it is > probably safe to say that the majority of readers have no clue what Z, > Ontolingua, KIF, CKML, RDF, TT, OSA, or PL are. Certainly I don't. If > this is an exciting area of applications of category theory, then > category theorists should know about it. If you have time, I think it > would be great if you could briefly explain these terms to the list, > and maybe say a word or two specifically about how category theory is > used there. > > Thanks, -- Peter Selinger > > Joseph R. Kiniry wrote: > > > > Hello Michael, > > > > I believe that category theory is an excellent foundation for ontology > > representation and manipulation -- I use it myself. > > > > However, choosing this foundation comes at a price. Unless significant > > work is done to hide this unfamiliar foundation, many users (of the theory, > > the system, the language, &c) will be biased against the work from > > minute-one. This has as much to do with the unfamiliarity of CT as it does > > with certain unfortunate negative biases regularly expressed by many > > mathematicians and computer scientists - biases that, IMHO, are founded in > > ignorance and not reason. > > > > Many computer scientists, mathematician, and users of knowledge > > representation systems are quite familiar (at least in use, but probably > > not in foundations or related complications) and comfortable with set > > theory. This familiarity is an incentive rather than an obstacle to using > > related work. > > > > Personally, I chose not to pursue a set theoretical foundation because of > > theoretical and representational complexity issues (e.g. witness the use of > > a set theoretical foundation for the Z specification language) as well as > > the unfortunate binding to a particular formalism that isn't necessarily > > congruent with others that I work in and apply my work to (e.g. type theory > > and programming languages). To rephrase, I find using CT to be more clear > > and tractable than set theory and I feel that my work can, as a result, say > > and do more than it could if it had a set theory (plus some extra > > formalisms) bases. > > > > Note that I also chose not to build my work (solely) on type theory and > > order sorted algebras for the same reason, though my work has elements of > > both of those fields as well. > > > > The comments about Ontolingua and KIF are on-target in my experience. I > > see no obstructions to the representation of CKML (the variant related to > > KIF and RDF that I happen to know well) with my work. > > > > Finally, I should point out that I am but an infant in CT - I'm much more > > comfortable with TT, OSA, PL, and others. I've only been learning and > > using CT for a few months and, while there have been some objection to my > > choice, I feel that a dissertation founded in these three major fields (CT, > > TT, and OSA) has significantly broader application and, implicitly, more to > > say about its author. <grin> > > > > Best, > > Joe Kiniry > > -- > > Joseph R. Kiniry http://www.cs.caltech.edu/~kiniry/ > > California Institute of Technology ID 78860581 ICQ 4344804 > > > > > > --On Tuesday, January 16, 2001 04:17:19 PM -0800 "Michael J. Healy > > 425-865-3123" <mjhealy(a)redwood.rt.cs.boeing.com> wrote: > > > > > > > > I'd like to ask category theorists how they would answer the attached > > > message from a colleague here. Both he and the person with whom he is > > > corresponding are experts in the areas of knowledge representation > > > within computer science (ontologies and the like). I thought it best to > > > hide their identities since I haven't asked permission to use them. If > > > you are interested, please respond to me privately if you would. > > > > > > Thank you, > > > Mike Healy > > > ------------------------------------------------------------------------- > > > ----- > > > > > > Message I received:---- > > > > > > I would be delighted if there was no semantic conflict between > > > category theory and set theory. I kind of flagged this as a > > > potential issue, but did not look into it in detail, as it was > > > not my main concern at the time. However, I remain unconvinced. > > > There has been some discussion of using set theory as the basis > > > for a semantics for SUOKIF. If this is true, then I think it may > > > be limiting to a CT based language. While it may be true that sets > > > are common example of a catagory, my sense is that CT is much more > > > powerful, and would be LIMITED if everything was forced into the > > > single catagory of sets. > > > > > > Im a bit out of my element here, however, and need to defer to the > > > formal expertise of others on this issue. > > > > > > > > > Message to which the above was replying:--- > > > > > > I agree that category theory is very powerful and could be > > > an important basis for combining and sharing ontologies. > > > But I disagree with the following point: > > > > > >> I think this idea has tremendous potential. One problem is that the > > >> underlying > > > > > >> formal semantics of category theory is NOT set theory (which is what KIF > > >> uses), > > > > > >> furthermore, I think they may well be incompatible. > > > > > > First-order logic (including any and all notations for it, > > > such as KIF, CGs, predicate calculus, existential graphs, etc.) > > > is completely neutral with respect to set theory or category > > > theory. The version 3.0 of KIF did include a version of set > > > theory, but that was removed in the KIF'99 version because it > > > belongs to ontology rather than logic. > > > > > > And for that matter, there is no reason why you can't use both > > > category theory and set theory together. In fact, one of the > > > most common examples of a category is the category of sets. > > > > > > Perhaps there may be incompatibilities between the methodology > > > associated with Ontolingua and category-based techiques, but > > > Ontolingua is not KIF. Ontolingua simply uses KIF. > > > -- > > > > > > Michael J. Healy > > > > > > > > > -- Joseph R. Kiniry http://www.cs.caltech.edu/~kiniry/ California Institute of Technology ID 78860581 ICQ 4344804

4 3

Conf. Session Opportunity URL correction
by Yuri Velinov 26 Jan '01

26 Jan '01

Dear all, Sorry for the misprint. This is what happens when you leave the work to a secretary. The correct URL http://www.iiis.org/sci Yours YV

1 0

Re: Machines in a Category
by D. E. (Steve) Stevenson 25 Jan '01

25 Jan '01

The original paper is Michael A. Arbib and Ernest G. Manes. "Machines in a Category: An expository introduction". SIAM Review. 16(2). April, 1974 (not 1976 as below). 163--192. Very available. steve At 12:45 AM 25-01-01 +0000, Bill Halchin wrote: > >Better how about a copy of the paper (assuming of course there is >a soft copy somewhere). > >Bill halchin > >>From: Steve Stevenson <steve(a)cs.clemson.edu> >>To: categories(a)mta.ca >>Subject: categories: Machines in a Category >>Date: Wed, 24 Jan 2001 08:28:29 -0500 (EST) >> >>In the mid 70s, Anderson, Arbib, and Manes did some work on "Machines >>in a Category" (SIAM, 1976) A lot of this was in support of work in >>using category theory in control theory. >> >>Can anyone provide information about the state of this research or a >>bibliography of this work in unifying control theory and computation? >> >>Best regards, >> >>steve >>---- >>D. E. (Steve) Stevenson, Department of Computer Science, Clemson >> >>At the genetic level, race does not exist. Studies of human DNA have >>found that there is far more genetic variability between individuals >>within any "given" group than between two such groups. >>Dawn Stover, <em> New York Times >>

1 0

Machines in a Category
by Steve Stevenson 25 Jan '01

25 Jan '01

In the mid 70s, Anderson, Arbib, and Manes did some work on "Machines in a Category" (SIAM, 1976) A lot of this was in support of work in using category theory in control theory. Can anyone provide information about the state of this research or a bibliography of this work in unifying control theory and computation? Best regards, steve ---- D. E. (Steve) Stevenson, Department of Computer Science, Clemson At the genetic level, race does not exist. Studies of human DNA have found that there is far more genetic variability between individuals within any "given" group than between two such groups. Dawn Stover, <em> New York Times

2 1

Conference Session Opportunity
by Yuri Velinov 25 Jan '01

25 Jan '01

Dear Colleagues, There is an opportunity to organize a session on FORMAL STRUCTURES IN COMPUTER SCIENCE in the framework of SCI2001 in Orlando, Florida (July 22-25-2001) (see www/iiis/org/sci for more information) . If you are interested please send me in the next couple of days the title an a short abstract of your possible contribution. Sincerely Yours Y.Velinov

1 0

ETAPS 2001 FIRST CALL FOR PARTICIPATION
by TR＠lipn.univ-paris13.fr 23 Jan '01

23 Jan '01

ETAPS 2001 APRIL 2 - 6, 2001 - GENOVA, ITALY The European Joint Conferences on Theory and Practice of Software (ETAPS) is a loose and open confederation of conferences and other events that has become the primary European forum for academic and industrial researchers working on topics relating to Software Science. http://www.disi.unige.it/etaps2001/ ----------------------------------------------------------------------- 5 Conferences - 10 Workshops - 10 Tutorials 7 Invited Lectures - 1 panel- 9 Tool Demos ----------------------------------------------------------------------- PROGRAM - REGISTRATION FORM - HOTEL BOOKING ----------------------------------------------------------------------- see http://www.disi.unige.it/etaps2001/ !!!!!! ONLINE REGISTRATION AVAILABLE NOW !!!!!! IMPORTANT DATES: ----------------------------------------------------------------------- FEBRUARY 10: deadline to register GETTING 10% DISCOUNT on fees MARCH 2: deadline to register having HOTEL GUARANTEED and AVOIDING 20% SURCHARGE on fees April 2-6, 2001: ETAPS 2001 in Genova March 31 - April 8, 2001: Satellite Events CONFERENCES ----------------------------------------------------------------------- CC 2001: International Conference on Compiler Construction ESOP 2001, European Symposium On Programming FASE 2001, Fundamental Approaches to Software Engineering FOSSACS 2001, Foundations of Software Science and Computation Structures TACAS 2001, Tools and Algorithms for the Construction and Analysis of Systems WORKSHOPS ----------------------------------------------------------------------- CMCS: Co-algebraic Methods in Computer Science ETI Day: Electronic Tool Integration platform Day JOSES: Java Optimization Strategies for Embedded Systems LDTA: Workshop on Language Descriptions, Tools and Applications MMAABS: Models and Methods of Analysis for Agent Based Systems PFM: Proofs For Mobility RelMiS: Relational Methods in Software UNIGRA: Uniform Approaches to Graphical Process Specification Techniques WADT: Workshop on Algebraic Development Techniques WTUML: Workshop on Transformations in UML TUTORIALS ----------------------------------------------------------------------- T1: Common Framework Initiative for Algebraic Specification and Development of Software T2: Abstract State Machines: Surveying their Theory and their Industrial Employment T3: Compiling object-oriented programming languages T4: Rule based programming using ELAN: a Tutorial T5: Mathematical Foundations for Software Architecture T6: Rigorous Analysis and Design with the Unified Modeling Language (UML) T7: Domain Analysis and Engineering with Sherlock - producing Software Product Lines T8: Extreme Modeling - Closing the Gap between Modeling and XP T9: Precise Component Architectures with UML/Catalysis T10: TTCN-3 - The new testing language for telecom and datacom INVITED LECTURES ----------------------------------------------------------------------- Luca Cardelli: Global Computing Michael Fourman: Propositional Reasoning Ole Lehrmann Madsen: Virtual Classes and their Implementation John Mitchell Gordon Plotkin: Adequacy for Algebraic Effects Bran Selic: Physical Programming: Beyond Mere Logic Moshe Y. Vardi: Branching vs. Linear Time: Final Showdown PANEL ----------------------------------------------------------------------- Free software: the future of software engineering?

1 0