Re: Kripke semantics

From: George Levy <>
Date: Sun, 08 Apr 2001 13:52:45 -0700

Marchal wrote:

> George Levy wrote:
> >My binder is getting fatter but I am catching up...

but it is getting fatter....

I feel like Zeno... Or maybe like Sisyphus....:-)

> You are welcome.


> Theorems:
> 1. (W,R) respects []p -> p iff (W,R) is reflexive,
> 2. (W,R) respects []p -> [][]p iff (W,R) is transitive,
> 3. (W,R) respects p -> []<>p iff (W,R) is symmetric,
> 4. All frames respect [](p->q) -> ([]p -> []q).

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

> Let us prove 1. and 4. (I leave 2. and 3. as exercice)

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

2) if p is true in all worlds in set T then p is true in all worlds in set T in
all worlds in set T (????) There seems to be two levels of "in all worlds"
Slightly confusing
I don't get this one.... in English.

3) If p is true in world A then in all worlds in set R there is at least one
world B where p is true. This statement is true if A =B........ OK

4) If the relation "p implies q" is true in all worlds in set S, then, if p is
true in all world in S then q is true in all world in S... OK

> Proof of 1.
> 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.
> Contradiction.
> Let us prove b), that is: if (W,R) respects []p -> p then R is
> reflexive.
> 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.
> OK? For theorems 2. and 3. you should perhaps find the proofs
> yourself. It is almost more easy to find the proof than to read
> someone else proof. The only difficulty is in the case b) and
> consists in finding the valuation which leads to the contradiction.
> Hint: put V(p) = FALSE in w, and V(p) = TRUE on all
> world accessible from w; or, for 3. put V(p) = TRUE in w, and
> V(p) = FALSE on all world accessible from w.
> () Hey! but what if w is a cul-de-sac or terminal world?
> Then []p, or even []False is always true in w. This follows
> easily from classical logic: []p is true at w because
> "(it exists x such that wRx) entails p true at x", this
> last sentence is true because wRx is always false for a
> terminal world, and "false implies whatever you want" is
> always true.
> Another way to swallow this tricky point is to remember
> that []p is -<>-p, but -<>(what you want) must be
> automatically true in a terminal world, by simple
> Kripke semantics for <>.
> Terminal world are are disquieting: everything is necessary
> and nothing is possible in a terminal world.
> Proof of 4.
> We want to show that [](p->q) -> ([]p -> []q) is respected in all
> frames. This means [](p->q) -> ([]p -> []q) is true in all world
> in all model in all frame!
> It will be easier to show that the theorem holds for the equivalent
> sentence ([](p->q) & []p) -> []q
> Do you see the equivalence? It is just propositional logic:
> A -> (B -> C) <-> (A & B) -> C
> Suppose now that ([](p->q) & []p) is true in some world w.
> We must show []q is true in w.
> If w is a terminal world then []q is automatically true as
> we have seen above.
> If w is not a terminal world, then there are worlds x, z, y ...
> with wRx, wRz, wRy, ...
> The fact that ([](p->q) & []p) is true at w entails that
> both [](p->q) and []p are true at w. But this, by Kripke
> semantics, entails that both (p->q) and p are true in
> the accessible worlds x, z, y, ..., and so, q is true
> in all those worlds (all world obeys classical logics and are
> thus closed for modus ponens). But if q is true in all
> accessible worlds from w, then, by Kripke again, []q must be
> true in w.
> * * *
> In fact some other frames will play an important role, so let us
> introduce them now. (The definition which follows are somehow
> less standart).
> I will say, by definition, that a world is transitory iff it is
> not terminal.
> A frame (W,R) will be said ideal if all worlds in W are transitory.
> (there is simply no cul-de-sac worlds in an ideal frame).
> A frame will be said realist if there is a terminal world accessible
> from any transitory world of that frame.
> (You can "die" at every world in a realist frame, as you are
> "immortal" in an ideal frame).
> The corresponding theorems (exercice) are
> 5. (W,R) respects []p -> <>p iff (W,R) is ideal,
> 6. (W,R) respects <>p -> -[]<>p iff (W,R) is realist,
> Do you have recognize <>p -> -[]<>p ?
> Yes. It is our modal form of Godel theorem (with TRUE instead of p).
> More will be said.

> My next post will anticipate toward the end of my proof to glimpse
> the "quasi-appearance of Hilbert Space" when we explain the UDA TE
> to the guardian angel of the sound machine.
> 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? But to connect this to SE,
where is the uncertainty? And in which world is the observer located?

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

This statement seems inconsistent. Where does the choice between completeness
and consistency come into play?

> I must say that I have believe for a quite long time that this was
> impossible. But then when you take the definition of knowledge
> belief, observation/perception in Plato's thaetetus, then the
> aritmetical translation of the UDA TE will lead us directly toward
> the solution.
> And so you will be obliged to give me the prize (at least
> a little abstract price!).
> Infinite thanks for your patience. All of you.
> Bruno

> I hope your binder will not explode.

No the binder is fine.... my head however is getting swollen :-)

Again thanks for this course in logic

Received on Sun Apr 08 2001 - 13:58:35 PDT

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