((a_1, b_1), \ldots, (a_k, b_k)) ~|~ {\overline{a}} \in R^{{\mathbf{A}}}, {\overline{b}} \in R^{{\mathbf{B}}} \}$ for all $R \in \sigma$. We use ${\mathbf{A}}^n$ to denote the $n$-fold product ${\mathbf{A}}\times \cdots \times {\mathbf{A}}$.

We say that a structure ${\mathbf{B}}$ over signature $\sigma'$ is an *expansion* of another structure ${\mathbf{A}}$ over signature $\sigma$ if (1) $\sigma' \supseteq \sigma$, (2) the universe of ${\mathbf{B}}$ is equal to the universe of ${\mathbf{A}}$, and (3) for every symbol $R \in \sigma$, it holds that $R^{{\mathbf{B}}} = R^{{\mathbf{A}}}$. We will use the following non-standard notation. For any structure ${\mathbf{A}}$ (over signature $\sigma$) and any subset $S \subseteq A$, we define $[{\mathbf{A}}, S]$ to be the expansion of ${\mathbf{A}}$ with the signature $\sigma \cup \{ U \}$ where $U$ is a new symbol of arity $1$, defined by $U^{[{\mathbf{A}}, S]} = S$ and $R^{[{\mathbf{A}}, S]} = R^{{\mathbf{A}}}$ for all $R \in \sigma$. More generally, for a structure ${\mathbf{A}}$ (over $\sigma$) and a sequence of subsets $S_1, \ldots, S_n \subseteq A$, we define $[{\mathbf{A}}, S_1, \ldots, S_n]$ to be the expansion of ${\mathbf{A}}$ with the signature $\sigma \cup \{ U_1, \ldots, U_n \}$ where $U_1, \ldots, U_n$ are new symbols of arity $1$, defined by $U_i^{[{\mathbf{A}}, S_1, \ldots, S_n]} = 