Re: Kripke semantics

From: Marchal <>
Date: Tue Apr 10 10:27:41 2001

George Levy wrote:

>I am not sure if you gave a definition of reflexive,
>transitive and symmetric.

I have. ( :-)

But there is no problem with repetition.

The real problem is with the absence of pictures!!!!

Please take a pencil and try to translate everything I say
with little drawings.

A relation R defined on a set W is just a subset of W X W.

 W = {1, 2, 3}

 R = { (1,1) (1,2) (2,2) (3,3)}

In this exemple R is said to be reflexive because for each x in W we have
xRx (we write aRb for saying that (a,b) is in the relation R)
indeed 1R1, 2R2, 3R3.

In your drawing just draw three points and represent the relation
by arrows between the points. Of course the relation is reflexive means
that for each points there is an arrow from the point to itself.


 W = {John, Paul, Sophie}

 R = the relation "is the father", and I tell you that John is the father
of Paul, and that Paul is the father of Sophie.

R is of course not reflexive (because nobody is its own father).

3) W = {John, Paul, Sophie}
  R is "as tall as"

then R is reflexive (for all x we have xRx : John is as tall as John, etc.)
R is also symmetric (which means for all x and y xRy entails yRx), because
if x is as tall as y, then y is as tall as x.
R is transitive (which means: xRy and yRz entails xRz).
Order (bigger than) and equivalence (like as tall as) are typically transitive

>> 1. (W,R) respects []p -> p iff (W,R) is reflexive,

>I find it easier to comprehend these theorems if I state them in English:
>1) If p is true in all worlds in set R, then p is true in world A.
>This is true if A belongs to set R. (we could use a Venn diagram
>to prove this) ...... OK


You should not drink when reading the post. Where does the "A" come
from. Also: the set is W, and R is a relation on W.

You translate []p by p is true in all worlds. But that is Leibniz
semantics. In Kripke semantics []p is true in the precise world w
if p is true in all world accessible from w.
In math notation: []p is true in w if p is true for all x such that wRx.

Then the proof that

          (W,R) respects []p -> p iff (W,R) is reflexive,

is hardly shorter than the one I give <<let me quote myself:

Because of the "iff" we must prove two things.

we must prove a) if R is reflexive then (W,R) respects []p -> p,
and we must prove b) if (W,R) respects []p -> p then R is reflexive.

Let us prove a).
To prove that "if A then B", a traditional way consists in supposing
that we have A and not B, and showing that this leads to a
contradiction. (BTW you can verify that ((A & -B) -> FALSE) <-> (A->B))
is a tautology).
So, let us suppose that R is reflexive and that (W,R) does not
respect []p -> p.
To say that (W,R) does not respect []p -> p means that there is at
least one world w in which []p -> p is false. Remember that worlds
obeys classical logic, so that if []p -> p is false at w, it means
that []p is true at w and p is false at w (and -p is true at w).
But (by Kripke semantics) if []p is true at w, it means p is true
at every world accessible from w. But R is reflexive, so we have wRw.
So p and -p are true at w. But then w does not obey to classical logic.

Let us prove b), that is: if (W,R) respects []p -> p then R is
Suppose (W,R) respects []p -> p and that R is not reflexive.
And let us search a contradiction from that.
If R is not reflexive, it means that there is a world w in W such that
we don't have wRw. Let us build a model on that frame by defining
a valuation V such that V(p) = FALSE in w, and V(p) = TRUE on all
world accessible from w (if there is any()).
By Kripke semantics we have []p true in w. So now we have both
[]p and -p true at w. But we have suppose that (W,R) respects
[]p -> p, so []p -> p is true at w, so p is true at w (because []p
has been shown true at w, and w obeys classical logic). But then
again p and -p are true at w. Contradiction. End of self-quoting>>

Make drawings, you will help yourself. Verify the theorem for little
reflexive frame like (W, R), with W having just two elements (worlds) and
R a simple reflexive relation you invent (like just xRx for the x in W).

>> And, just because you promise me a prize for deriving SE from
>> the "psychology of machine" I tell you that I have decided
>> to call the modal formula (the one for the symmetrical frame):
>> p->[]<>p,
>> the little abstract Schroedinger Equation (LASE),
>In English:
>If p is true in one world then in the set of all worlds, there is at least on
>world in which p is true....OK, isn't that obvious?

