Everything folks,
Here's a posting I made last night to another list, a list of folks who
meet to discuss math. I had been telling them about nonstandard logic,
notably Intuitionist or Brouwer/Heyting logic, and the natural logic of
toposes. This post below expands on a few points we had been talking
about at our session in Palo Alto a few days ago.
(By the way, if anyone is local to the Bay Area and wants to try one of
the evening gatherings, let me know. We just started meeting and it's
too soon to know how it'll go in the future. The basic idea is to have
an informal group similar to the "Assembler Multitudes" nanotechnology
discussion group that Ted Kaehler ran in the early 90s. I enjoyed that
group immensely and was disappointed to see it fade out. With all of the
new excitment in math, and with links to the cosmology and Everything
universes, it seems to be a good time to try something again. We had six
people at our gathering a few days ago.)
The background for this article is not given here, so I'll make a very
few points now:
* conventional logic (Aristotelian, Boolean) uses "law of the excluded
middle": A or Not-A, something is or is not, the complement of an open
set is a closed set. The complement of a complement of a set is the set.
* alternative or nonstandard logics exist, and turn out to be quite
natural...when looked at properly.
* one of these is the logic pursued by Brouwer early in the 20th
century: Intuitionism (which is not mysticism, by the way). Brouwer
argued that only constructible entities have meaning, that abstractions
about infinite sets or things like the axiom of choice are misleading.
His student Heyting formalized the axioms of Intuitionist logic.
Marshall Stone proved in the 1930s that the set of operations on open
subsets of a set (think of blobs drawn on a page, or time intervals,
etc.) forms a Heyting algebra, that is, that the natural logic for these
open sets is not Boolean logic, but Heyting logic.
* lattices are sets of node and links between the nodes which satisfy
certain properties, such as that any two nodes have a "meet" and "join."
Events in time are a good example of a lattice.
* partially ordered sets (posets) are those with some relationship (such
as "less than or equal to" or "preceeds or happens at the same time" or
"is contained in or equals") such that certain properties of comparison
exist. Posetss are less ordered than the integers, for example, which
are fully-ordered. An example is containment and inclusion of open sets
(or intervals on the line).
(The Web has a lot of good definitions, complete with diagrams and
drawings, of these ideas. For example, MathWorld has this article on
posets:
http://mathworld.wolfram.com/PartiallyOrderedSet.html.)
* To relate this to the Everything list, sort of, imagine the lattice of
events in "our" universe. It forms a poset, basically. What about
possible "branch points" where other universes form (as in MWI)? What
about the overall notion of "possible worlds"? (Branching, fictional, AI
planning, plurality of worlds a la David Lewis, etc.).
* Fotini Markopoulou has been looking at causal sets and the nature of
time. Her articles are available at the xxx.lanl.gov arXive site.
Here's the article:
From: Tim May <tcmay.domain.name.hidden>
Date: Sat Aug 03, 2002 10:57:18 PM US/Pacific
To: xxxxxxxxx
Subject: Time, causality, posets, Heyting
....
Second, while watching a fairly silly movie called "Signs" today, I was
thinking about the issue of "when is a negation of a negation of
something not the same as that something. That is, "not not A !=! A" or
"not not A NEQ A" or A' ' NEQ A. (Lots of symbologies exist, and our
keyboards and screens can't easily handle the most common ones.)
An example Mac Lane gives in "Form and Function" is this:
Consider the real number line. Consider the topology of open sets (or
intervals). Suppose that we define an open set (or interval) U which is
the open set of all of the positive reals _EXCEPT_ the number 1. Then
"Not U" or "Complement of U" would be the set of all negative reals. (1
would not be in this complement because any actual number is of course a
_closed_ set (endpoints and all that stuff from the definition of open
and closed intervals. (Drawing a picture on a blackboard would help!)
So far, no surprises.
However, the negation or complement of his open subset (the negative
reals) is the open subset of all of the positive reals. So Not Not U is
bigger than U.
This phenomenon of Not Not something being larger than something is
common in Heyting algebras.
Think about time. Think of a "lattice" of events combining in various
causal ways to product events, which then combine with other events, and
so on. Judea Pearl has some of these causal diagrams in his book
"Causality," and Lee Smolin has some in his book "Three Roads to Quantum
Gravity." A basic idea, to be sure.
OK, suppose one is at time t. What's the "negation" or "complement" of
the open set "PAST"? Obviously, "FUTURE." Not-PAST is FUTURE and
Not-FUTURE is PAST. So Not-Not-PAST is PAST and Not-Not-FUTURE is
FUTURE. Standard Aristotelian or Boolean logic, standard common sense.
Or is it?
Drawn as a lattice, with the various events having various links and
with a "partial ordering" (hence the term "poset"), the FUTURE is
affected by events which are unable to be compared (before, after, same
time) as events right now or in the PAST.
This may not sound clear. In a Newtonian world, with no limits on the
speed of information flow, the PAST is plausibly the same for all
observers. But not so in our actual world. Events "outside our light
cone" cannot be said to have occurred before some time, after some time,
or at the same time as something. Different observers travelling at
different speeds may see entirely different orders of events. There is
no absolute PAST or FUTURE.
OK, but at some future time, when the light cones intersect, some event
from that "other" light cone can help to make some event happen. For
example, a supernova happening "now" at Alpha Centauri will take 4.3
years to make its presence felt here on Earth.
Perhaps you see where this is going. Not-PAST is FUTURE, but
Not-Not-PAST is not the PAST. Things get bigger, exactly as with the
example above with the real number line and the open subset topology on
it.
In fact, the lattice that makes up non-classical time and the open
subset topology both are examples of posets. (The oddly-named poset is
thus a common thing, more "practical" than a fully-ordered set where
'trichotomy" holds: something is either bigger than, smaller than, or
the same size as something else. Or an event either occurs before,
after, or at the same time as some other event.)
(Ultra-speculatively, it would be interesting to see what connections
exist between the amount of "size growth" and entropy, a la the
Bekenstein bound and holographic models of relativistic systems. I sense
there's something there, but I haven't looked hard enough yet, or with
enough knowledge.)
And there's another parallel example. Those causal diagrams, with things
happening and combining and contributing to future events...well, they
are of course just a logic circuit. And though it is canonically true
that these circuits use "Boolean logic" (Boolean algebras), that is in
fact only _locally_ true. The global picture is one of a lattice just
like the lattice above with time and events. The FUTURE is more than
just a negation or complement of the PAST...it is affected by
information flow from other parts of the universe (the chip, the
computer, the program). This is why computations are not trivial...
So, it seems natural to view logic circuits and programs in this
"lattice/poset/Heyting algebra" scheme...which is presumably what all
those books and papers on such things is going to tell me when I am able
to read them! (And why category theory/topos theory/sheaves is so
closely tied to computer science.)
This is very cool stuff. The basic stuff of reality.
There may be practical applications. Clockless logic, reversible
computing, and issues of concurrence are perhaps best analyzed in terms
of these poset lattices. Checking Google on this, I find that Vaughn
Pratt, a local prof at Stanford I expect most of you have heard of, has
been exploring this area for a while now. (And I saw his name just
yesterday in the URL Peter sent us on Mac Lane's comments on e-mail.)
Note that the "lattice/poset" model doesn't require the speed of light
limits that relativity gives us. It applies just as well to conditions
of limited visibility into what other agents are doing (hence links to
categorification of money??) and to essentially any situations where the
aforementioned trichotomy fails. I contend that this is "most of the
time." (Though as analysts and scientists we often then simplify and
make assumptions to get to situations where trichotomy applies or is
assumed to apply, and hence where linear orderings are usable and hence
where the "weirdnesses" of Intuitionistic/Heyting logic don't show up.)
A huge amount of stuff to learn on this. Which I count as being good,
because I hate boredom! I can see why Smolin says in
"Three Roads" that topos theory is perhaps the hardest thing he's ever
tired to learn. Most branches of mathematics, like partial differential
equations or differential geometry, have a clearly defined set of tools
and results. This area keeps expanding, with background needed in first
order logic, proof theory, type theory, topology, more topology,
algebra, lattice theory, and more! Familiarity with Kleene, Rosser,
Church, Curry, Godel, and all of the other logicians is helpful. Just
one of my books, Paul Taylor's "Practical Foundations of Mathematics,"
looks like it will take me years and years to master.
Great interdisciplinary stuff, though, as it hits on the themes above:
the causal structure of reality, cosmology, why information is so
important, the nature of language (possible worlds semantics), and even
the deep nature of computation.
--Tim
Received on Sun Aug 04 2002 - 11:15:24 PDT