On Sunday, July 7, 2002, at 12:23 AM, Wei Dai wrote:
> Hi Tim, it's really interesting to see you here. (For those who don't > know, I knew Tim from the cypherpunks mailing list. Hal Finney was an > active member of the list as well. See > http://www.activism.net/cypherpunk/crypto-anarchy.html if you're > wondering > what a cypherpunk is.) Two of the most prominent cypherpunks I know are > now on my Everything mailing list. I wonder what that means... Anyway, > welcome! Thanks. One of my motivations here is to a) learn, b) have a chance to explain what I have learned (which helps to learn), and c) avoid politics and policies and similar issues completely. (Unless there is talk of funding a National Everything Initiative, I think it's safe to say that politics won't enter!). The first couple of years, especially the first year, of Cypherpunks was heavy on learning and explaining, but politics was of course important. The last several years have been recyclings of older ideas...this can happen to any list, of course. I've known of the Everything list, and of course the Everett/DeWitt/Niven/Wheeler/Egan/Tegmark ideas for a while...I remember reading Larry Niven's "All the Myriad Ways" around 1970 or so. We used to sit around in the early 70s debating the Everett model, which a couple of science fiction writers were making much of, and which had gained new popularity after Bryce DeWitt dusted off the idea and began publishing a lot on it. (DeWitt assigned much credit to his student, RN Graham, and even called the MWI the "Everett-Wheeler-Graham" theory. Way too charitable to Graham, I think.) I learned of your list a while back, but wasn't super-interested in what I thought (and partially still think) is a fanciful idea, akin to the late David Lewis' "plurality of worlds" philosophy (that everything we can imagine must have reality). Saul Kripke's "possible worlds" work was more interesting, as it is closely linked to linguistics and AI and predictions about the future ("If Oracle were to announce bad earnings tomorrow, then this is what would probably happen," a possible worlds "story" which is of course very close to some discussions of alternate _presents_. In fact, no different, except more practical.) Enough of this digression. I'll answer your question: > > I remember your post on the cypherpunks list about category theory, > but I > have to admit I didn't pay it much attention since it didn't seem very > relevent at the time. I posted to that list just to let folks know I was exploring a new area. And because there actually be implications for areas of interest...I mentioned these in that post. > I guess this is my second chance to learn about > category theory, so there are some questions for you. > > Suppose I had the time for only one book, which would you recommend? I would start with Lee Smolin's "Three Roads to Quantum Gravity." This is not about category theory, but provides a lot of the motivation. He discusses many of the points that I allude to. In bullet form: -- that we are embedded in the universe, that there is no "omniscient observer who can see all of space-time" -- that certain pieces of information are forever beyond our ability to see. These turn out to be important for why accelerating objects see a "temperature" of space, isomorphic to the temperature seen by a spacecraft hovering over a black hole expending fuel at the same rate. (I can explain separately if there's interest.) -- that space appears to be discrete at the Planck scale (a la the "It from bit" discreteness outlined by Wheeler 30 years ago, later by Fredkin, Toffoli, and others, and more recently by Wolfram)--this discreteness has not been proved, and may not be testable for many decades, but all three of the routes Smolin outlines essentially predict that space-time is not an infinitely differentiable (smooth) manifold made of real numbers: the holographic/Crane/Susskind route, the loop gravity/spin foam route, and the currently much popularized string/M-brane Schwartz/Witten/etc. route. -- that _relationships_ are more important than objects (which fits very closely with category theory, as I'll explain below) -- that the proper logic of understanding cosmology, given some or all of the above points, is not the "omniscient" logic of Aristotelian/Boolean logic ("A or not-A, nothing in between"), but a more general form of Intuitionist (bad political connotations for many!) Brouwer/Heyting logic, which also happens to be the natural logic of a topos, a category with certain properties of logic attached to it. Smolin spends a few pages discussing topos theory, but in such light detail that anyone not tuned in to spotting the phrase "topos theory" might even miss it. He refers to Fotini Markopoulou, a Greek woman who collaborates a lot with him and with the other biggies of the "loop gravity/spin foam" school, e.g., Rovelli, Ashketar, Baez, etc. If you want a straight intro to category theory, with none of the stuff about cosmology, space-time, and such, the Lawvere and Schanuel book "Conceptual Mathematics: A first introduction to categories" is the book I recommend. But perhaps before reading a book, surfing the Web is better. There are many tutorials and primers, and one can read a bunch of them to get the lay of the land. I've mentioned John Baez's site a couple of times. Chris Hillman has a good "Categorical Primer," but it's incomplete. Some authors, like Barr and Wells, have even put their books up on the Web. Reading any of the main books will not show many _apparent_ links to Tegmark, Schmidhuber, etc. The same applies to reading Kleene's 1952 opus, "Metamathematics," or Lang's "Algebra," or any math book. None of these will appear to be closely relate tp theories of everything, or multiverses. One has to read between the lines. For example, when reading about categories, think of Tegmark's diagram showing links between "Abelian Fields," "Manifolds with Tensors Fields," etc. A categorical approach is cleaner and shows the morphisms more clearly. Take a look at category theory for about 2 days (of 2-3 hours a day) and then look at Tegmark's paper again. (This is just for the formalisms he talks about, not the underlying philosophical point.) > Also, > can you elaborate a bit more on the motivation behind category theory? > Why > was it invented, and what problems does it solve? OK, on to some history. Mathematics had two great waves of consolidation and formalization in the past century. Around 1920 much had been done with symmetries, embodied in group theory. Much was known about integers and even the real number line, embodied in the work of Stephen Dedekind in the 19th century. Also, G. Peano, etc. This was mostly the algebra of rings and fields. (On mostly separate tracks, a lot of work in topology, logic, set theory.) Two associates/students of David Hilbert largely gave us our modern outlook on math in the 1920s: Emil Artin and Emmy Noether. In influential lectures in Germany during the 1920s they consolidated all of the bits and pieces about groups, rings, fields, modules, and vector spaces into a coherent, axiomatized whole. Others in this milieu were Herman Weyl, John von Neumann (different country, but still same milieu), David Birkhoff (in the U.S.), and others. One of those who transcribed Artin's and Noether's lectures was van der Waerden, who wrote an enormously influential book, "Moderne Algebra," published around 1930-32 in German. Van der Waerden established the "groups-rings-fields" structure of nearly all of the abstract algebra books to come later, such as G. Birkhoff (David's son) and Mac Lane's 1941 text in English, Jacobson's early 50s text, Mac Lane and Birkhoff's more advanced text, Herstein's "Topics in Algebra," and so on. One of Emil Artin's students (both Artin and Noether moved to the U.S. in the early 1930s, part of the enormous wave of refugees from Germany and Europe) was Serge Lang, author of a dozen or more "classics." (Warning: Lang's books are dry, but complete.) OK, so that was the first great wave of consolidation in "real" mathematics. (By "real" I mean the stuff mathematicians actually use every day...there were of course consolidations in foundational areas happening at about the same time, via Russell, Whitehead, Godel, Curry, Church, Kleene, etc.) This was the "abstract math" we all know and love. Around 1940 there was much work on applying algebra to topology, e.g., counting holes in surfaces, seeing which loops drawn on a surface could be contracted to points and which could not. Two of those working on this were Samuel Eilenberg, a young emigre from Poland (dubbed "S-squared, P-squared, for "Smart Sammy the Polish Prodigy") and an equally young Saunders Mac Lane, the same as the author of the Birkhoff and Mac Lane basic text on algebra. The combination of algebra and topology is of course algebraic topology. What Eilenberg and Mac Lane realized is that certain _structures_ were present in both algebra and topology, and that _structure-preserving maps_ were showing up all over the place. For example, deformations of an object would have the same structure as algebraic transformations. Even examples like counting holes in surfaces were in a deep sense isomorphic to counting things in purely symbolic or algebraic structures. They began thinking about what the abstract ideas were, and came up with the core ideas: -- that maps, or arrows, or morphisms go between objects -- that the arrrows themselves can be studied, and that arrows between the arrows (morphisms of morphisms) are interesting to look at. (The arrows between arrows, or the morphisms between morphisms, are usually called "functors.") (Digression: For example, look at _languages_. Words in English are mapped into their plural form in various ways, usually by adding an "s." Sometimes in other ways ("oxen"). The morphisms between words can be compared (mapped) to morphisms between words in other languages, e.g., Chinese, German. There are functors going between plural formation in English and plural formation in German. And between other structures in each of these languages. In this sense, the "structures" of different languages can be diagrammed and compared in a more interesting way than simply talking about them or just by compiling descriptions.) -- that we can often take the set of objects and morphisms and view them as a "picture" (a model, sort of) of relationships -- that "natural transformations" are ways of "sliding" this picture into other categories, other domains -- critical to much of category theory is the analysis of diagrams, showing arrows from A to B, or A --> B, arrows from C to D, etc., and then figuring out what is needed to make such diagrams commute (as an example). This leads to things I won't try to explain here (for space, and because I'm not the best person to look to for such explanations) such as "pushouts" and "pullbacks." And it turns out that these diagrams are closely linked to physics issues (!). (If you turn on your morphing engines and begin playing with the words, you probably are already speculating that maybe Feynman diagrams are a kind of category theory diagram. And you would be right. See John Baez's "From Causal Sets to Feynman Diagrams" for more.) (Digression: By talking to you folks, by attempting to explain these ideas, I am essentially trying to take the picture which is inside _my_ head and plant some semblance of it in _your_ head. This is a kind of natural transformation, albeit much more complicated and fuzzier than most nice, formal, pristine examples in math!) So in 1945, delayed for 3 years by the war, Eilenberg and Mac Lane published their influential and very long paper on what they called "categories." A category was like a set, except made up of objects and arrrows between the objects. Ordinary sets formed the category SET. Vector spaces formed the category VECT, and so on, for essentially all objects and relationships known to mathematics. And of course there are then ways to map one category into another, or to compare two categories (actually mapping and asking about the mapping are of course essentially the same thing, with just a change of direction or emphasis). Eilenberg and Mac Lane used category theory as a concise and unifying notation for talking about mathematics, especially for algebraic topology. Use of category theory for algebraic topology (particularly an important branch called "homology theory") became widespread in the late 40s and ever since. Aside: They coined the term "category." Perhaps they should have called them something like "structures." Then category theory would be understand at a glance (via those morphisms in our everyday language, those patterns!) as "structure theory." Or as "pattern theory." And then probably more people would have understand why it would likely to be very important. But much more was to come. In the late 1950s a couple of important extensions (obscure pun not intended) of Eilenberg and Mac Lane's "notational language" happened. Daniel Kan discovered the "Kan extension" and proved something called the "adjoint functor theorem." Now physicists have used "adjoints" and "self-adjoint" concepts for years. When the category theory and algebra people showed the power of their diagrams, physicists began to take notice. And at around that time the great mathematician Grothendieck developed some notions which led to a particular kind of category called a topos. (No space in this already too-long article to try to explain what a topos is.) William (Bill) Lawvere was a young student of Eilenberg's. He was convinced that topos theory could provide a foundation for mathematics equvalient in power to that of set theory. Instead of sets consisting of points and axioms about inclusion we would have objects (not necessarily consisting of points) and arrows (morphisms). According to the story, Mac Lane warned him away from attempting this. The story goes that Eilenberg and Mac Lane were flying down to consult for the Pentagon in 1963 and Eilenberg handed Mac Lane the recently completed thesis of Lawvere. Bill Lawvere had largely established that toposes could form the basis of all of mathematics. (Some worked needed to be completed, and this was largely done by 1970.) Meanwhile, a couple of major theorems were solved in the 1960s with the use of category theory: the Weill Conjecture and Paul Cohen's work on "forcing" to Let me give a description I found of just one course in topos theory. This will mention a lot of buzzwords, including folks like Saul Kripke (logician, "possible worlds"), Grothendieck, etc. Don't expect to grok this from a course summary (!), but I include it to show some of the links: http://www.math.uu.se/~palmgren/topos-eng.html "Topos Theory, spring term 1999 "A graduate course (6 course points) in mathematical logic. ------------------------------------------------------------------------ "Topos theory grew out of the observation that the category of sheaves over a fixed topological space forms a universe of "continuously variable sets" which obeys the laws of intuitionistic logic. These sheaf models, or Grothendieck toposes, turn out to be generalisations of Kripke and Beth models (which are fundamental for various non-classical logics) as well as Cohen's forcing models for set theory. The notion of topos was subsequently extended and given an elementary axiomatisation by Lawvere and Tierney, and shown to correspond to a certain higher order intuitionistic logic. Various logics and type theories have been given categorical characterisations, which are of importance for the mathematical foundations for programming languages. One of the most interesting aspects of toposes is that they can provide natural models of certain theories that lack classical models, viz. synthetic differential geometry. "This graduate course offers an introduction to topos theory and categorical logic. In particular the following topics will be covered: Categorical logic: relation between logics, type theories and categories. Generalised topologies, including formal topologies. Sheaves. Pretoposes and toposes. Beth-Kripke-Joyal semantics. Boolean toposes and Cohen forcing. Barr's theorem and Diaconescu covers. Geometric morphisms. Classifying toposes. Sheaf models of infinitesimal analysis. "We will assume some familiarity with basic category theory, such as is obtained in courses in domain theory or algebra. The course will be given English, in case someone requests this. " (Sorry for the quoted material, but it sometimes helps to see someone else talking about something. At least I find it does.) I'd best move on to answering or commenting the rest of Wei Dai's questions: > What's the relationship > between category theory and the idea that all possible universes exists? I believe it provides a natural language for talking about time-varying sets and "sheaves" (Jargon Alert: the "sheaf" in mathematics may not match exactly what one pictures a "sheaf of histories" to look like. But mathematicians usually pick names that bear _some_ resemblance to ordinary things, e.g., fibers, fiber bundles, sheaves, pre-sheaves, partially ordered sets, spaces, etc.) Personally, I'm not (yet) "taking seriously" either the David Lewis "plurality of worlds" or Max Tegmark "everything" or Greg Egan "all topologies model" ideas. At least not yet. I need to learn a lot more of the language first. (Without a good language, we end up just _talking_ and _speculating_. I'm finding my category theory reading is giving me a welcome new perspective on issues I've long been fascinated with, e.g., if a single atom were to have been moved on Sirius a million years ago, would the world around us be different? And how much different? The cascade of changes has what topology? Is it the Pachinko topology?) My strong hunch is that the universe at these levels (nature of space-time) will need all of the mathematical tools we can muster. Now, I'm not saying one needs to be an expert at group theory, for example. Or that one needs to know all of algebraic topology. But it's pretty clear to me that mathematics has historically been our most important tool for all of the interesting branches of physics. No one can get far in relativity or quantum mechanics without mastering some interesting math. For me, category theory has been a stunning window on things. I regret that it is not taught, or even mentioned, to most physicists. (This may be changing, with the books by folks like Robert Geroch, who starts with category theory and covers much of modern physics from this perspective, and the progress by the string theory and quantum gravity communities.) > Does it help understand or formalize the notion of "all possible > universes"? I know in logic there is the concept of a categorical theory > meaning all models of the theory are isomorphic. Does that have anything > to do with category theory? Yes, there are deep and important connections. Models form a category. The book I mentioned by Paul Taylor, "Practical Foundations of Mathematics," is very good on these issues. In my view, category theory (and topos theory) represents the "modern" way of looking at a lot of seemingly unrelated areas. As we know, as Hal Finney and several of us used to discuss about ten years ago on the Extropians list, Chaitin's formulation of algorithmic information theory gives us a much more understandable and comprehensible proof of Godel's Theorem than Godel himself gave! (For the best explanation of this, and why this is so, either see Greg Chaitin's own papers and books or the wonderful summaries by Rudy Rucker in his "Mind Tools" book. These modern viewpoints are much more comprehensible than the classics. Which is not surprising. Shoulders of giants and all that. The same is true of category theory. It's a relentlessly modern approach to seeing the similarities that pervade mathematics and physics. Whether it answers the question about whether lots of other universes exist is doubtful...I'm not convinced we'll know the answer to that question in the year 3000. But it's a powerful and elegant approach, with perhaps a slightly misleading name, and it looks to me to be the right language for talking about the world around us and possibly the worlds we cannot directly see. I agree with Lee Smolin that topos logic is not just the logic of cosmology, but also the logic of our everyday world of limited information, bounded rationality, Bayesian decision making, and information horizons. Even if this is not useful for answering questions about "the Everything theory," because we may need to wait 600 or 6000 years for experimental tests to become feasible, I believe this outlook will be of great utility in many areas. I'll keep you all posted! --Tim May
