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
Received on Sun Jul 07 2002 - 11:41:14 PDT