called the *arity* of the tuple; when ${\overline{t}}$ is a tuple, we often use the notation ${\overline{t}} = (t_1, \ldots, t_k)$ to denote its entries. A *relation* over a set $B$ is a subset of $B^k$ for a value $k \geq 1$ called the *arity* of the relation. We use $\pi_i$ to denote the operator that projects onto the $i$th coordinate: $\pi_i({\overline{t}})$ denotes the $i$th entry $t_i$ of a tuple ${\overline{t}} = (t_1, \ldots, t_k)$, and for a relation $R$ we define $\pi_i(R) = \{ \pi_i({\overline{t}}) ~|~ {\overline{t}} \in R \}$. Similarly, for a subset $I \subseteq [k]$ whose elements are $i_1 < \cdots < i_m$, we use $\pi_I({\overline{t}})$ to denote the tuple $(t_{i_1}, \ldots, t_{i_m})$, and we define $\pi_I(R) = \{ \pi_I({\overline{t}}) ~|~ {\overline{t}} \in R \}$.

A *signature* $\sigma$ is a set of symbols, each of which has an associated arity. A *structure* ${\mathbf{B}}$ over signature $\sigma$ consists of a universe $B$, which is a set, and a relation $R^{{\mathbf{B}}} \subseteq B^k$ for each symbol $R \in \sigma$ of arity $k$. (Note that in this paper, we are concerned only with relational structures, which we refer to simply as structures.) Throughout, we will use the bold capital letters 