models constructed from constants

The definition of a structure and of the satisfaction relation isnice, but it raises the following question : how do we get models inthe first place? The most basic construction for models offirst-order theory is the construction that uses constants. Throughoutthis entry, $L$ is a fixed first-order language.

Let $C$ be a set of constant symbols of $L$, and $T$ be a theory in$L$. Then we say $C$ is a set of witnesses for $T$ if and onlyif for every formula $\phi$ with at most one free variable $x$,we have $T⊢\exists x(\phi )\Rightarrow \phi (c)$ for some $c\in C$.

Lemma.Let $T$ is any consistentset of sentences of $L$, and $C$ is a set of new symbolssuch that $|C|=|L|$. Let $L^{\prime }=L\cup C$. Then there is a consistentset $T^{\prime }\subseteq L^{\prime }$ extending $T$ and which has $C$ as set ofwitnesses.

Lemma.If $T$ is a consistent theory in $L$, and $C$ is a set of witnessesfor $T$ in $L$, then $T$ has a model whose elements are the constantsin $C$.

Proof:Let $\mathrm{\Sigma }$ be the signature for $L$. If $T$ is a consistent set ofsentences of $L$, then there is a maximal consistent $T^{\prime }\supseteq T$.Note that $T^{\prime }$ and $T$ have the same sets of witnesses. As everymodel of $T^{\prime }$ is also a model of $T$, we may assume $T$ is maximalconsistent.

We let the universe of $𝔐$ be the set of equivalence classes$C/\sim$, where $a\sim b$ if and only if $\text{“}a=b\text{”}\in T$. As $T$ ismaximal consistent, this is an equivalence relation. We interpret thenon-logical symbols as follows :

1. $[a]{=}^{𝔐}[b]$ if and only if $a\sim b$;

2. Constant symbols are interpreted in the obvious way, i.e. if$c\in \mathrm{\Sigma }$ is a constant symbol, then $c^{𝔐}=[c]$;

3. If $R\in \mathrm{\Sigma }$ is an $n$-ary relation symbol, then$([a_1],\mathrm{\dots },[a_n])\in R^{𝔐}$ if and only if $R(a_1,\mathrm{\dots },a_n)\in T$;

4. If $F\in \mathrm{\Sigma }$ is an $n$-any function symbol, then$F^{𝔐}([a_0],\mathrm{\dots },[a_n])=[b]$ if and only if $\text{“}F(a_1,\mathrm{\dots },a_n)=b\text{”}\in T$.

From the fact that $T$ is maximal consistent, and $\sim$ is anequivalence relation, we get that the operations are well-defined (itis not so simple, i’ll write it out later).The proof that $𝔐\vDash T$ is a straightforward induction on thecomplexity of the formulas of $T$. $\mathrm{♢}$

Corollary.(The extended completeness theorem) A set $T$ of formulas of $L$ isconsistent if and only if it has a model (regardless of whether or not$L$ has witnesses for $T$).

Proof:First add a set $C$ of new constants to $L$, and expand $T$ to $T^{\prime }$ insuch a way that $C$ is a set of witnesses for $T^{\prime }$. Then expand $T^{\prime }$to a maximal consistent set $T^{\prime \prime }$. This set has a model $𝔐$ consisting ofthe constants in $C$, and $𝔐$ is also a model of $T$. $\mathrm{♢}$

Corollary.(Compactness theorem) A set $T$ of sentences of $L$ has a model ifand only if every finite subset of $T$ has a model.

Proof:Replace “has a model” by “is consistent”, and apply the syntacticcompactness theorem. $\mathrm{♢}$

Corollary.(Gödel’s completeness theorem)Let $T$ be a consistent set of formulas of $L$. ThenA sentence $\phi$ is a theorem of $T$ if and only if it is true inevery model of $T$.

Proof:If $\phi$ is not a theorem of $T$, then $\mathrm{\neg }\phi$ is consistentwith $T$, so $T\cup \{\mathrm{\neg }\phi \}$ has a model $𝔐$, in which$\phi$ cannot be true. $\mathrm{♢}$

Corollary.(Downward Löwenheim-Skolem theorem) If $T\subseteq L$ has a model,then it has a model of power at most $|L|$.

Proof:If $T$ has a model, then it is consistent. The model constructed fromconstants has power at most $|L|$ (because we must add at most $|L|$many new constants). $\mathrm{♢}$

Most of the treatment found in this entry can be read in more detailsin Chang and Keisler’s book Model Theory.