My question concerns the exercise on p.77 of Boolos, Logic of Provability:

True or false: if $A$ is satisfiable in some finite transitive and irreflexive [FIT] model and contains at most one sentence letter, then $A$ is satisfiable in some FIT model in which for all $w_0$, $w_1$, ..., $w_n$ in $W$, not: $w_0Rw_1R...Rw_n$.

Here, $A$ is some modal sentence, $W$ is the domain of the model, $n$ is the degree of $A$, i.e., the highest number of nested boxes in $A$, and $R$ is the accessibility relation.

My provisional answer is True: If $ M=<W, R, V>$ is FIT and $M, w \vDash A$, where $w \in W$, define $N=<X, S, U>$ as follows:

$X= \{x \in W : \neg \exists i>n wR^ix\}$ (So $X$ is obtained from $W$ by removing all members accessible from $w$ via an "$R$-chain" of length $>n$.)

$S= \{<x, y> : x, y \in X, xRy\}$

$xUp$ iff $xVp$ ($p$ is any sentence letter).

$N$ meets the conditions for the "continuity theorem" (p. 72), therefore $N, w \vDash A$. Moreover $N$ is FIT, and by design for all $w_0$, $w_1$, ..., $w_n$ in $X$, not: $w_0Rw_1R...Rw_n$.

The reason I have doubt about this answer is that I did not use the fact that $A$ has at most one sentence letter; I don't see why this matters. Does it?


You removed all R-chains longer than $n$, but you were required to remove R-chains of length $n$. (Or am I missing something from your argumentation?)

Regarding the exercise I'd say this (might be a spoiler so I hid it):

The answer is false. Counterexample: $\Diamond \top$ (or $\Diamond \neg\bot$). It's satisfied on the following FIT model at $w_0$: $w_0 \rightarrow w_1$. We are supposed to be able to construct a model without $xRy$, for $x, y \in W$. But by definition of $\Diamond$, this is impossible.

  • $\begingroup$ Yes, I realized this not long after posting. It's trivially false, although trivially true if you accept my misunderstanding of what's asked. $\endgroup$ – rj7k8 Sep 16 '13 at 14:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.