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 n 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 n 32 > then qr(α(x)) ≥ n + 1. n 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 3.2.2@blue 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. 1