# models constructed from constants

The definition of a structure and of the satisfaction relation is nice, but it raises the following question : how do we get models in the first place? The most basic construction for models of first-order theory is the construction that uses constants. Throughout this 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 only if for every formula $\varphi$ with at most one free variable $x$, we have $T\vdash\exists x(\varphi)\Rightarrow\varphi(c)$ for some $c\in C$.

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

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

Proof: Let $\Sigma$ be the signature for $L$. If $T$ is a consistent set of sentences 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 every model of $T^{\prime}$ is also a model of $T$, we may assume $T$ is maximal consistent.

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

1. 1.

$[a]=^{\mathfrak{M}}[b]$ if and only if $a\sim b$;

2. 2.

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

3. 3.

If $R\in\Sigma$ is an $n$-ary relation symbol, then $([a_{1}],...,[a_{n}])\in R^{\mathfrak{M}}$ if and only if $R(a_{1},...,a_{n})\in T$;

4. 4.

If $F\in\Sigma$ is an $n$-any function symbol, then $F^{\mathfrak{M}}([a_{0}],...,[a_{n}])=[b]$ if and only if $\text{}F(a_{1},...,a_{n})=b\text{''}\in T$.

From the fact that $T$ is maximal consistent, and $\sim$ is an equivalence relation, we get that the operations are well-defined (it is not so simple, i’ll write it out later). The proof that $\mathfrak{M}\models T$ is a straightforward induction on the complexity of the formulas of $T$. $\diamondsuit$

(The extended completeness theorem) A set $T$ of formulas of $L$ is consistent 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}$ in such 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 $\mathfrak{M}$ consisting of the constants in $C$, and $\mathfrak{M}$ is also a model of $T$. $\diamondsuit$

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

Proof: Replace “has a model” by “is consistent”, and apply the syntactic compactness theorem. $\diamondsuit$

Corollary. (Gödel’s completeness theorem) Let $T$ be a consistent set of formulas of $L$. Then A sentence $\varphi$ is a theorem of $T$ if and only if it is true in every model of $T$.

Proof: If $\varphi$ is not a theorem of $T$, then $\neg\varphi$ is consistent with $T$, so $T\cup\{\neg\varphi\}$ has a model $\mathfrak{M}$, in which $\varphi$ cannot be true. $\diamondsuit$

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 from constants has power at most $|L|$ (because we must add at most $|L|$ many new constants). $\diamondsuit$

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

Title models constructed from constants ModelsConstructedFromConstants 2013-03-22 12:44:42 2013-03-22 12:44:42 ratboy (4018) ratboy (4018) 17 ratboy (4018) Definition msc 03C07 completeness theorem Gödel completeness theorem UpwardsSkolemLowenheimTheorem set of witnesses