# A necessary condition for S4-completeness?

It is well-known that the modal logic S4 is complete with respect to the class of all finite quasi-trees (where we interpret the $\Box$ modality as topological interior, and topologize a quasi-tree with the up-set topology). It is also well-known that p-morphisms (open, continuous surjections) preserve modal validity. Thus, for any space $X$, the existence of p-morphisms from $X$ onto every finite quasi-tree is a sufficient condition for $X$ to be S4-complete. This technique can be used to establish, for example, McKinsey and Tarski's famous result that S4 is the logic of any dense-in-itself, metrizable space.

My question is:

Is this condition also necessary? Said differently: is there a space $X$ and a finite quasi-tree $Q$ such that $X$ is S4-complete but there exists no p-morphism $\rho: X \to Q$?

This seems like a natural question to ask, but I haven't had much luck in finding any discussion about it. Even just a pointer to the right body of literature would be very much appreciated.

Here I'll define my terms a little more carefully, and spell out the translation of my question in terms of the more standard Kripke semantics.

Recall that quasi-orders are sets equipped with reflexive, transitive binary relations, which is precisely the class of Kripke frames corresponding to S4. A quasi-order $Q = (Q,\leq)$ is called a quasi-tree if $Q/\sim$ is a tree, where $\sim$ is the equivalence relation on $Q$ defined by

$$x \sim y \iff x \leq y \textrm{ and } y \leq x.$$

As mentioned in the comments, there is a correspondence between quasi-orders and Alexandrov spaces, one direction of which is given by topologizing quasi-orders with the up-set topology. There is also a notion of a p-morphism between quasi-orders, nicely outlined by Wikipedia. A p-morphism between quasi-order corresponds to an open, continuous map between the corresponding Alexandrov spaces.

I use the phrase "$X$ is S4-complete" (perhaps somewhat idiosyncratically?) to mean that every formula validated by $X$ is provable in S4; equivalently, $X$ refutes all non-theorems of S4. It is known that if $Q$ is any quasi-order and for each finite quasi-tree $Q_{t}$ there exists a surjective p-morphism $\rho_{t}: Q \to Q_{t}$, then $Q$ is S4-complete. One can then ask:

Is the converse true? Does every S4-complete quasi-order Q admit maps $\rho_{t}$ as above?

If not, then a counter-example can be "lifted" into the topological setting, thus answering my original question. However, a positive answer to this question does not immediately resolve the topological version since the quantification in the topological version is over all spaces, rather than just the Alexandrov spaces. Nonetheless, I would be interested in an answer (or even a hint at an answer) to either question.

-
Can you provide the translation of your question into Kripke models and frames? The finite quasi-trees are complete for S4 in the sense that every Kripke model built on such a frame will satisfy S4, but not every frame all of whose models satisfy S4 will be a tree, since every directed quasi-order satisfies S4.2, which includes S4, but these need not be trees. I'm not sure without further thought, however, whether this provides an answer to the topological version of your question. – Joel David Hamkins Aug 27 '11 at 21:57
If you do not require Q to be finite you can take X to be the Cantor space (which is shown in McKinsey-Tarski paper to be S4-complete), and Q the quasi-order corresponding to an Alexandrov space which is non compact (I use here that Alexandrov spaces are in correspondence with quasi-orders). – boumol Aug 27 '11 at 22:09
boumol: Good point (and nice example)! I did mean to say "finite", and I've edited that in now. It is interesting to note that even the infinite binary tree, which is itself S4-complete (and, of course, a quasi-tree) fails to be the open, continuous image of all S4-complete spaces. Joel: Thanks for your thoughts. I've edited the question to include some of what you asked for. I'm not sure I understand the example with directed quasi-orders, so if it still makes sense in light of my recent edits, I'd appreciate hearing more! – Adam Bjorndahl Aug 28 '11 at 14:53

S4 is complete with respect to a Kripke frame or general frame or topological frame $F$ if and only if $F$ is an S4-frame and for every finite rooted S4-frame $G$, there exists a p-morphism of a generated subframe of $F$ onto $G$.

The left-to-right implication follows from the existence of Fine’s frame formulas: there is a formula $\alpha_G$ such that for any K4-frame $H$, $\alpha_G$ is refutable in $H$ if and only if there exists a p-morphism of a generated subframe of $H$ onto $G$. One way of constructing $\alpha_G$ is as follows. Assume that $r$ is a root of $G$, and let $R$ be the accessibility relation of $G$. We put

