# Prove that $\Diamond\Box p \rightarrow \Diamond (\Box (p\land q) \lor \Box(p\land\neg q))$ does not define a first-order condition on frames

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?

-
Do you mean $\Vdash$ or $\vdash$ in the first paragraph? The former is often used to denote th forcing relation, but is used in other contexts as well; the latter is used to denote the probability relation. –  Asaf Karagila Dec 28 '12 at 7:38
@AsafKaragila The forcing relation is, in some sense, a special case of the $\Vdash$ relation for modal semantics... –  Zhen Lin Dec 28 '12 at 7:56
@AsafKaragila I added a quick review of the concepts of modal logic i used; among them what i meant by $\Vdash$. Is this clear enough? (Also, sorry, i do not know what the forcing or probability relations are) –  hcp Dec 28 '12 at 13:59
Ugh. I just noticed, the silly iPhone replaced provability by probability. –  Asaf Karagila Dec 28 '12 at 14:01

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.

-
Tis good to see you active! –  Asaf Karagila Dec 28 '12 at 16:46
@Asaf: Nice to see you too! :) –  Apostolos Dec 28 '12 at 18:18
@Apostolos After some thinking, i believe there's a flawed (perhaps incomplete) step in your reasoning. You can infer that there is an element $w_a$ that contains a subset of $\{a_k:k\in A\}$. So i'm not so sure that, just because there are uncountable many $A$, there would be uncountable many $w_a$. Consider, for example, all $A$ that contain the set of odd numbers. There are uncountably many such $A$, but as long as my frame contains a $w$ of second type that contains $(a_1,a_3,a_5,...)$, then it satisfies $\varphi$ for all such $V_A$. –  hcp Dec 28 '12 at 21:37
@Apostolos Oh, and if you're familiar with the downward Löwenheim–Skolem theorem, i think you can use it to work with a proper substructure of the original frame, sidestepping the multiple types of elements and $a_k$ talk. –  hcp Dec 28 '12 at 21:41
@hcp: I'll fix it. –  Apostolos Dec 29 '12 at 0:50