MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose $D$ is a non-empty set and $\{ R_i : i \in \mathbb{N} \}$ is a family of binary relations on sequences over $D$ so that $R_i \subseteq D^i \times D^i$. Let $R_\omega \subseteq D^\omega \times D^\omega$ be a relation that holds between two denumerable sequences $x$ and $y$ over $D$ iff for all $n\in \mathbb{N}$, $x_1,\ldots,x_n R_n y_1,\ldots,y_n$.

Now for every ordinal $n \leq \omega$, there is a Kripke frame $F_n = (D^n, R_n)$. I would like to show that any formula of (standard propositional) modal logic is valid in $F_\omega$ iff it is valid in all $F_n$ with finite $n$.

For example, clearly $R_\omega$ is reflexive iff all $R_n$ with finite $n$ are reflexive, so $\Box p \to p$ is valid in $F_\omega$ iff it is valid in all $F_n$ with finite $n$. But is this true for all formulas? If so, how would I go about showing it?

share|cite|improve this question
up vote 3 down vote accepted

It is an attractive idea, but unfortunately, it seems not to be true.

The reason is that we can have that every $R_n$ is nontrivial, in the sense that the relation sometimes holds between different two different sequences, but there is no path through these relations so that $R^\omega$ never holds between two different sequences. For example, let $D=\{0,1\}$, and when $n$ is even, let $R_n$ be the reflexive lexical order on binary sequences, but when $n$ is odd, let it be the reverse lexical order. Thus, $R_\omega$ will never hold except reflexively, since the initial segments of a two infinite sequence can't be related lexically in both directions unless they are equal.

In this case, the formula $\Box p\leftrightarrow p$ will be valid in $R_\omega$, but not in any $R_n$.

Another simple counterexample would occur where one $R_n$, say $R_{17}$, never holds, but all the other $R_n$'s always hold. In this case, $R_\omega$ will never hold, and so it's validities will agree with the validities of $R_{17}$, but not with any other $R_n$.

share|cite|improve this answer
Thanks! Your response suggests that the claim might be true if each $R_n$ extends $R_{n-1}$ in the sense that whenever $(x_1,\ldots,x_n)R_n(y_1,\ldots,y_n)$, then $(x_1,\ldots,x_{n-1})R_{n-1}(y_1,\ldots,y_{n-1})$. (That would actually be enough for my application.) Does that seem right? – Wolfgang Schwarz May 11 '13 at 14:13
Yes, you seem to have some need for greater interaction of the $R_n$'s with each other. But that specific proposal is refuted by Sam Robert's example. I believe that some kind of bisimilarity type relation will be required to make the conclusion go through. – Joel David Hamkins May 12 '13 at 2:14

Let $D=\omega$ and $(x_0,...,x_n)R_n(y_0,...,y_n)$ just in case $x_0 <...< x_n$, $y_0 <...< y_n$, and $x_n < y_0$. It is easy to see that for any two infinite sequences $s, s'$ there is some $n$ such that $(s(0),...,s(n))\not R_n(s'(0),...,s'(n))$ -- for some $n$, $s'(0) < s(n)$. Thus $R^\omega$ is empty and $\Box \bot$ is valid in $(D^\omega, R^\omega)$ though not in any $(D^n, R_n)$. In addition, if $(x_0,...,x_{n+1})R_{n+1}(y_0,...,y_{n+1})$, then $(x_0,...,x_n)R_n(y_0,...,y_n)$ since $x_n < x_{n+1} < y_0$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.