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
