Question concerning satisfiability in a certain Kripke model

133 Views Asked by At

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?

1

There are 1 best solutions below

1
On BEST ANSWER

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.