Re: modal logic and possible worlds

From: Tim May <tcmay.domain.name.hidden>
Date: Tue, 13 Aug 2002 10:08:50 -0700

On Monday, August 12, 2002, at 11:41 PM, Russell Standish wrote:

> Bruno probably does, but I'll put my spin on it. Each distinguishable
> "world" is a description*, which is a conjunction of propositions "I
> have green eyes _and_ I live in Sydney _and_ the twin towers were
> destroyed by airliners on 11/9/2002 _and_ ...", and as such is a
> proposition. I'm not completely convinced that one can simply apply
> modal logic to the set of all descriptions in this way, but it does
> have some plausibility.


I think small. Attempting to reason about entire "worlds" with huge
amounts of state (put various ways: long description, high logical
depth, high algorithmic complexity, big) is not useful...to me.

So I use "A" and "B" for two possible worlds. The outcome of a coin
toss, for example. The click of a geiger counter or not. Schrodinger's
cat alive, or dead. These states are, as Russell notes, propositions. Or
sets of propositions (or huge sets of propositions, for entire worlds).

I prefer at this time to ignore the implied complexity of an entire
world and just call them "A" and "B." Two outcomes, two branches in the
MWI sense, two possible worlds, two points in a lattice, two points in a
pre-ordered set (see below), two points in a partially-ordered set
(poset, see below).

