Structures

Une structure $\mathcal M$ pour la signature $\mathcal L$ est la donnée d'un ensemble non vide $M$, son domaine, et d'une interprétation de chaque symbole : un élément $c^{\mathcal M} \in M$ pour chaque constante, une application $f^{\mathcal M} : M^n \to M$ pour chaque symbole de fonction d'arité $n$, une partie $R^{\mathcal M} \subset M^n$ pour chaque symbole de relation d'arité $n$.

Une valuation est une application $s$ de l'ensemble des variables dans $M$. La valeur $t^{\mathcal M}[s]$ d'un terme s'obtient par récurrence : $x^{\mathcal M}[s] = s(x)$ pour une variable, $c^{\mathcal M}[s] = c^{\mathcal M}$ pour une constante, et $$\begin{aligned} &(f\, t_1 \cdots t_n)^{\mathcal M}[s] \\ &\quad = f^{\mathcal M}(t_1^{\mathcal M}[s], \dots, t_n^{\mathcal M}[s]). \end{aligned}$$