problem set 4 (modal definability and its limits)

1. A relation \(R\) is functional on \(W\) iff for all \(w, u, v \in W\), if \(Rwu\) and \(Rwv\), then \(u = v\). Justify the claims below.

   1. \(\Diamond p \to \Box p\) defines the class of functional frames.

   2. \(p \to \Diamond p\) defines the class of reflexive frames.

2. Let \(\textsf{Id}\) be the class of identity frames \((W, R)\) with \(R = \{(u, v)\in W \times W: u = v\}\).

   1. \((p \to \Diamond p) \wedge (\Diamond p \to \Box p)\) defines \(\textsf{Id}\).

      Observe that a frame \((W, R)\) is in \(\textsf{Id}\) iff \(R\) is reflexive and functional on \(W\).

   2. \(p \leftrightarrow \Diamond p\) defines \(\textsf{Id}\).

   3. The formulas in 2.1 and 2.2 are not equivalent. For each formula, find a model and a world where it is true and the other is false. Explain why this is consistent with 2.1 and 2.2. (Could either of your models be based on an identity frame?)

3. Let \(\textsf{Diff}\) be the class of difference frames \((W, R)\) with \(R = \{(u, v) \in W \times W: u \neq v\}\).

   1. Provide an argument for the undefinability of \(\textsf{Diff}\) by a set of modal formulas.

      Compare the two-world frame in which each world sees only the other with the one-world frame in which the world sees itself.

   2. Provide an argument for the undefinability by a set of modal formulas of the class of non-identity frames by which we mean the complement of \(\textsf{Id}\).

   3. Conclude that modal definability is not closed under complement. Which earlier parts did you use?