I picked "WWIII happens this year" (or doesn't) to illustrate the
general point that modal logic applies, that classical logic cannot
apply to find and implication from A to B or B to A, as they represent
contradictory to each other worlds. I didn't mean it to imply that modal
logic is going to somehow tell us how likely such a world is, or what
life might be like in either of those worlds, etc. I just wanted to make
"A" and "B" more tangible to MWI sorts of folks.

(Goldblatt, in his book "Topoi," uses "Fermat's last theorem is true or
false" as the two contradictory possible worlds. At the time he wrote
his book, 1979, the truth or falsity of FLT was unknown. These were two
possible worlds, visualizable by mathematicians and others, each having
a kind of tangible reality. In fact, something that was shown to be
equivalent to FLT was the "Taniyama-Shimura Conjecture" about some
curious relationships between elliptic functions and modular forms. And
for many years before Taniyama was proved, papers would start with this
perfect example of modal logic: "Assuming Taniyama-Shimura is true,
then...." People _believed_ T-S was probably true, but it hadn't been
proved formally until Andrew Wiles did so, thus proving Fermat's Last
Theorem as almost a trivial afternote.)

A series of moments or events is drawn as a graph, with vertices linked
with edges, with some events clearly coming "after" others, because they
are causally-dependent on "earlier" events. But also some events
_independent_ of other events, with no known (and perhaps no _possible_
causal relationship, e.g., events outside each other's light cones,
i.e., spacelike intervals).

This graph, this set of vertices and edges, is a "per-ordered" set. More
than just a set, any category with the property that between any two
objects "p" and "q" there is AT MOST one arrow "p --> q" is said to be
"pre-ordered." There are lots of examples of this: the integers (and the
real numbers) are pre-ordered under the operation "greater than or equal
to" or "less than or equal to." Moments in time are pre-ordered.
Containment of sets is pre-ordered.

Following Goldblatt, I'll call the arrow "R." So the "p --> q" example
above is written as "pRq."

Here are some properties of pre-orders:

1. Reflexive: for every p, pRp.

Example: For every p, p implies p.

Example: For every real number, that real number is less than or equal
(LTE) to itself. And also greater than or equal (GTE) to itself.

Example: For every event, that event occurs before or at the same time
as that event.

(Here I'm using time, because time is the most interesting pre-order for
our discussion of worlds, MWI, causality, etc.)

Example: Every set contains itself (where containment is "contains or is
equal to"). (This may say like a tautological definition. Draw pictures
of sets as blobs. The motivation for this example will become clearer
with later properties.)

2. Transitive: Whenever pRq and qRs, then pRs.

Example: If p implies q and q implies s, then p implies s.

Example: if p is less than or equal (LTE) to q and q is LTE to s, then
p is LTE to s.

Example: if event A happens before (or at the same time as) event B and
event B happens before (or at the same times as) event C, then even A
happens before (or at the same time as) event C.

Example: (short version--you know the drill by now): If A contains B and
B contains C, then A contains C.

Discussion: These are all simple points to make. Obvious even. But they
tell us some important things about the ontological structure of many
familiar things. I encourage anyone not familiar with these ideas to
think about the points and think about how many things around us are
pre-ordered.

If a pre-order has an additional property we call it a partial-order:

3. Anitsymmetric: Whenever pRq and qRp, then p = q.

Example: If p implies q and q implies p, then p and q are the same
thing. (Equality, isomorphism, identity.)

Example: If p is LTE q and q is LTE p, then p = q.

Example: the time example is left as an exercise!

Example: ditto for set containment.

A set with a partial-order is called a "poset." These feature
prominently in all sorts of areas. For our purposes, posets are
essentially what _time_ is all about.

In addition, we can define things like "meets" and "joins" and the
result is a _lattice_, studied extensively by Dedekind, Von Neumann, and
Garrett Birkhoff. Lattices look exactly like lattices, or trellises. Two
vertices have at most one link (arrow, R, etc.) between them, though
many links may point to any particular vertex.

In this view, it doesn't really matter (at this level) whether the
vertices are the outcomes of a coin toss or entire worlds.

This was the sense in which I was using "WWIII happens this year" or
"WWIII doesn't happen this year" for my MWI-type example.

The essential point is that the natural logic of such posets is not
necessarily Boolean. There are several names for this "not necessarily
Boolean" aspect, depending on the interest of the researcher or writer:

* He may call it "non-Aristotelean logic," as even Aristotle was said to
have realized that a statement like "The fleet at Carthage will either
be sunk tomorrow or it won't be" is not always meaningful, and that
attempting to force future or time-varying truth into the Stoic model of
"A or not-A" is not the most useful thing to do.

* He may call it "Intuitionist" or "Constructivist," asking that
mathematical proofs be _constructive_ in nature rather than using proof
by contradiction. ("Assume the proposition not to be true, then we see
that,...then, and this is a contradiction, therefore the proposition
must be true.") This turns out to be fairly important when proofs use
the so-called "Axiom of Choice." (Which is equivalent to many other
axioms and theorems.) Some important results of the past 40 years have
come about by challenging the role of the Axiom of Choice. (BTW, as an
aside which may be of interest to some list members, John Nash used the
Axiom of Choice to prove that certain solutions to multi-party protocols
must exist, but he did not give a constructive proof of what those
solutions are.)

* He may call it a "Heyting algebra," as opposed to a Boolean algebra.
I've discussed Heyting algebras and logic here in the past, and I refer
readers to the Web for many articles of varying levels of assumed
background.

* He may call it "possible worlds semantics," after the work by the
logician Saul Kripke on the logic implicit in possible worlds.

* And most generally of all, at this time, he may call it topos theory.

Does it relate specifically to the speculations of Max Tegmark, Greg
Egan, and others on "all mathematics" and "all topologies" models?

I can't say for sure, but it's the direction *I* am taking. As I said, I
think small. I can't "reason about" entire worlds and draw meaningful
conclusions. I _think_ this kind of thinking about posets, lattices, and
toposes is the right way to think about systems with varying choices,
even varying mathematics (*).

* Because toposes are essentially mathematical universes in which
various bits and pieces of mathematics can be assumed. A topos in which
Euclid's Fifth Postulate is true, and many in which it is not. A topos
where all functions are differentiable. A topos in which the Axiom of
Choice is assumed--and ones where it is not assumed. In other words, as
all of the major thinkers have realized over the past 30 years, topos
theory is the natural theory of possible worlds.

So, I think small. I think about flips of coins, about simple lattices
and simple posets.

These are not the Universe, let alone the Multiverse, but it seems clear
to me we cannot reason about the entire Universe or Multiverse unless we
can reason about very simple sub-parts of it.

In any case, it's my particular interest at this time.

I hope this helps clarify things a bit.

--Tim May
(.sig for Everything list background)
Corralitos, CA. Born in 1951. Retired from Intel in 1986.
Current main interest: category and topos theory, math, quantum reality,
cosmology.
Background: physics, Intel, crypto, Cypherpunks
Received on Tue Aug 13 2002 - 10:18:08 PDT