such that, ${\xi}\equiv\widetilde{{\xi}}$, $\varphi\equiv{\widetilde{\varphi}}(x)$, and $\pi\equiv{\widetilde{\pi}}(x,y)$.

The main result is a *strong* converse of Proposition \[prop:pdl-fo3\]:

\[thm:FO-to-PDLm-main\] Every ${\textup{FO}}[{\rightarrow},{\lhd},\le]$ formula with at most two free variables is equivalent to some ${{{\textup{PDL}_{\mathsf{sf}}}}}$ formula. More precisely, for every ${\textup{FO}}[{\rightarrow},{\lhd},\le]$ sentence $\Phi_0$, formula $\Phi_1(x)$ with one free variable, and formula $\Phi_2(x,y)$ with two free variables, there exist some ${{{\textup{PDL}_{\mathsf{sf}}}[{\mathsf{Loop}}]}}$ sentence ${\xi}$, ${{{\textup{PDL}_{\mathsf{sf}}}[{\mathsf{Loop}}]}}$ event formula $\varphi$, and ${{{\textup{PDL}_{\mathsf{sf}}}[{\mathsf{Loop}}]}}$ path formulas $\pi_{ij}$, respectively, such that, $\Phi_0\equiv{\xi}$, $\Phi_1(x)\equiv\varphi$, and $\Phi_2(x,y)\equiv\bigcup_i\bigcap_j\pi_{ij}$.

From Theorem \[thm:FO-to-PDLm-main\] and Proposition \[prop:pdl-fo3\], we deduce that ${\textup{FO}}$ has the three variable property:

\[thm:fo3\] ${\mathcal{L}}({\textup{FO}}[{\rightarrow},{\lhd},\le]) = {\mathcal{L}}({\textup{FO}}^3[{\rightarrow},{\lhd},\le])$.

From ${\textup{FO}}$ to $\boldsymbol{{{{\textup{PDL}_{\mathsf{sf}}}}}}$ {#sec:fo-pdl}
-----------------------------------------------------------------------

In the remainder of this section, we give the translation from ${\textup{FO}}$ to ${{{\textup{PDL}_{\mathsf{sf}}}}}$. We start with some basic properties of ${{{\textup{PDL}_{\mathsf{sf}}}}}$. First, the converse of a ${{{\textup{PDL}_{\mathsf{sf}}}}}$ formula is definable in ${{{\textup{PDL}_{\mathsf{sf}}}}}$ (easy induction on $\pi$).

\[lem:inverse\] Let $R \subseteq \{{\mathsf{Loop}},\cup,\cap,{\mathsf{c}}\}$ and $\pi \in {\textup{PDL}_{\mathsf{sf}}}[R]$ be a path formula. There exists $\pi^{-1} \in {\textup{PDL}_{\mathsf{sf}}}[R]$ such that, for all MSCs $M$, ${\llbracket {\pi^{-1}} \rrbracket_{M}} = {\llbracket {\pi} \rrbracket_{M}}^{-1} = \{(f,e) \mid (e,f) \in {\llbracket {\pi} \rrbracket_{M}}\}$.

Given a ${{{\textup{PDL}_{\mathsf{sf}}}[{\mathsf{Loop}}]}}$ path formula $\pi$, we denote by ${\mathsf{Comp}(\pi)}$ the set of pairs $(p,q) \in {P}\times {P}$ such that there may be a $\pi$-path 