Transcript Possible World Semantics for Modal Logic

Possible World Semantics
for Modal Logic
Intermediate Logic
April 14
Kripke Models
for Propositional Modal Logic
• A model <W,R,h> consists of:
– W: a set of worlds
– R  W  W: an accessibility relationship
• W and R together is called a frame
– h: W  P  {true, false}: a propositional truthassignment function for each world
• Thus, in a Kripke model, statements are true
relative to whichever world they are being
evaluated in.
Semantics
• Propositional semantics is exactly as one would
think, i.e:
– hw(  ) = true iff hw() = true and hw() = true
– Etc.
• Modal semantics is as follows:
– hw(□) = true iff for all w’ such that wRw’: hw’() = true
– hw(◊) = true iff there exists a w’ such that wRw’ and
hw’() = true
• That’s it!
Tautology, Consequence, etc.
• A statement  is called a (modal) tautology
iff for any W, R, and h: hw() = true for all
wW
• A statement  is a (modal) consequence
of a statement  iff for any W, R, and h: if
hw() = true then hw() = true for all wW
• Etc.
Characteristic Axioms
• Systems T, S4, and S5 can be defined
using ‘characteristic axioms’:
– T: □p  p
– S4: □p  □□p
– S5: ◊p  □◊p
• On the next slides we will see that these
axioms correspond to certain properties of
the accessibility relationship R.
T
• T is defined using the axiom □p  p. In
other words, in system T the statement □p
 p is considered a (modal) tautology.
• But, without any restrictions on R, we can
easily build a model that shows that □p 
p is not a tautology:
In w1, □p is true,
but p is false
p
w1
T (cont’d)
• On the previous slide we were able to construct a
countermodel for the claim □p  p using a non-reflexive
accessibility relationship R. So, it is not true that hw(□p 
p) = true for any W, R, and h and wW: if we don’t know
that R is reflexive, we can’t be certain of the principle.
Reflexivity of R is therefore a necessary condition for □p
 p to always hold true.
• In fact, reflexivity is sufficient: hw(□p  p) = true for any
W, reflexive R, h and wW
• Proof by contradiction: Suppose hw(□p  p) = false for
some W, reflexive R, h and wW. Then hw(□p) = true
and hw(p) = false. But, since R is reflexive, wRw. So,
since hw(□p) = true, then by the semantics of □, it must
also be the case that hw(p)=true. Contradiction.
S4
• The characteristic axiom for S4 is □p 
□□p. Again, however, this is not a
tautology:
p
p
p
w1
w2
w3
In w1, □p is true,
but □□p is false
S4 (cont’d)
• However, as long as R is transitive, then □p  □□p will
always hold.
• Proof by contradiction: Suppose there is a world w1 such
that hw1(□p  □□p) = false. Then hw1(□p) = true and
hw1(□□p) = false. Since hw1(□□p) = false, there must be a
world w2 such that w1Rw2 and hw2(□p) = false. So there
must also be a world w3 such that w2Rw3 and hw3(p) =
false. But since R is transitive, we must have w1Rw3. And
since hw1(□p) = true, we know that hw3(p) = true.
Contradiction.
• Please note that S4 adds the axiom □p  □□p to the
axiom □p  p. Hence, S4 assumes the accessibility
relationship to be transitive and reflexive.
S5
• The characteristic formula of S5 is ◊p 
□◊p. Again, this gets added to the axioms
of T and S4. What does this do to R?
• First, let’s see how the characteristic
axiom of S5 is not a tautology in S4:
In w1, ◊p is true,
but □◊p is false
p
p
w1
w2
S5 (cont’d)
• Notice that R on the previous slide is
reflexive and transitive, but not symmetric.
Hence, if R is not symmetric, the
characteristic formula does not hold.
• What if R is symmetric? Well, symmetry
alone is not enough either:
p
p
p
w2
w1
w3
In w1, ◊p is true,
but □◊p is false
S5 (cont’d)
• In fact, even symmetry plus reflexivity is
not enough:
p
p
p
w2
w1
w3
In w1, ◊p is true,
but □◊p is false
S5 (cont’d)
• However, symmetry plus transitivity will do the job.
• Proof by contradiction: Suppose hw1(◊p  □◊p) = false.
Then hw1(◊p) = true and hw1(□◊p) = false. Since hw1(□◊p)
= false, there must be a world w2 such that w1Rw2 and
hw2(◊p) = false. And since hw1(◊p) = true, there must be a
world w3 such that w1Rw3 and hw3(p) = true. Now, since
R is symmetrical, we must have w2Rw1, and by
transitivity, we must then have w2Rw3. But since hw2(◊p)
= false, we must have hw3(p) = false. Contradiction.
• Of course, S5 adds the axiom ◊p  □◊p to the axioms of
T and S4, requiring R to be reflexive, symmetrical, and
transitive.
HW 18
• Use possible world semantics to see
whether ◊(p  ◊q)  (□◊p  ◊□q) is a
tautology in T.
• In other words, try and find a model and a
world in that model such that this
statement is false in that world, or prove
that no such model can be constructed.