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?) ...

## Advertising

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