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 <[EMAIL PROTECTED]>
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

Reply via email to