Structures and Semantics — Foundations of Mathematics

Definition 2.3.1. An $$\mathcal{L}$-$ structure $\mathcal{M}$ is given by the following data:

a nonempty set $$M$$ called the underlying set of $\mathcal{M};$
a function $f^{\mathcal{M}}\colon M^{n_f}\to M$ for each $f\in {\mathcal{F}};$
a set $R^{\mathcal{M}}\subseteq M^{n_R}$ for each $R\in {\mathcal{R}};$
an element $c^{\mathcal{M}}\in M$ for each $c\in \mathcal{C}.$

The functions $f^{\mathcal M},$ relations $R^{\mathcal M},$ and elements $c^{\mathcal M}$ are the interpretations of the symbols $$f,R,$$ and $$c.$$

Definition 2.3.2. Let $\operatorname{Var}=\{v_1,v_2,\dots\}.$ A variable assignment in $\mathcal M$ is a map $s\colon \operatorname{Var}\to M.$ For $a\in M,$ the assignment $s[x\mapsto a]$ is defined by

\[s[x\mapsto a](y) = \begin{cases} a & \text{if } y=x,\\ s(y) & \text{if } y\ne x. \end{cases}\]

Definition 2.3.3. The value $t^{\mathcal M,s}$ of a term $$t$$ in $\mathcal M$ under an assignment $$s$$ is defined recursively by

\[\begin{aligned} c^{\mathcal M,s} &= c^{\mathcal M},\\ x^{\mathcal M,s} &= s(x),\\ f(t_1,\dots,t_{n_f})^{\mathcal M,s} &=f^{\mathcal M}(t_1^{\mathcal M,s},\dots,t_{n_f}^{\mathcal M,s}). \end{aligned}\]

Definition 2.3.4. The satisfaction relation $\mathcal M,s\vDash\phi$ is defined recursively by

\[\begin{aligned} \mathcal M,s\vDash t=u &\quad\Longleftrightarrow\quad t^{\mathcal M,s}=u^{\mathcal M,s},\\ \mathcal M,s\vDash R(t_1,\dots,t_{n_R}) &\quad\Longleftrightarrow\quad (t_1^{\mathcal M,s},\dots,t_{n_R}^{\mathcal M,s})\in R^{\mathcal M},\\ \mathcal M,s\vDash\neg\phi &\quad\Longleftrightarrow\quad \mathcal M,s\nvDash\phi,\\ \mathcal M,s\vDash\phi\rightarrow\psi &\quad\Longleftrightarrow\quad \mathcal M,s\nvDash\phi\text{ or }\mathcal M,s\vDash\psi,\\ \mathcal M,s\vDash(\forall x)\phi &\quad\Longleftrightarrow\quad \mathcal M,s[x\mapsto a]\vDash\phi\text{ for every }a\in M. \end{aligned}\]

Proposition 2.3.5. Let $$s$$ and $$s'$$ be assignments in an $$\mathcal L$-$ structure $\mathcal M.$

If $$s$$ and $$s'$$ agree on $\operatorname{FV}(t),$ then $t^{\mathcal M,s}=t^{\mathcal M,s'}.$
If $$s$$ and $$s'$$ agree on $\operatorname{FV}(\phi),$ then $\mathcal M,s\vDash\phi$ if and only if $\mathcal M,s'\vDash\phi.$

Definition 2.3.6. For an $$\mathcal L$-$ sentence $\sigma,$ we write $\mathcal M\vDash\sigma$ if $\mathcal M,s\vDash\sigma$ for every assignment $$s,$$ and say that $\sigma$ is true in $\mathcal M.$

Let $\phi$ be a formula with free variables among the distinct variables $\bar v=(v_{i_1},\dots,v_{i_m}),$ and let $\bar a=(a_{i_1},\dots,a_{i_m})\in M^m.$ We write $\mathcal M\vDash\phi(\bar a)$ if $\mathcal M,s\vDash\phi$ for an assignment $$s$$ satisfying $s(v_{i_j})=a_{i_j}$ for $j=1,\dots,m.$

Lemma 2.3.7 (Substitution lemma). Let $\mathcal M$ be an $$\mathcal L$-$ structure, let $$s$$ be an assignment in $\mathcal M,$ and let $$t$$ be a term.

For every term $$u,$$
\[(u[t/x])^{\mathcal M,s}=u^{\mathcal M,s[x\mapsto t^{\mathcal M,s}]}.\]
If $$t$$ is free for $$x$$ in $\phi,$ then
\[\mathcal M,s\vDash\phi[t/x] \quad\Longleftrightarrow\quad \mathcal M,s[x\mapsto t^{\mathcal M,s}]\vDash\phi.\]

