Reducts and expansions
From Learning Logic for Computer Science
Reducts and expansions relate structures over signatures where one signature is contained in the other one.
Reducts
A directed graph with two distinguished vertices can also be viewed as an ordinary graph without distinguished vertices, simply by ignoring the fact that vertices are distinguished. This can be generalized and formalized.
Definition Let $\mathcal S$ and $\mathcal S'$ be signatures such that $\mathcal S \subseteq \mathcal S'$. The reduct of an $\mathcal S'$ structure $\mathcal A'$ to $\mathcal S$ is denoted $\mathcal A' \vert \mathcal S$. It is the $\mathcal S$ structure which has the same universe as $\mathcal A'$ and where all symbols from $\mathcal S$ are interpreted as in $\mathcal A'$.
Example Let $\mathcal S' = \{s, t, E/2\}$. Let the $\mathcal S'$ structure $\mathcal A'$ be defined by: \begin{align} A' & = \{0,1,2\}\\ s^{\mathcal A'} & = 0\\ t^{\mathcal A'} & = 2\\ E^{\mathcal A'} & = \{\langle 0, 1\rangle, \langle 1,1\rangle, \langle 1,2\rangle\} \end{align} Let $\mathcal S = \{E/2\}$, that is, $\mathcal S \subseteq \mathcal S'$. Then $\mathcal A' \vert \mathcal S$ is the $\mathcal S$ structure $\mathcal A$ defined by: \begin{align} A & = \{0,1,2\}\\ E^\mathcal A & = \{\langle 0, 1\rangle, \langle 1,1\rangle, \langle 1,2\rangle\} \end{align}
Expansions
The opposite of forgetting certain symbols in a signature is introducing new ones. Clearly, these symbols need to be interpreted.
Definition Let $\mathcal S$ and $\mathcal S'$ be signatures such that $\mathcal S \subseteq \mathcal S'$. An $\mathcal S'$ structure $\mathcal A'$ is an $\mathcal S'$ expansion of a $\mathcal S$ structure $\mathcal A$ if $\mathcal A' \vert \mathcal S = \mathcal A$.
Example Let $\mathcal S = \{E/2\}$ and $\mathcal S' = \{s, t, E/2\}$, that is, $\mathcal S \subseteq \mathcal S'$. Consider the $\mathcal S$-structure $\mathcal A$ defined by: \begin{align} A & = \{0,1,2\}\\ E^\mathcal A & = \{\langle 0, 1\rangle, \langle 1,1\rangle, \langle 1,2\rangle\} \end{align} Then there are 9 different $\mathcal S'$ expansions of $\mathcal A$.