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
    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.2012-12-28
  • 0
    @AsafKaragila The forcing relation is, in some sense, a special case of the $\Vdash$ relation for modal semantics...2012-12-28
  • 0
    @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)2012-12-28
  • 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
    Tis good to see you active!2012-12-28
  • 0
    @Asaf: Nice to see you too! :)2012-12-28
  • 0
    @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$.2012-12-28
  • 0
    @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.2012-12-28
  • 0
    @hcp: I'll fix it.2012-12-29
  • 0
    @hcp: Now I think it's ok, but there's a combinatorial argument involved and I really wish I could do without it. Also, indeed the Lowenheim-Skolem theorem can be used as you mention. I'll try to improve on the answer tomorrow.2012-12-29
  • 0
    @Apostolos: Sorry, i wasn't able to follow the very last inference - couldn't tell why $w_A$ and $w_B$ needed to be distinct. In fact, the new paragraph seems odd to me. Most of it is spent proving the existence of an uncountable family of subsets of $\mathbb{N}$ with non-empty pairwise intersection and difference; but the example given at the top, the family of branches, is already such a family, making most of the paragraph redundant.2012-12-29
  • 0
    @hcp: Yes, you are right the branches are such a family. Apologies for that, but my answer was rewritten late at night. I plan to rewrite the answer and make it more clear.2012-12-29
  • 0
    @Apostolos: At this point, i'm pretty sure i'm the one who needs to apologize for all the nitpicking! But back on topic; the furthest i got on $w_a \neq w_b$ from the given facts was realizing that any non-principal ultrafilter contains at most one element of the family of branches. Couldn't quite proceed from there, though (let alone know whether i'm in the rigth path or not).2012-12-29
  • 0
    @Apostolos: Here we're back to the original issue: $w_a\cap \{ a_k:k\in\mathbb{N}\}$ is a subset of $\{ a_k:k\in A\}$, or of $\{ a_k:k\notin A\}$, not exactly one or other. It could very well, for example, contain only $b$. The issue is on the last line of the second-to-last paragraph.2012-12-29
  • 0
    @hcp: You are right. I cannot believe how I completely misunderstood what you said. Sorry.2012-12-29
  • 0
    @hcp: I *hope* it's ok now. The proof is completely different now. Sorry for the faulty proof.2012-12-29
  • 0
    @Apostolos: There are some details i could complain about ("...for every $m\leq k$ there are some $a,b\in A$ such that..." instead of "...for every $m\leq k$ there are some $a,b\in A \setminus A_k$ such that..."), but as far as i'm concerned, this is it!2012-12-29
  • 0
    @hcp: Why is that a problem? $A\setminus A_k$ contains exactly the elements for which $V(q)$ is defined.2012-12-30
  • 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