# 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$.