proof of downward Lowenheim-Skolem theorem

We present here a proof of the Downward Lowenheim Skolem Theorem. The idea is to construct a submodel that meets the requirements of the DLS Theorem: we take $K$ and close it under a procedure of choosing appropriate witnesses for the existential formulas satisfied by $𝒜$. Choosing the appropriate witnesses is done with the help of the so-called Skolem functions and thus rests upon the choice function.

Proof: First of all we introduce a usefull tool for the proof.Lemma: (Tarski’s Lemma) If $𝒜$ and $ℬ$ are $L$-structures with the domain of $𝒜$ being a subset of the domain of $ℬ$ then $𝒜$ is an elementary substructure of $ℬ$ if for every $L$-formula $\varphi (\text{<em class="ltx\_emph ltx\_font\_italic">x</em>},y)$ with $a\in A$ and $b\in B$, we have$ℬ\vDash \varphi (a,b)$ ¡-¿ For some $a^{\prime }\in A$ we have $𝒜\vDash \varphi (a,a^{\prime })$

Proof. Let’s supposes the biconditionnal holds, then we need to show that $𝒜$ is a substructure of $ℬ$. This means that we need to show that every formula that is true in $𝒜$ is true in $ℬ$. The proof is straighforward with an induction on the complexity of formulas (connectives, negation, quantifiers).

Now, fix a point $p\in dom(𝒜)$. For each $L$-formula $\varphi (\text{<em class="ltx\_emph ltx\_font\_italic">x</em>},y)$, define the Skolem function of $\varphi$, $g_{\varphi }:A^n\to A$ (with $A=dom(𝒜)$) by:

$p\in A^n\to$ some $p^{\prime }\in A$ such that $𝒜\vDash \varphi (p,p^{\prime })$ if such a $p^{\prime }$ exists and $p$ otherwise.The set of Skolem functions has a cardinality equal to that of $L$.

The purpose here is to construct a model $ℬ$ whose domain $B$ is closed under the skolem functions. This means that the domain of $𝒜$ contains all the witnesses we’ve appropriately choosen. If we take an existential formula $\exists y\varphi (\text{<em class="ltx\_emph ltx\_font\_italic">x</em>},y)$ and $b\in B^k$ and if we apply the Skolem function to $b$ we will have a witness for $\exists x\varphi (\text{<em class="ltx\_emph ltx\_font\_italic">b</em>},x)$. In other words, this means that $𝒜\vDash \exists x\varphi (b,x)\to 𝒜\vDash \varphi (b,g_{\varphi }(b))$. By construction $g_{\varphi }(b)$ is in $B$ and thus $ℬ$ meets the requirements of Tarski’s Lemma. We can find an elementary substructure of $𝒜$.

Let’s take $K$ of above and set $K_0:=K$ and $K_{i+1}$ is the set of the $g_{\varphi }(p),p\in K_i\wedge g_{\varphi }$ (with $g_{\varphi }$ a Skolem function). Let $B:=\bigcup K_i$. Then $B$ is closed under Skolem functions. And we have $|K|\le \omega .|L|+|K|=|L|+|K|$. This comes from the fact that $|L|+|K_i|=|\text{<em class="ltx\_emph ltx\_font\_italic">SF</em>}|+|K_i|={\sum }_{k\in \mathbb{N}}|{(SF)}_k|+|K_i|={\sum }_{k\in \mathbb{N}}|{(SF)}_k|*|K_i|$ but we have $|K_{i+1}|\le {\sum }_{k\in \mathbb{N}}|{(SF)}_k|*|K_i|$.We need now to provide interpretations of relations, predicates, functions and constants so it can fit $𝒜$.

We have because $B$ is closed under $L$-terms and for an $L$-function symbol $f$, the Skolem function of the $L$-formula $f(x)=y$ takes the value $f^{𝒜}(p)$ at p:

for any n-ary relation symbol $P$: $P^{ℬ}=P^{𝒜}\bigcap B^n$

for an m-ary function symbol $f$ and $p\in B^m,p^{\prime }\in B$ we have $f^{𝒜}(p)=p^{\prime }$ ¡-¿ $f^{ℬ}(p)=p^{\prime }$.

for a constant symbol $c$, we have $c^{𝒜}=c^{ℬ}$ We have constructed a substructure $ℬ$ of $𝒜$.