- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]

From: Tim May <tcmay.domain.name.hidden>

Date: Sun, 4 Aug 2002 11:09:17 -0700

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

Date: Sun, 4 Aug 2002 11:09:17 -0700

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

*
This archive was generated by hypermail 2.3.0
: Fri Feb 16 2018 - 13:20:07 PST
*