How can you prove the equivalance relation for the following model?

Question

Given two Kripke-frames $M=(W,R)$ and $U=(E,S)$ where $W,E$ are 'possible worlds' and $R,S$ are equivalence relations on $W,E$ respectively.

we define $M\otimes U = (W',R')$ as follows:

• $W'=\{\ (x,y) | x\in W, y\in E $ and some preconditions in $x$ are satisfied $\}$
• $R'= \{\big((x,y)(w,v)\big)| (x,y), (w,v)\in W'; (x,w)\in R; (y,v)\in S\}$

How can I prove that $R'$ is again an equivalence relation (or in other words: if my frames satisfy the S5 axioms of epistemic logic, how can I show that these properties hold in my new model?

Another variant of the question: Assume that the frames satisfy the KD45 properties, that is, our frames $M$ and $U$ are serial, transitive and euclidean: how can I prove that the properties of my frames are maintained in $M\otimes E$?

Answer 1

It's easiest to show this component-wise. Using infix notation to avoid parentheses, I argue for symmetry. If $(x,y)R'(w,v)$ then it implies $xRw$, which by symmetry of $R$ implies $wRx$; likewise the definition of $R'$ implies that $ySv$, which in turn implies $vSy$. Therefore $((w,v),(x,y))$ is a pair that satisfies the conditions of $R'$. Reflexivity and transitivity work similarly.

More generally, (using $\varphi$ to stand for the "preconditions" in the definition of $W'$) the relation you describe is a product relation of $M'\times U$ where $M'$ is the substructure of $M$ with underlying set $\{x\in W:\varphi\}$. Three basic model theoretic facts combine to give you the full result immediately:

1. Universal sentences are preserved under taking substructures.
2. The product of two structures preserves Horn sentences.
3. The theory of equivalence relations is Horn and universal.

For the variant, it's easy to see that being Euclidian, being transitive, and being serial are Horn conditions and will be preserved by the step of taking product relations, but seriality still poses a different problem. "$R$ is serial" is not a universal sentence, and therefore needn't be closed under restriction like the conditions from the previous example. One needs to ensure that $\{x\in W:\varphi\}$ is closed under witnesses for seriality in some suitable way.