Skip to main content
added 1905 characters in body
Source Link

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$p-morphisms (open, continuous surjections) preserve modal validity. Thus, for any space $X$, the existence of $p$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$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.


Addendum

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.

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 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.

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.


Addendum

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.

Source Link

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 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.