Re: modal logic and possible worlds

From: Bruno Marchal <marchal.domain.name.hidden>
Date: Fri, 16 Aug 2002 15:23:43 +0200

At 10:29 -0700 13/08/2002, Wei Dai wrote:

>Does it mean anything that S4 and intuitionistic propositional
>calculus (= 0-order intutionistic logic, right?) ...


Right.



>.... have the same kind of models, or is
>it just a coincidence? I guess Tim is saying that it does mean something,
>but I don't understand what.




I almost missed this fair question. It is not a coincidence.
I choose S4 for not frightening Tim with irreflexive or non
transitive accessibility relation :-).


Kripke knew a 1933 result(*) by Godel according to which, (with IL
standing for Intuitionist logic):

   Theorem: S4 proves T(A) if and only if IL proves A

where T is a function from the propositional language to the modal
propositional logic given by

  T(A) = A if A is a propositional letter = A belongs to {p, q, r ...}
  T(-A) = []-T(A)
  T(A->B) = [](T(A) -> T(B)

Kripke first discovered his semantics for general normal modal logic.
By Godel 1933 this provides him (and us!) the "S4" possible world
semantics of IL.
Note that Beth developed a more awkward but similar semantics before.

The "world" of the S4 models (= of the IL) models are sometimes
interpreted as *state of knowledge*. This fit well with the fact
that the S4 logic in my thesis describes a pure first person knower.
(But I get S4Grz, its antisymmetrical extension, good for subjective
irreversible time).

The following remarks may help.


S4, which is a *classical* extension of CL
(Classical Logic), is capable of simulating IL. This is not an argument
that CL is better, for Godel (again) found that IL can simulate CL:
basically IL proves (- - A) when CL proves A. It's a key of IL that
IL does not prove (- - A) -> A. (but IL proves A -> (- - A))

Like CL admits an algebraic semantics in term of Boolean Algebra, ...

parenthesis:
(where the propositions A, B, C ... are interpreted by subsets of
a set W, the "and" by intersection, the "or" by union, the "-" by the
complementary, the constant f by the empty set and the constant t by
the whole set W. You can even (in our modal context interpret the element
of W as worlds verifying the formula, for example a tautology being
true in all world you see a tautology, like the constant t, is
interpreted by W). For example [A union -A] = W, i.e the exclude
middle principle is universally valid, in CL.
end of parenthesis

... IL admits a topological interpretation, where the propositions
are interpreted by open sets in a topological space. The "and" by
intersection, the "or" by union, the not by ... the interior of
the complementary. For exemple take as topological space the real
line. Interpret A by the open set (-infinity 0) then -A is (O infinity)
you see [A union -A] does not give the whole space, and this
shows the exclude middle is not universally valid, in IL.

Quantum Logic (QL) like IL, is a syntactically weaker logic than CL.
(And thus IL and QL are semantically richer). Algebraic semantics
for QL is given by the lattice of subspace of vector spaces (or Hilbert
spaces).

A good shape to remember is the following drawing (Arrows from bottom
to up = "syntactically extend":


                   S4 B
                    \ /
                     \ /
                      CL
                     / \
                    / \
                  IL QL

S4 gives a classical representation of IL, and B gives (thanks to
Goldblatt result) classical representation of QL.


(*) Godel was so famous that he did'nt need no more to prove his
affirmation/conjecture. It is a two pages paper without proof.
  The Godel's "result" will be proved by McKinsey and Tarski in 1948.


Bruno
Received on Fri Aug 16 2002 - 06:32:44 PDT