It is obvious *in Leibniz semantics*. In kripke semantics it is "obvious"
only for the symmetric frame. Try to build a little non symetric model which
does not validate the formula.

>But to connect this to SE,
>where is the uncertainty? And in which world is the observer located?

Until now the word "world" means only that it is an element of a frame W,
by definition. I was anticipating for motivation. The relation between
p->[]<>p and SE will be based on quantum logic.

>> as I have called before the (godel-like) formula
>> <>p -> -[]<>p
>> the first theorem of machine's psychology. (FTMP)
>> And our goal is to find a natural bridge from FTMP to LASE.

>In English:
>if there is at least one world where p is true, then it is false that in
>the set
>of all worlds there is at least one world where p is true.

Your translation in english is false. You still mixt Leibniz
semantics and Kripke. Be careful.

>This statement (<>p -> -[]<>p) seems inconsistent.

It is inconsistent in Leibniz semantics.

>> When the box []p is interpreted in english as provable(p),
>You are saying that "p is true in all worlds" is identical to "p is
>provable." You have lost me....

Although you are a relativist you keep thinking in Leibniz
semantics. You are still victim off 2OOO years of Aristotelian
brainwashing :-)
[]p does not mean that p is true in all worlds. (that is Leibniz
With Kripke []p has no absolute meaning at all.
With Kripke, []p is defined only relatively to a world.
[]p is true at world w means p is true in all worlds
accessible from w. (i.e. p is true at all z such that wRz).

So there is as much Kripke semantics than there is relation
of accessibility. And that is nice because it gives independant
semantics for most interesting modal formula.
Don't hesitate to read and reread the preceding post.

>Again thanks for this course in logic

I hope I will not give you too much work. You can find some drawing
in my french thesis. For exemple ideal frame can be
found page 64. The Kripke semantics of the Aristotelian square, page
62, should help you.

>Great adding an unprovable statement to a set of axiom is OK. But how do
>you know it is not provable until you actually attempt to prove it... and
>how long will you attempt to do so?

I will come back on this latter.

>Consistency ("logical thinking") is certainly a necessary condition for
>consciousness ("I think" a la Descartes)
>> A more psychological reading of that formula is, by identifying
>> (audaciously perhaps) consistency with consciousness (or awakeness)
>> you get "if I am conscious then I cannot prove it.
>but consistency is not a sufficient condition for consciousness. Or is it?
>What else would be required?

Consistency is indeed not a sufficient condition for consciousness.
What is required is some form of (automatic) anticipation of that
consistency. But that will not be relevant for the derivation of SE.

>Yes I am.... but as the saying goes "l'appetit vient en mangeant." We
>shall see.

We can take holiday at any moment, and even discussed other more
informal point, and then come back to the math.

>Forgive me for not being too prompt....

Take your time. Read the post carefully.

>Responding to your posts is not
>simply a matter of making a few cute remarks....

I'm afraid y're right. This is because we try to go
for being more technical. BTW I am astonished that
people are not attacking us on that way to proceed.
I was expecting remarks like "logic cannot be used
for solving philosophical problems, nor for solving
physical problems, etc.".
I'm used to such kind of arguments ...

>We are certainly going in
>the right direction....

I hope so.

>I think that the basic ideas are probably very

I'm not so sure. Do you know Hilbert Space, or Linear Space. We will
need them for quantum logic (which will explains why I call
p->[]<>p the little Schroedinger equation).
Godel's theorem will also be needed (as you know). It is not
difficult, but then to say it is easy would be an exageration

>the hard part is to communicate them.

... especially without drawing facilities. I believe that those
who will just add a little pen to the e-mailing will make
lot of money !

You know, when I teach modal logic, I do drawings and drawings
and drawings. I have even invented a sort of slide-comics technics
for the presentation of Kripke semantics. Let us try to be


PS Those who understands my thesis AND are willing to study the
formidable paper by J.P. Rawling and S.A. Selesnick : "Orthologic
and Quantum Logic: Models and Computational Elements" should be
able to explain where does quantum computation come from, and why
any modest lobian machine can discover their necessary existence
by pure introspection.
This paper could motivate you for quantum logic.
The paper is in "Journal of the ACM, july 2000, Vol. 47, N4,
page 721-751". (Not really easy, for sure).
Received on Tue Apr 10 2001 - 10:27:41 PDT

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