# Validity in Kripke frames whose points are finite or infinite sequences

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?

-

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

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

-