Languages and Semantics

Definition 2.1.1. A language $\mathcal{L}$ is given by the following data:

a set of function symbols $\mathcal{F}$ and positive integer $$n_f$$ for each $f\in {\mathcal{F}};$
a set of relation symbols $\mathcal{R}$ and positive integer $$n_R$$ for each $R\in {\mathcal{R}};$
a set of constant symbols $\mathcal{C}.$

Definition 2.1.2. 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}}: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}.$

We refer to $f^{\mathcal{M}}, R^{\mathcal{M}},$ and $c^{\mathcal{M}}$ as the interpretations of the symbols $$f,R,$$ and $$c.$$

Definition 2.1.3. Suppose that $\mathcal{M}$ and $\mathcal{N}$ are $\mathcal{L}$ -structures with underlying sets $$M$$ and $$N,$$ respectively. An $\mathcal{L}$ -homomorphism $\eta: \mathcal{M}\to\mathcal{N}$ is a map $\eta:M\to N$ that preserves the interpretation of all of the symbols of $\mathcal{L}.$
The condition depends on whether the symbol is a constant symbol, function symbol, or relation symbol. For every constant symbol $c\in \mathcal L,$ preservation means

\[\eta \left(c^{\mathcal M}\right) = c^{\mathcal N}.\]

For every $$n$$ -ary function symbol $f\in \mathcal L,$ preservation means that for all $a_1,\dots,a_n\in M,$

\[\eta\left(f^{\mathcal M}(a_1,\dots,a_n)\right) = f^{\mathcal N}(\eta(a_1),\dots,\eta(a_n)).\]

Equivalently, the following diagram commutes:

For every $$n$$ -ary relation symbol $R\in\mathcal L$ , a homomorphism must preserve the relation:

\[(a_1,\dots,a_n)\in R^{\mathcal M} \quad\Longrightarrow\quad \left(\eta(a_1),\dots,\eta(a_n)\right)\in R^{\mathcal N}.\]

If $\eta$ is injective, it is an $\mathcal{L}$ -monomorphism.
An $\mathcal{L}$ -monomorphism is an $\mathcal{L}$ -embedding if it both preserves and reflects relations:

\[(a_1,\dots,a_n)\in R^{\mathcal M} \quad\iff\quad \left(\eta(a_1),\dots,\eta(a_n)\right)\in R^{\mathcal N}.\]

That is, an embedding identifies $\mathcal M$ with the substructure of $\mathcal N$ carried by the subset $\eta(M).$
A bijective $\mathcal{L}$ -embedding is called an $\mathcal{L}$ -isomorphism.

Definition 2.1.4. The set of $\mathcal L$ -terms is the smallest set $\mathcal T$ such that

$c\in \mathcal T$ for each constant symbol $c\in \mathcal C,$
each variable symbol $v_i\in \mathcal T$ for $i=1,2,\dots,$ and
if $t_1,\dots,t_{n_f}\in \mathcal T$ and $f\in \mathcal F,$ then $f(t_1,\dots,t_{n_f})\in \mathcal T.$

For example, $\cdot(v_1, -(v_3,1))$ and $$+1(1, +(1, 1))$$ are $\mathcal L_r$ -terms.

Definition 2.1.5. We say that $\phi$ is an atomic $\mathcal L$ -formula if $\phi$ is either

$$t_1=t_2,$$ where $$t_1$$ and $$t_2$$ are terms, or
$R(t_1,\dots, t_{n_R}),$ where $R\in \mathcal R$ and $t_1,\dots,t_{n_R}$ are terms.

The set of $\mathcal L$ -formulas is the smallest set $\mathcal W$ containing the atomic formulas such that

if $\phi$ is in $\mathcal W,$ then $\neg \phi$ is in $\mathcal W,$
if $\phi$ and $\psi$ are in $\mathcal W,$ then $(\phi \wedge \psi)$ and $(\phi \lor \psi)$ are in $\mathcal W,$ and
if $\phi$ is in $\mathcal W,$ then $\exists v_i\ \phi$ and $\forall v_i\ \phi$ in $\mathcal W.$

We call a formula a sentence if it has no free variables.

Definition 2.1.6. Let $\phi$ be a formula with free variables from $\bar v=(v_{i_1},\dots,v_{i_m}),$ and let $\bar a=(a_{i_1},\dots,a_{i_m})\in M^m.$ We can inductively define $\mathcal M \vDash \phi (\bar a).$ If $\mathcal M \vDash \phi (\bar a)$ we say that $\phi (\bar a)$ is true in $\mathcal M.$

Definition 2.1.7. We say that two $\mathcal L$ -structures $\mathcal M$ and $\mathcal N$ are elementarily equivalent and write $\mathcal M \equiv \mathcal N$ if

\[\mathcal M \vDash \phi \text{ if and only if } \mathcal N \vDash \phi\]

for all $\mathcal L$ -sentences $\phi.$
We let $\text{Th}(\mathcal M),$ the full theory of $\mathcal M,$ be the set of $\mathcal L$ -sentences $\phi$ such that $\mathcal M \vDash \phi.$

Definition 2.1.8. An $\mathcal L$ -theory $$T$$ is simply a set of $\mathcal L$ -sentences. We say that $\mathcal M$ is a model of $$T$$ and write $\mathcal M \vDash T$ if $\mathcal M \vDash \phi$ for all sentences $\phi \in T.$ And, we say that a theory is satisfiable if it has a model.

Definition 2.1.9. We say that a class of $\mathcal L$ structures $\mathcal K$ is an elementary class if there is an $\mathcal L$ -theory such that $\mathcal K=\lbrace \mathcal M: \mathcal M\vDash T\rbrace.$ The elementary class of models of $\text{Th}(\mathcal M)$ is exactly the class of $\mathcal L$ -structures elementarily equivalent to $\mathcal M.$

References

Marker, D. (2002). Model theory: An introduction. Springer. https://doi.org/10.1007/b98860