Homework set 4 – Advanced Modal Logic

Homework set 4 – Advanced Modal Logic
Due April 29th
In the following we only consider the basic modal logic.
Exercise 1 (2 points) Find a class K of pointed models such that K is definable by a set of modal
formulas but K is not modally definable by any set of modal formulas?
Exercise 2 (2 point) Modal logic formulas can be translated to equivalent first-order formulas
(over pointed models). However first-order formulas can be more succinct than modal formulas.
Let 3n > be the abbreviation of 3
· · 3} >.
| ·{z
1. Try to give a general form of first-order formulas αn (x) such that αn (x) is equivalent to 32 >
and qr(αn (x)) = n + 1.
2. Prove or disprove the following claim: for any first-order formula α(x), if α(x) is equivalent to
32 > then qr(α(x)) ≥ n + 1.
Exercise 3 (2 point) We say a modal formula φ defines a pointed model M, s if for all pointed
model N , t: N , t φ ⇐⇒ M, s ↔ N , t. Now suppose |P| is finite, can you then define every
finite transitive pointed model within the class of transitive pointed models? (and why?)
Exercise 4 (1 point) A Kripke frame with a binary relation R is said to be conversely euclidean if
it satisfies the first-order formula ∀x∀y(∃z(xRz∧yRz) → xRy). Show that the class of conversely
euclidean frames is not modally definable.
Exercise 5 (1 point) Which class of frames is defined by the modal formula (p ∧ 2p) → 3p?
Prove that your answer is indeed correct.
Exercise 6 (2 point Exercise [email protected] book) Show that Grzegorczyk’s formula 2(2(p → 2p) →
p) → p defines the class of frames which are reflexive, transitive and there is no infinite path
x0 , x1 . . . such that xi 6= xi+1 for all i.