From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.io/gmane.science.mathematics.categories/5813 Path: news.gmane.org!not-for-mail From: Vaughan Pratt Newsgroups: gmane.science.mathematics.categories Subject: Words, sets, categories, and graphs Date: Sun, 16 May 2010 02:19:26 -0400 Message-ID: References: Reply-To: Vaughan Pratt NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Trace: dough.gmane.org 1274031013 8261 80.91.229.12 (16 May 2010 17:30:13 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Sun, 16 May 2010 17:30:13 +0000 (UTC) To: categories@mta.ca Original-X-From: categories@mta.ca Sun May 16 19:30:12 2010 connect(): No such file or directory Return-path: Envelope-to: gsmc-categories@m.gmane.org Original-Received: from mailserv.mta.ca ([138.73.1.1]) by lo.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1ODhfG-00030p-1r for gsmc-categories@m.gmane.org; Sun, 16 May 2010 19:30:10 +0200 Original-Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1ODhLm-000151-E9 for categories-list@mta.ca; Sun, 16 May 2010 14:10:02 -0300 In-Reply-To: Original-Sender: categories@mta.ca Precedence: bulk Xref: news.gmane.org gmane.science.mathematics.categories:5813 Archived-At: Dusko asked: > is there any reason why words should be taken seriously? Colin answered: > That just depends on whether or not you want to be understood by > people who do not already know everything you are going to say. I took Dusko's question to be about particular words rather than words in general. However I've become rather attached to the latter in connection with foundations of mathematics. It's fashionable in certain circles to consider mathematics to be founded on the concept of set, customarily defined by ZFC, a first order language with a single nonlogical symbol, membership, a binary relation. After considerable development one can eventually arrive at the notion of free monoid on an alphabet, whose elements can be identified with the words over that alphabet. On that basis it is argued that sets are conceptually prior to words. Throughout this development however the exposition is mediated by words. On that basis it would appear that words must be conceptually prior to sets, since without words how can sets be explained? Category theory is as much organized around the binary operation of composition as ZFC set theory is around the binary relation of membership. Composition of morphisms works like concatenation of words with the following two refinements. 1. Multiple objects. Whereas any two words can be concatenated, morphisms have a domain and codomain which composition must respect. This creates a form of phrase structure grammar in which each phrase has not one type but two, one at each end. Words thereby form the edges of a graph G, the finite paths in which constitute the composites, forming the free category G* on G. (William Wood's notion of Augmented Transition Network, ATN, as developed in his 1968 Harvard Ph.D. thesis, see also CACM 13:10 (Oct. 1970), works roughly that way. The idea is to replace the notion of nonterminal vocabulary V_N with that of state set Q of an automaton, with the transitions labeled with either terminals from the terminal vocabulary V_T or subroutine calls to other graphs. An Augmented Syntax Diagram, ASD, is similar but with the edge labels moved to the vertices. It would be nice if the categorial grammars of Ajdukiewicz (1935), Bar-Hillel (1953), and Lambek (1958) were vertex-oriented along those lines but I haven't seen linguists explicate them that way.) 2. Commutative diagrams. A congruence T on, or typed equational theory of, the paths in such a graph. A category C = (G,T) consists of a graph G whose finite paths, as words with typed endpoints, are understood modulo a given congruence T on G*, namely as the quotient C = G*/T. Every category can be presented in this way, just as every group can be presented by generators and relators. (Like many computer scientists I'm a big fan of both graph theory and equational logic and have no objection to inferring from the above that graphs and equational theories should be considered conceptually prior to categories. And for that matter prior to sets, since a set can be defined as simply a graph with no edges, which is how I generally picture them.) Had Russell and Whitehead developed Principia Mathematica by starting with words, they could have defined numbers as words on a one-letter alphabet, with addition defined simply as concatenation. Their proof that 1+1 = 2, which with their approach they were able to complete by Volume II, could have been shortened to the reasoning I+I = II, which could surely be dealt with by page (ii) of the forward. By extending this approach to numbers to provide for larger alphabets, multiple objects, and commutative diagrams, they could have compressed their three volumes into one chapter, freeing up time and space for further principles. That's with a century of hindsight, mind you. That much hindsight applied to heavier-than-air flight would have been harder because gasoline engines were relatively new in 1903, cf. http://en.wikipedia.org/wiki/Steam_aircraft . Graphs and congruences are not at all new. Vaughan [For admin and other information see: http://www.mta.ca/~cat-dist/ ]