Definition 2.3.8. Let $$T$$ be an $$\mathcal L$-$ theory. An $$\mathcal L$-$ structure $\mathcal M$ is a model of $$T,$$ written $\mathcal M\vDash T,$ if $\mathcal M\vDash\sigma$ for every sentence $\sigma\in T.$ The theory $$T$$ is satisfiable if it has a model. We write

\[\operatorname{Mod}(T)=\{\mathcal M:\mathcal M\text{ is an }\mathcal L\text{-structure and }\mathcal M\vDash T\}.\]

Definition 2.3.9. Let $$T$$ be an $$\mathcal L$-$ theory and let $\sigma$ be an $$\mathcal L$-$ sentence. We write $T\vDash\sigma$ and call $\sigma$ a logical consequence of $$T$$ if every model of $$T$$ satisfies $\sigma.$ A sentence $\sigma$ is logically valid if $\varnothing\vDash\sigma,$ in which case we write $\vDash\sigma.$

Definition 2.3.10. An $$\mathcal L$-$ structure $\mathcal M$ is a substructure of an $$\mathcal L$-$ structure $\mathcal N,$ written $\mathcal M\subseteq\mathcal N,$ if

$M\subseteq N,$
$c^{\mathcal M}=c^{\mathcal N}$ for every constant symbol $$c,$$
$f^{\mathcal M}=f^{\mathcal N}|_{M^{n_f}}$ for every function symbol $$f,$$ and
$R^{\mathcal M}=R^{\mathcal N}\cap M^{n_R}$ for every relation symbol $$R.$$

Definition 2.3.11. Suppose that $\mathcal M$ and $\mathcal N$ are $$\mathcal L$-$ structures with underlying sets $$M$$ and $$N,$$ respectively. An $$\mathcal L$-$ homomorphism $\eta\colon M\to N$ is a map such that

for every constant symbol $$c,$$
\[\eta(c^{\mathcal M})=c^{\mathcal N};\]
for every function symbol $$f$$ and all $a_1,\dots,a_{n_f}\in M,$
\[\eta(f^{\mathcal M}(a_1,\dots,a_{n_f})) =f^{\mathcal N}(\eta(a_1),\dots,\eta(a_{n_f}));\]
equivalently, the following diagram commutes:
for every relation symbol $$R$$ and all $a_1,\dots,a_{n_R}\in M,$
\[(a_1,\dots,a_{n_R})\in R^{\mathcal M} \quad\Longrightarrow\quad (\eta(a_1),\dots,\eta(a_{n_R}))\in R^{\mathcal N}.\]

Definition 2.3.12. An injective $$\mathcal L$-$ homomorphism $\eta\colon M\to N$ is an $$\mathcal L$-$ monomorphism. An $$\mathcal L$-$ monomorphism is an $$\mathcal L$-$ embedding if it both preserves and reflects relations: for every relation symbol $$R$$ and all $a_1,\dots,a_{n_R}\in M,$

\[(a_1,\dots,a_{n_R})\in R^{\mathcal M} \quad\Longleftrightarrow\quad (\eta(a_1),\dots,\eta(a_{n_R}))\in R^{\mathcal N}.\]

An embedding identifies $\mathcal M$ with the substructure of $\mathcal N$ carried by $\eta(M).$ A bijective $$\mathcal L$-$ embedding is an $$\mathcal L$-$ isomorphism.

Definition 2.3.13. Two $$\mathcal L$-$ structures $\mathcal M$ and $\mathcal N$ are elementarily equivalent, written $\mathcal M\equiv\mathcal N,$ if

\[\mathcal M\vDash\sigma\quad\Longleftrightarrow\quad\mathcal N\vDash\sigma\]

for every $$\mathcal L$-$ sentence $\sigma.$ The full theory of $\mathcal M$ is

\[\operatorname{Th}(\mathcal M)=\{\sigma:\sigma\text{ is an }\mathcal L\text{-sentence and }\mathcal M\vDash\sigma\}.\]

Definition 2.3.14. A class $\mathcal K$ of $$\mathcal L$-$ structures is an elementary class if there is an $$\mathcal L$-$ theory $$T$$ such that $\mathcal K=\operatorname{Mod}(T).$

Proposition 2.3.15. For every $$\mathcal L$-$ structure $\mathcal M,$

\[\operatorname{Mod}(\operatorname{Th}(\mathcal M)) =\{\mathcal N:\mathcal N\text{ is an }\mathcal L\text{-structure and }\mathcal N\equiv\mathcal M\}.\]