be defined by $x \le y \wedge \bigvee_{p \in {P}} p(x) \wedge p(y)$. We write ${\mathsf{Free}}(\Phi)$ the set of free variables of $\Phi$.

Let $M = (E,{\rightarrow},{\lhd},{\mathit{loc}},\lambda)$ be an MSC. An *interpretation* (for $M$) is a mapping $\nu\colon {\mathcal{V}_{\mathsf{event}}}\cup {\mathcal{V}_{\mathsf{set}}}\to E \cup 2^E$ assigning to each $x \in {\mathcal{V}_{\mathsf{event}}}$ an event $\nu(x) \in E$, and to each $X \in {\mathcal{V}_{\mathsf{set}}}$ a set of events $\nu(X) \subseteq E$. We write $M,\nu \models {\Phi}$ if $M$ satisfies ${\Phi}$ when the free variables of ${\Phi}$ are interpreted according to $\nu$. Hereby, satisfaction is defined in the usual manner. In fact, whether $M,\nu \models {\Phi}$ holds or not only depends on the interpretation of variables that occur free in ${\Phi}$. Thus, we may restrict $\nu$ to any set of variables that contains at least all free variables. For example, for ${\Phi}(x,y) = (x {\lhd}y)$, we have $M,[x \mapsto e, y \mapsto f] \models {\Phi}(x,y)$ iff $e {\lhd}f$. For a *sentence* ${\Phi}\in {\textup{MSO}}$ (without free variables), we define ${\mathbb{L}}({\Phi}) {:=}\{M \in {\mathbb{MSC}({P},\Sigma)} \mid M \models {\Phi}\}$.

We say that two formulas ${\Phi}$ and ${\Phi}'$ are *equivalent*, written ${\Phi}\equiv {\Phi}'$, if, for all MSCs $M = (E,{\rightarrow},{\lhd},{\mathit{loc}},\lambda)$ and interpretations $\nu \colon {\mathcal{V}_{\mathsf{event}}}\cup {\mathcal{V}_{\mathsf{set}}}\to E \cup 2^E$, 