Muhammad Haris Rao
Thorughout, we will fix a first-order language $\mathcal{L}$ with constant symbols $\mathcal{C}$, relational symbols $\mathcal{R}$, and function symbols $\mathcal{F}$.
Definition: An $\mathcal{L}$-structure $\mathfrak{A}$ is specified by the following information:
These structures over which we interpret our first-order languages are the central objects of study of model theory. As is common in many parts of mathematics, we would like to be able to compare these objects of study through maps between them.
Definition: Let $\mathfrak{A}, \mathfrak{B}$ be $\mathcal{L}$-structures with universes $A, B$ respectively. An $\mathcal{L}$-embedding of $\mathfrak{A}$ into $\mathfrak{B}$ is an injective function $\Phi : A \longrightarrow B$ such that
An $\mathcal{L}$-isomorphism is a bijective $\mathcal{L}$-embedding.
We will abuse notation a little bit an write an $\mathcal{L}$-embededing of one $\mathcal{L}$-structure $\mathfrak{A}$ into another $\mathfrak{B}$ as $\Phi : \mathfrak{A} \longrightarrow \mathfrak{B}$ even though $\varphi$ is a function between their universes.
Definition: Let $\mathfrak{A}, \mathfrak{B}$ be $\mathcal{L}$-structures. We say that $\mathfrak{A}$ is a substructure of $\mathfrak{B}$ if there exists an $\mathcal{L}$-embedding $\Phi : \mathfrak{A} \longrightarrow \mathfrak{B}$. In this case, $\varphi$ is an embedding of $\mathfrak{A}$ into $\mathfrak{B}$, and $\mathfrak{B}$ is an extension of $\mathfrak{A}$.
Definition: Given an $\mathcal{L}$-structure $\mathfrak{A}$, an assignment is a function $\sigma : \texttt{Var} \longrightarrow A$ where $A$ is the universe of $\mathfrak{A}$. Given two assignments $\sigma, \tau : \tt{Var} \longrightarrow A$ and variable $x \in \tt{Var}$, we say that $\tau$ is an $x$-variant of $\sigma$, denoted $\sigma \sim_x \tau$, if for all $y \in \tt{Var}$ with $y \ne x$, $\sigma(y) = \tau(y)$.
Again, we will often write $\sigma : \texttt{Var} \longrightarrow \mathfrak{A}$ even though the codomain is really the universe of $\mathfrak{A}$.
In the previous section, what we did was assign some sort of meaning to the language $\mathcal{L}$ which was until now, just a collection of meaningless symbols which can be used to form strings and formulas according to strict syntactic rules. The symbols have been interpretted on an underlying universe so that each constant symbol corresponds to an element of this universe, each relation symbol a relation betwen elements of this universe, each function symbol a function taking arguments from and values in this universe.
What we want to do next is to interpret $\mathcal{L}$-terms, so that they 'refer' to things in the universe. This is done in the following way:
Definition: Let $\mathfrak{A}$ be an $\mathcal{L}$-structure. If $t \in \texttt{Term} \left( \mathcal{L} \right)$ is an $\mathcal{L}$ term, and $\sigma : \texttt{Var} \longrightarrow \mathfrak{A}$ an assignment, then $t$ is interpretted in $\mathfrak{A}$ as follows:
Now that we have given meaning to the symbols of $\mathcal{L}$ and interpretted onto an $\mathcal{L}$-structure and interpretted $\mathcal{L}$-terms so that they refer to things in the underlying universe of this structure, we want to be able to say things about this structure using the language. This is what formulas do: they say things about the structure. In particular, they have truth values depending on whether what they are saying about the structure holds or not. Precisely, we have
Definition: Let $\mathfrak{A}$ be an $\mathcal{L}$-structure and $\sigma : \texttt{Var} \longrightarrow \mathfrak{A}$ an assignment. If $\varphi \in \texttt{Form} \left( \mathcal{L} \right)$, we define $\mathfrak{A} \models \varphi (\sigma)$ as follows:
Definition: Let $\Gamma \subseteq \text{Form}(\mathcal{L}$) be a set of $\mathcal{L}$-formulas, and $\varphi \in \texttt{Form}(\mathcal{L})$ an $\mathcal{L}$-formula. We say that $\varphi$ is a semantic consequence of $\Gamma$, written $\Gamma \models \varphi$, if whenever $\mathfrak{A}$ is an $\mathcal{L}$-strucutre such that $\mathfrak{A} \models \psi$ for every $\psi \in \Gamma$, then also $\mathfrak{A} \models \varphi$.
We say that an $\mathcal{L}$-sentence $\varphi \in \texttt{Sent}(\mathcal{L})$ is valid if it is a semantic consequence of the empty set of premises, notated as $\models \varphi$.
We say that a collection of $\mathcal{L}$-sentences $\Gamma \subseteq \texttt{Sent}(\mathcal{L})$ is unsatisfiable if the falsum is a semantic consequence of the singleton set of premises consisting of just $\varphi$, notated as $\Gamma \models (\bot)$. We say that $\Gamma$ is satisfiable if it is not unsatisfiable.
That is to say, an $\mathcal{L}$-formula is valid if it is true in every $\mathcal{L}$-structure, and unsatisfiable if it is false in every $\mathcal{L}$-structure. Clearly, an $\mathcal{L}$-formula $\varphi \in \texttt{Form}(\mathcal{L})$ is valid if and only if $(\neg \varphi)$ is unsatisfiable, and unsatisfiable if and only if $(\neg \varphi)$ is valid.
It should be noted that in making the definition of an interpretation, we need the unique reading lemma which guarantees that exactly one of the cases above will hold. It would be a problem if multiple cases could apply for a single formula because then it might be possible that two cases give different answers as to whether the formula should be interpretted as true or not in the structure. Which would of course be a disaster.
Given an $\mathcal{L}$-structure $\mathfrak{A}$, we define its theory to be $$ \text{Th} \left( \mathfrak{A} \right) = \left\{ \varphi \in \texttt{Sent}\left( \mathcal{L} \right) \mid \mathfrak{A} \models \varphi(\sigma) \text{ for every $\sigma : \texttt{Var} \longrightarrow \mathfrak{A}$} \right\} $$
Definition: Let $\mathfrak{A}, \mathfrak{B}$ be $\mathcal{L}$-structures. We say that $\mathfrak{A}$, $\mathfrak{B}$ are elementarily equivalent, written $\mathfrak{A} \equiv \mathfrak{B}$, if $\text{Th} \left( \mathfrak{A} \right) = \text{Th} \left( \mathfrak{B} \right)$
We say that $\mathfrak{A}$ is an elementary substructure of $\mathfrak{B}$ if there exists an $\mathcal{L}$-embedding $\Phi : \mathfrak{A} \longrightarrow \mathfrak{B}$ such that for every $\mathcal{L}$-formula $\varphi \in \texttt{Form}(\mathcal{L})$ and assignment $\sigma : \texttt{Var} \longrightarrow \mathfrak{A}$, $$ \mathfrak{A} \models \varphi(\sigma) \text{ if and only if } \mathfrak{B} \models \varphi(\Phi \circ \sigma) $$ In this case, $\varphi$ is an elementary embedding of $\mathfrak{A}$ into $\mathfrak{B}$, $\mathfrak{B}$ is an elementary extention of $\mathfrak{A}$, and we write $\mathfrak{A} \preceq \mathfrak{B}$.
Proposition: Let $\mathfrak{A}$ be an $\mathcal{L}$-structure and $\sigma, \tau : \texttt{Var} \longrightarrow \mathfrak{A}$ two assignments. If $t \in \tt{Term}(\mathcal{L})$ is an $\mathcal{L}$-term such that $\sigma(x) = \tau(x)$ for every $x \in \text{fv}(t)$, then $t^\mathfrak{A}(\sigma) = t^\mathfrak{A}(\tau)$.
Proof. As usual, we induct on the complexity of the term.
If there is $c \in \mathcal{C}$ such that $t = c$ then we have $t^\mathfrak{A}(\sigma) = c^\mathfrak{A} = t^\mathfrak{A}(\tau)$.
If there is $x \in \tt{Var}$ such that $t = x$, then $x \in \text{fv}(t)$. So $\sigma(x) = \tau(x)$. Thus, $t^\mathfrak{A}(\sigma) = \sigma(x) = \tau(x) = t^\mathfrak{A}(\tau)$.
Now suppose there is $f \in \mathcal{F}$ and $\mathcal{L}$-terms $t_1, t_2, \cdots, t_{n_f} \in \tt{Term}(\mathcal{L})$ such that $t = f t_1 t_2 \cdots t_{n_f}$. We assume as the induction hypothesis that the desired result holds on terms of lower complexity that $t$. In particular, for each $k \in \{ 1, 2, \cdots, n_f \}$, $t_k$ is an $\mathcal{L}$-term of lower complexity that $t$ and also $\text{var}(t_k) \subseteq \bigcup_{i = 1}^n \text{var}(t_i) = \text{var}(t)$ so we will have $t_k^\mathfrak{A}(\sigma) = t_k^\mathfrak{A}(\tau)$. Then, $$ t^\mathfrak{A}(\sigma) = f^\mathfrak{A} \left( t_1^\mathfrak{A}(\sigma), t_2^\mathfrak{A}(\sigma), \cdots, t_{n_f}^\mathfrak{A}(\sigma) \right) = f^\mathfrak{A} \left( t_1^\mathfrak{A}(\tau), t_2^\mathfrak{A}(\tau), \cdots, t_{n_f}^\mathfrak{A}(\tau) \right) = t^\mathfrak{A}(\tau) $$ This completes all the cases, so we are done. $\blacksquare$
Proposition: Let $\varphi \in \texttt{Form}(\mathcal{L}$ be an $\mathcal{L}$-formula, and $\mathfrak{A}$ an $\mathcal{L}$-structure. If $\sigma, \tau : \texttt{Var} \longrightarrow \mathfrak{A}$ are two assignments such that $\sigma(x) = \tau(x)$ for every $x \in \text{fv}(\varphi)$, then $\mathfrak{A} \models \varphi(\sigma)$ if and only if $\mathfrak{A} \models \varphi(\tau)$.
Proof. First to deal with the atomic formulas. If $\varphi = (\bot)$ then the formula is always false in the model regardless of the assignment.
If there are $\mathcal{L}$-terms $t_1, t_2 \in \tt{Term}(\mathcal{L})$ such that $\varphi = (t_1 \doteq t_2)$, then applying the previous analogous result for $\mathcal{L}$-terms which tells us that $t_k^\mathfrak{A}(\sigma) = t_k^\mathfrak{A}(\tau)$ for $k \in \{ 1, 2 \}$, it follows that \begin{align*} \mathfrak{A} \models \varphi(\sigma) &\text{ if and only if } t_1^\mathfrak{A}(\sigma) = t_2^\mathfrak{A}(\sigma) \\ &\text{ if and only if } t_1^\mathfrak{A}(\tau) = t_2^\mathfrak{A}(\tau) \\ &\text{ if and only if } \mathfrak{A} \models \varphi(\tau) \end{align*}
If there is a relation symbol $R \in \mathcal{R}$ and $\mathcal{L}$-terms $t_1, t_2, \cdots, t_{n_R} \in \tt{Term}(\mathcal{L})$ such that $\varphi = (R t_1 t_2 \cdots t_{n_R})$, then we have for all $k \in \{ 1, 2, \cdots, n_R \}$ that $$ \text{var}(t_k) \subseteq \bigcup_{i = 1}^n \text{var}(t_i) = \text{fv}(\varphi) $$ so that $t_k^\mathfrak{A}(\sigma) = t_k^\mathfrak{A}(\tau)$. Hence, \begin{align*} \mathfrak{A} \models \varphi(\sigma) &\text{ if and only if } \left( t_1^\mathfrak{A}(\sigma), t_2^\mathfrak{A}(\sigma), \cdots, t_{n_R}^\mathfrak{A}(\sigma) \right) \in R^\mathfrak{A} \\ &\text{ if and only if } \left( t_1^\mathfrak{A}(\tau), t_2^\mathfrak{A}(\tau), \cdots, t_{n_R}^\mathfrak{A}(\tau) \right) \in R^\mathfrak{A} \\ &\text{ if and only if } \mathfrak{A} \models \varphi(\tau) \end{align*} This completes all the cases for the atomic formulas. From now, we take as the induction hypothesis that the result above holds for every $\mathcal{L}$-formula of lower complexity that $\varphi$.
If there is an $\mathcal{L}$-formula $\psi \in \tt{Form}(\mathcal{L})$ such that $\varphi = (\neg \psi)$, then $\text{fv}(\psi) = \text{fv}(\varphi)$ so by applying the induction hypothesis on $\psi$, we have \begin{align*} \mathfrak{A} \models \varphi(\sigma) &\text{ if and only if } \mathfrak{A} \not\displaystyle\models \psi(\sigma) \\ &\text{ if and only if } \mathfrak{A} \not\displaystyle\models \psi(\tau) \\ &\text{ if and only if } \mathfrak{A} \models \varphi(\tau) \end{align*}
If there are $\mathcal{L}$-formulas $\psi, \chi \in \tt{Form}(\mathcal{L})$ such that $\varphi = (\psi \wedge \chi)$, then $\text{fv}(\psi), \text{fv}(\chi) \subseteq \text{fv}(\varphi)$ so by applying the induction hypothesis on $\psi, \chi$, we have \begin{align*} \mathfrak{A} \models \varphi(\sigma) &\text{ if and only if } \mathfrak{A} \models \psi(\sigma) \text{ and } \mathfrak{A} \models \chi(\sigma) \\ &\text{ if and only if } \mathfrak{A} \models \psi(\tau) \text{ and } \mathfrak{A} \models \chi(\tau) \\ &\text{ if and only if } \mathfrak{A} \models \varphi(\tau) \end{align*}
If there are $\mathcal{L}$-formulas $\psi, \chi \in \tt{Form}(\mathcal{L})$ such that $\varphi = (\psi \vee \chi)$, then $\text{fv}(\psi), \text{fv}(\chi) \subseteq \text{fv}(\varphi)$ so by applying the induction hypothesis on $\psi, \chi$, we have \begin{align*} \mathfrak{A} \models \varphi(\sigma) &\text{ if and only if } \mathfrak{A} \models \psi(\sigma) \text{ or } \mathfrak{A} \models \chi(\sigma) \\ &\text{ if and only if } \mathfrak{A} \models \psi(\tau) \text{ or } \mathfrak{A} \models \chi(\tau) \\ &\text{ if and only if } \mathfrak{A} \models \varphi(\tau) \end{align*}
If there are $\mathcal{L}$-formulas $\psi, \chi \in \tt{Form}(\mathcal{L})$ such that $\varphi = (\psi \to \chi)$, then $\text{fv}(\psi), \text{fv}(\chi) \subseteq \text{fv}(\varphi)$ so by applying the induction hypothesis on $\psi, \chi$, we have \begin{align*} \mathfrak{A} \models \varphi(\sigma) &\text{ if and only if } \mathfrak{A} \not\displaystyle\models \psi(\sigma) \text{ or } \mathfrak{A} \models \chi(\sigma) \\ &\text{ if and only if } \mathfrak{A} \not\displaystyle\models \psi(\tau) \text{ or } \mathfrak{A} \models \chi(\tau) \\ &\text{ if and only if } \mathfrak{A} \models \varphi(\tau) \end{align*} This completes all the cases for binary connectives. Now to deal with the quantifiers.
Suppose there is an $\mathcal{L}$-formula and variable $x \in \tt{Var}$ such that $\varphi = (\forall x \, \psi)$. Suppose further that $\mathfrak{A} \models \varphi(\sigma)$.
Given any $\tau^\prime : \tt{Var} \longrightarrow \mathfrak{A}$ such that $\tau^\prime \sim_x \tau$, define $\sigma^\prime : \tt{Var} \longrightarrow \mathfrak{A}$ at $y \in \tt{Var}$ by $$ \sigma^\prime(y) = \begin{cases} \tau^\prime(y) &\text{ , if $y \in \text{fv}(\psi)$} \\ \sigma(y) &\text{ , if $y \notin \text{fv}(\psi)$} \end{cases} $$ Then if $y \ne x$, we have $\sigma^\prime(y) = \sigma(y)$ if $y \notin \text{fv}(\psi)$ and otherwise if $y \in \text{fv}(\psi)$, then $\sigma^\prime(y) = \tau^\prime(y)$ by the above definition, $\tau^\prime(y) = \tau(y)$ since $\tau^\prime \sim_x \tau$ and $y \ne x$, and $\tau(y) = \sigma(y)$ since $y \in \text{fv}(\psi) \backslash \{ x \} = \text{fv}(\varphi)$ and $\sigma, \tau$ agree on $\text{fv}(\varphi)$. So for all $y \in \tt{Var}$ with $y \ne x$, we have $\sigma(y) = \sigma^\prime(y)$ so that $\sigma^\prime \sim_x \sigma$. Then, because $\mathfrak{A} \models \varphi(\sigma)$, it follows that $\mathfrak{A} \models \psi (\sigma^\prime)$. From definition of $\sigma^\prime$, we have that $\sigma^\prime, \tau^\prime$ agree on $\text{fv}(\psi)$, so by consequence of induction hypothesis, we have $\mathfrak{A} \models \psi(\tau^\prime)$. This works for any $x$-variant $\tau^\prime$ of $\tau$, so we can conclude that $\mathfrak{A} \models \varphi (\tau)$.
The other implication follows by symmetry, so we conclude that $\mathfrak{A} \models \varphi(\sigma)$ if and only if $\mathfrak{A} \models \varphi(\tau)$.
Suppose there is an $\mathcal{L}$-formula and variable $x \in \tt{Var}$ such that $\varphi = (\exists x \, \psi)$. Suppose further that $\mathfrak{A} \models \varphi(\sigma)$.
This means there is $\sigma^\prime : \tt{Var} \longrightarrow \mathfrak{A}$ such that $\mathfrak{A} \models \psi(\sigma^\prime)$. Define define $\tau^\prime : \tt{Var} \longrightarrow \mathfrak{A}$ at $y \in \tt{Var}$ by $$ \tau^\prime(y) = \begin{cases} \sigma^\prime(y) &\text{ , if $y \in \text{fv}(\psi)$} \\ \tau(y) &\text{ , if $y \notin \text{fv}(\psi)$} \end{cases} $$ By precisely the same argument as before, we have $\tau^\prime \sim_x \tau$ and also $\tau^\prime, \sigma^\prime$ agree on $\text{fv}(\psi)$. Because of the latter fact and the induction hypothesis, $\mathfrak{A} \models \psi(\tau^\prime)$ since $\mathfrak{A} \models \varphi(\sigma^\prime)$. Then because $\tau^\prime \sim_x \tau$, it follows that $\mathfrak{A} \models \varphi(\tau)$.
Again, the other implication follows by symmetry, so we conclude that $\mathfrak{A} \models \varphi(\sigma)$ if and only if $\mathfrak{A} \models \varphi(\tau)$.
This completes all the cases, so we are now done. $\blacksquare$
The above fact justifies a notational convention. Recall that given $v_1, v_2, \cdots, v_n \in \tt{Var}$ for some $n \in \mathbb{Z}_{\ge 0}$ and an $\mathcal{L}$-formula $\varphi \in \tt{Form}(\mathcal{L})$, we will write $\varphi(v_1, v_2, \cdots, v_n)$ to mean that $\text{fv}(\varphi) \subseteq \{ v_1, v_2, \cdots, v_n \}$. Then given $a_i \in \mathfrak{A}$ for $i \in \{ 1, 2, \cdots, n \}$, we will write $\mathfrak{A} \models \varphi(a_1, a_2, \cdots, a_n)$ to mean $\mathfrak{A} \models \varphi(\sigma)$ where $\sigma : \tt{Var} \longrightarrow \mathfrak{A}$ is any assignment such that $\sigma(v_i) = a_i$ for $i \in \{ 1, 2, \cdots, n \}$. By the above proposition, there is no ambiguity introduced with this convention.
In particular, if $\varphi \in \tt{Sent}(\mathcal{L})$ is an $\mathcal{L}$-sentance and $\mathfrak{A}$ an $\mathcal{L}$-structure, there is no ambiguity in writing $\mathfrak{A} \models \varphi$ without specifying the assignment of variables. In particular, we can write $$ \text{Th} \left( \mathfrak{A} \right) = \left\{ \varphi \in \texttt{Sent} \mid \mathfrak{A} \models \varphi \right\} $$