Given a clone $\mathcal{C}$ over the set $\{\top,\perp\}$, let $\mathsf{FOL}^\mathcal{C}$ be the version of first-order logic with (symbols corresponding to) elements of $\mathcal{C}$ replacing the usual Booleans; note that I will always include $\forall,\exists$, and $=$. If $\mathcal{C}$ is a proper subclone of $\mathcal{D}$ then $\mathsf{FOL}^\mathcal{C}$ is strictly less expressive than $\mathsf{FOL}^\mathcal{D}$. However, if we restrict the structures under consideration, the picture can change; e.g. while $\{\wedge,\vee\}$ is not functionally complete in general it is if we restrict attention to the structure $(\mathbb{N};+,1)$ or similar. See this MSE post of mine for details.
For $\mathfrak{M}$ a structure and $\mathcal{C},\mathcal{D}$ clones on $\{\top,\perp\}$, let $\mathcal{C}\sim_\mathfrak{M}\mathcal{D}$ iff every $\mathsf{FOL}^\mathcal{C}$-definable relations on $\mathfrak{M}$ is $\mathsf{FOL}^\mathcal{D}$-definable and vice-versa (allowing parameters from $\mathfrak{M}$ throughout). My general question is which equivalence relations are of the form $\sim_\mathfrak{M}$ for some $\mathfrak{M}$, but I suspect that's intractable (EDIT: as Emil Jerabek observes, this might be doable since we really only care about clones containing the constants and there are few of those); to keep things more focused, the following seems like a good test question:
Is $\sim_\mathfrak{M}$ always a congruence on Post's lattice?
I briefly thought I had a proof that the answer was yes, but it broke down.
