6
$\begingroup$

First of all, the modal logic we are working with in this case is the basic one: that is, all propositional formulas, plus formulas of the form $\Diamond\phi$, where $\phi$ is any modal formula (we define $\Box\phi$ as $\neg\Diamond\neg\phi$).

Let's define satisfaction. For that, we must define models for modal logic. Given $M=(F,V),F=(W,R)$ and a set, $\Phi$, we say $M$ is a model for the modal logic based on $\Phi$ if $W$ is a set, $R\subseteq W\times W$, and $V$ is a function from $\Phi$ to $2^{W}$, that is, it maps each element of $\Phi$ to a subset of $W$. From this, we also define (among other things) that $\Phi$ is the set of propositional letters of the logic, $F$ is a frame for the same modal logic and $V$ is a valuation on that frame.

Now we can proceed with the satisfaction definition. Given $w\in W$, we say $M,w\Vdash \phi$, that is, $M$ satisfies $\phi$ in $w$, if the following is true: $\phi=p$, where $p\in \Phi$ and $w\in V(p)$, or $\phi=\neg \psi$ and $M,w\nVdash \psi$, or $\phi=\psi\land\chi$ and $M,w\Vdash\psi$ and $M,w\Vdash\chi$, or $\phi=\Diamond \psi$ and there exists $v\in W$ such that $Rwv$ and $M,v\Vdash\psi$.

Then, we can define validity. We say that $F\Vdash\phi$, that is, $\phi$ is valid in $F=(W,R)$, if, for all $w\in W$ and all valuations $V$ on $F$, $(F,V),w$ satisfies $\phi$.

A modal formula $\phi$ defines a class of frames $\textrm{F}$ if, for every frame $F$, $F$ is in $\textrm{F}$ if and only if $F\Vdash\phi$, that is, $\phi$ is valid in $F$. A similar definition applies to first-order logic, obviously replacing $\Vdash$ with $\vDash$. We say that a modal formula $\phi$ defines a first-order condition $\psi$ if they define exactly the same class of frames.

As part of this question, we were already given a hint on how to proceed; it is known that, in the frame $(\{u\}\cup u \cup \mathbb{N}, \ni)$, where $u$ is a non-principal ultrafilter on $\mathbb{N}$, $\Diamond\Box p \rightarrow \Diamond (\Box (p\land q) \lor \Box(p\land\neg q))$ is valid, and the original question suggests that you should establish that in any countable structure elementarily equivalent to the given frame the formula is not in fact valid.

The proof of the first fact (formula is valid on frame) does give out some intuition on how to proceed: The crucial step of said proof relies on any subset of $\mathbb{N}$ (or its complement) being a member of $u$ and that $u$ is closed under intersection, but we can expect a countable structure to be missing several of these elements, allowing the formula to be falsified.

Unfortunately, i have not been able to convert said intuition into an actual proof. Is there a way to do so? Or, alternatively, is there a different approach to this question?

  • 0
    Ugh. I just noticed, the silly iPhone replaced `provability` by `probability`.2012-12-28

1 Answers 1

3

Check that in your frame you can describe in first order language that there are three types elements: Those that do not contain any elements (first type), those that contain elements that do not contain elements (second type) and a unique element that contains all the elements of the second type (third type).

Next check that via first order language you can make sure that the elements of the first type are infinite many, that all the elements of the second type contain infinite many elements and are closed under finite unions and intersections.

Now take a frame $(W,R)$ (I will assume w.l.o.g. that $R$ is ''$\ni$'' to improve the notation a bit) elementarily equivalent to your original frame and assume that it is countable. Let $A$ be the set of the countable elements of the first type and let $\{w_1,\ldots,w_n,\ldots\}$ be the set of the elements of the second type. Then I will construct a valuation such that the element of the third type falsifies the formula.

To do this pick $a_1,b_1\in w_1\cap A$ and let $a_1\in V(q)$ and $b_1\notin V(q)$. Let's define $A_1=A\setminus\{a_1,b_1\}$. Continue inductively: Assume you have a cofinite set $A_k$ and you have defined the valuation for the elements of $A\setminus A_k$ such that for every $m\leq k$ there are some $a,b\in A\setminus A_k$ such that $a,b\in w_m$ and $a\in V(q)$ while $b\notin V(q)$. Then since $w_{k+1}$ is infinite (by elementary equivalence) we have that $w_{k+1}\cap A_k$ is infinite. Hence we can pick $a_{k+1},b_{k+1}\in w_{k+1}\cap A_k$ and let $a_{k+1}\in V(q)$ while $b_{k+1}\notin V(q)$ and let $A_{k+1}=A_k\setminus\{a_{k+1},b_{k+1}\}$. Also let $V(p)=W$ and for define $V(q)$ arbitrarily elsewhere (after the inductive construction).

If $w$ is the unique element of the third type in your model you have that $(W,R,V),w\Vdash\diamondsuit\square p$ but $(W,R,V),w\nVdash\diamondsuit(\square(p\land \lnot q)\lor\square(p\land q))$. This is because for every successor of $w$, there is a successor of it that satisfies $q$ and one that doesn't.

  • 0
    @Apostolos: Silly me! I kinda missed the "double complement" going on there ($A \setminus A_k = A \setminus (A \setminus \{ a_1,a_2,...a_k,b_1,b_2,...,b_k\}) = \{ a_1,a_2,...a_k,b_1,b_2,...,b_k\}$). Though i'm pretty sure the proof still goes through if you make the replacement; quite the testament for your argument's simplicity (pretty sure i can capture the gist of it in one sentence - "For every subset of $\mathbb{N}$ in the countable frame, select two elements in it not previously selected, adding only one to an initially empty $V(q)$; then observe that the formula isn't valid").2012-12-30