Modal logic - satisfiability - MathOverflow

Modal logic - satisfiability

2010-11-13T16:54:34Z

Hi there,

Assuming X and Y are modal formulae and diamond X is satisfiable and diamond Y is satisfiable, how would one show that they X AND Y is satisfiable?

I don't think it requires much effort?

I think you need to choose one world and one model where X AND Y is true and that would mean it is satisfiable?

So assuming I'm going about it correctly, any ideas what model and world I should select to show this X AND Y is satisfiable?

Any advice would be great,

Thank you.

P.S. NO appropriate tags for this type of most, maybe someone should create a modal logic one (I can't as I'm a new user)

Answer by Henry Towsner for Modal logic - satisfiability

2010-11-13T18:03:34Z

Your question is quite underspecified; it's not clear what language you're talking about (my guess is propositional logic plus box and diamond, which is the most common modal logic, but by no means the only one). Even then, there are many different proposed semantics, corresponding to different interpretations of diamond. Even if, by "satisfiable", you mean satisfiable in a possible world semantics (which later parts of your question imply), there are still questions to be decided about the kinds of relationships between the possible worlds allowed. However I think the statement is untrue in just about any system.

To see this, let $X$ be any propositional formula which is neither a tautology nor the negation of a tautology, and let $Y$ be $\neg X$. Take a model with just two worlds, interpret $\diamond$ as meaning "true in either world", and make $X$ true in one and false in the other. Then $\diamond X$ and $\diamond Y=\diamond \neg X$ are both true in every world of this model, but clearly $X\wedge Y=X\wedge\neg X$ is unsatisfiable.

Answer by Ed Dean for Modal logic - satisfiability

2010-11-13T20:10:23Z

Your question as originally written (which Henry correctly diagnosed as problematic in two ways) does not match the more reasonable aim reflected in your comments to Henry's answer. Specifically, your comments make it sound like you want to show that the satisfiability of both $\diamond X$ and $\diamond Y$ implies the satisfiability of $\diamond X \wedge \diamond Y$, not the satisfiability of $X\wedge Y$ as your original phrasing states.

If your notion of satisfiability of a formula $Z$ is simply that there is some Kripke model $\mathcal{M}$ (with no restrictions on its accessibility relation) and some world $w$ in it such that $\mathcal{M},w\models Z$, then this weaker form of the question isn't too difficult to answer.

Let $\mathcal{M},w\models\diamond X$ and $\mathcal{N},v\models\diamond Y$. In particular, there is a world $u$ in $\mathcal{N}$ which is accessible from $v$ and satisfies $Y$. Now just form a new model $\mathcal{P}$ whose set of worlds is the union of those of $\mathcal{M},\mathcal{N}$, and whose accessibility relation is the union of those of $\mathcal{M},\mathcal{N}$, plus we set $u$ to be accessible from $w$. Then $\mathcal{P},w\models\diamond X \wedge \diamond Y$.

Henry's point about underspecification is still pertinent. I'm not sure I've gotten at what you want, and if you were to be limited to special kinds of Kripke frames, for instance, then the argument would need to say a bit more (ensuring we end up with an appropriate $\mathcal{P}$). I hope this is helpful.