${\mathbf{A}}, {\mathbf{B}}, \ldots$ to denote structures, and the corresponding non-bold capital letters $A, B, \ldots$ to denote their universes. We say that a structure ${\mathbf{B}}$ is *finite* if its universe $B$ has finite size. Unless stated otherwise, we assume all structures under discussion in this paper to be finite. We say that a structure ${\mathbf{B}}$ *has all constants* if for each $b \in B$, there is a relation symbol $R_b$ with $R_b^{{\mathbf{B}}} = \{ (b) \}$.

When two structures ${\mathbf{A}}$ and ${\mathbf{B}}$ are defined over the same signature $\sigma$, we say that they are *similar*. We define the following notions on similar structures. For similar structures ${\mathbf{A}}$ and ${\mathbf{B}}$ over a signature $\sigma$, we say that ${\mathbf{A}}$ is an *induced substructure* of ${\mathbf{B}}$ if $A \subseteq B$ and for every $R \in \sigma$ of arity $k$, it holds that $R^{{\mathbf{A}}} = A^k \cap R^{{\mathbf{B}}}$. Observe that for a structure ${\mathbf{B}}$ and a subset $B' \subseteq B$, there is exactly one induced substructure of ${\mathbf{B}}$ with universe $B'$. For similar structures ${\mathbf{A}}$ and ${\mathbf{B}}$ over a signature $\sigma$, the product structure ${\mathbf{A}}\times {\mathbf{B}}$ is defined to be the structure with universe $A \times B$ and such that $R^{{\mathbf{A}}\times {\mathbf{B}}} = 
\{ 