Necessary and sufficient condition for a first-order property of binary relations to be preserved under domain enlargement.

Question

Let $(A;R)$ be a structure consisting of a single binary relation. Now, if $B$ is a superset of $A$, $R$ is still a binary relation on $B$, so we can form the structure $(B;R)$. I call such a structure a domain enlargement of our original structure. I am very curious as to exactly which first-order properties of binary relations are preserved by domain enlargement. For example, transitivity is preserved, and so is symmetry, but reflexivity is not preserved. I initially thought all and only universal sentences are preserved, but it turns out that is not the case. So, then, what is a syntactic property of a sentence in the language of binary relations that is necessary and sufficient for it to be preserved under domain enlargement?

Answer 1

I don't know the answer but here is a sufficient condition, i.e., a fairly extensive set of sentences which are preserved by domain enlargement. Let $\Phi$ be the smallest set of formulas satisfying the closure conditions:

1. All quantifier-free formulas belong to $\Phi$.
2. If $\varphi,\psi\in\Phi$ then $\varphi\land\psi,\varphi\lor\psi\in\Phi$.
3. If $\phi\in\Phi$ and $x$ is a variable then $\exists x\varphi\in\Phi$.
4. If $\varphi\in\Phi$ and $x,y$ are distinct variables then $\forall x[\exists y(Rxy\lor Ryx)\to\varphi]\in\Phi$.

Every formula in $\Phi$ is preserved by domain enlargement. in particular, every sentence in $\Phi$ is preserved by domain enlargement, as is every sentence which is logically equivalent to a sentence in $\Phi$.