$$\alpha_G=\Box^+\biggl(\bigwedge_{\substack{i,j\in G\\\\i\ne j}}(p_i\to\neg p_j)\land\bigwedge_{\substack{i,j\in G\\\\i\mathrel Rj}}(p_i\to\Diamond p_j)\land\bigwedge_{i\in G}\Bigl(p_i\to\Box\bigvee_{i\mathrel Rj}p_j\Bigr)\biggr)\to\neg p_r,$$

where $\Box^+\phi=\phi\land\Box\phi$ (which is equivalent to $\Box\phi$ in S4; the formula above works for K4 as well). Let $\models$ be a valuation in $H$ such that $x\not\models\alpha_G$ for some $x\in H$. Let $H_x$ be the generated subframe of $H$ rooted at $x$. For every $y\in H_x$, there exists a unique $i\in G$ such that $y\models p_i$; put $f(y)=i$. Then $f\colon H_x\to G$ is a p-morphism such that $f(x)=r$. Conversely, given such a p-morphism, one can construct a valuation refuting $\alpha$ by reversing the process.

Now, if $G$ is an S4-frame, it is a p-morphic image of itself, hence $\alpha_G$ is not valid in $G$, and a fortiori it is not an S4-tautology. Thus, any $H$ wrt which S4 is complete must also refute $\alpha_G$, hence there exists a p-morphism from a generated subframe of $H$ onto $G$.

Since every finite rooted S4-model is a p-morphic image of a finite quasi-tree, one can restrict attention to such $G$’s.

I’m not quite familiar with the topological semantics of S4, but I suppose the criterion translates to something to the effect of: S4 is complete wrt a space $X$ iff for every finite quasi-tree $G$, there exists an open subset $U\subseteq X$ and a p-morphism (whatever that means when the space is not ordered) of $U$ onto $G$.

-
Maybe I should also stress that there is nothing special about S4: the criterion above works, after obvious modifications, for every normal modal logic extending K4 which has the finite model property. – Emil Jeřábek Sep 14 '11 at 14:38
This is a great answer, thank you very much. Using $G$ as an impromptu index set for propositional variables in the language is a nice technique; is there a reference you might suggest where I can read more about Fine's formula? Also, am I missing something, or should there perhaps be an extra conjunct within the scope of the $\Box^{+}$, something like $\bigvee_{i \in G} p_{i}$ to ensure existence of an $i \in G$ such that $y \models p_{i}$? At any rate, this completely answers my question, and moreover I believe the topological translation you gestured at is the correct one. Thanks again! – Adam Bjorndahl Sep 14 '11 at 14:46
I would suggest Chagrov and Zakharyaschev’s “Modal logic”, which (along with a lot of other useful information) contains a detailed presentation of Zakharyaschev’s canonical formulas (which are generalizations of frame formulas). As for $\bigvee_{i\in G}p_i$: this is redundant, as $\neg\alpha_G$ implies $p_r$ and $\Box^+(p_r\to\Box\bigvee_{r\mathrel Rj}p_j)$, which together imply $\Box\bigvee_ip_i$. (In other words: the domain of a partial p-morphism is always a generated submodel, hence it is total if it includes a root.) – Emil Jeřábek Sep 14 '11 at 15:00
Right, of course! Good point. And thanks for the reference! – Adam Bjorndahl Sep 14 '11 at 15:08

The converse does not hold in general. Thanks to Nick and Guram Bezhanishvili and David Gabelaia for coming up with a counterexample.

Let $X$ denote the topological sum of $\mathbb{R}$ and a single point space, $\{x\}$. Since $\mathbb{R}$ sits as an open subspace of $X$ and $\mathbb{R}$ is S4-complete, $X$ is also S4-complete. On the other hand, since $x$ is isolated in X, there is no hope of finding an open map which sends $x$ to a 2-element cluster (since neither point in such a cluster is itself isolated).

In terms of Kripke frames (i.e. quasi-orders), an analogous counter-example can be constructed by starting with some S4-complete quasi order $Q$ (for example, the infinite binary tree), and adjoining to it a new element $x$ which is incomparable to any of the original elements of $Q$.

There is a sense in which these counter-examples are unsatisfying, because they work essentially by exhibiting objects which have two entirely separate "pieces": one piece to satisfy S4-completeness, and the other to block the existence of certain open, continuous maps. A refinement of the question may therefore be in order, though such a refinement is still at the "pencil and paper" stage, and not quite the "post on MO" stage.

-