Structures and variable assignments

An $L$-structure $\mathcal{M}$ has a nonempty set carrier $M$, values $c^{\mathcal{M}}\in M$, total functions $f^{\mathcal{M}}:M^{a(f)}\to M$, and relations $R^{\mathcal{M}}\subseteq M^{a(R)}$, supplied as set-indexed interpretation data. Logical equality is literal equality on $M$. An assignment is a function $s:\omega \to M$, also written $s(v_i)=s(i)$. The update $s[x:=b]$ changes only the value at variable $x$ to $b\in M$.

For structures in the same signature a homomorphism $h:M\to N$ preserves constants and function values and takes related tuples to related tuples. It is strong if it also reflects every nonlogical relation. An embedding is an injective strong homomorphism; an isomorphism is a surjective embedding. A substructure has a nonempty subcarrier containing all constants, closed under all functions, with functions and relations restricted from the larger structure. A reduct keeps the carrier and only the interpretations for a smaller signature; an expansion is the reverse relationship. All finite powers and the assignment set $M^{\omega }$ are sets.

Conventions and prerequisites: Set signatures and finite syntax strings.