S_i$ for all $i \in [n]$, and $R^{[{\mathbf{A}}, S_1, \ldots, S_n]} = R^{{\mathbf{A}}}$ for all $R \in \sigma$.

#### Homomorphisms and the constraint satisfaction problem.

For similar structures ${\mathbf{A}}$ and ${\mathbf{B}}$ over the signature $\sigma$, a *homomorphism* from ${\mathbf{A}}$ to ${\mathbf{B}}$ is a mapping $h: A \rightarrow B$ such that for every symbol $R$ of $\sigma$ and every tuple $(a_1, \ldots, a_k) \in R^{{\mathbf{A}}}$, it holds that $(h(a_1), \ldots, h(a_k)) \in R^{{\mathbf{B}}}$. We use ${\mathbf{A}}{\rightarrow}{\mathbf{B}}$ to indicate that there is a homomorphism from ${\mathbf{A}}$ to ${\mathbf{B}}$; when this holds, we also say that ${\mathbf{A}}$ *is homomorphic to* ${\mathbf{B}}$. It is well-known and straightforward to verify that the homomorphism relation ${\rightarrow}$ is transitive, that is, if ${\mathbf{A}}{\rightarrow}{\mathbf{B}}$ and ${\mathbf{B}}{\rightarrow}{\mathbf{C}}$, then ${\mathbf{A}}{\rightarrow}{\mathbf{C}}$.

The *constraint satisfaction problem (CSP)* is the problem of deciding, given as input a pair $({\mathbf{A}}, {\mathbf{B}})$ of similar structures, whether or not there exists a homomorphism from ${\mathbf{A}}$ to ${\mathbf{B}}$. When $({\mathbf{A}}, {\mathbf{B}})$ is an instance of the CSP, we will also call a homomorphism from ${\mathbf{A}}$ to ${\mathbf{B}}$ a *satisfying assignment*; say that the instance is *satisfiable* if there exists such a homomorphism; and, say that the instance is *unsatisfiable* if there does not exist such a homomorphism. 