# 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 $\mathcal{A}$. 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 $\mathcal{A}$ and $\mathcal{B}$ are $L$-structures with the domain of $\mathcal{A}$ being a subset of the domain of $\mathcal{B}$ then $\mathcal{A}$ is an elementary substructure of $\mathcal{B}$ if for every $L$-formula $\phi(\emph{x},y)$ with $a\in A$ and $b\in B$, we have $\mathcal{B}\models\phi(a,b)$ ¡-¿ For some $a^{\prime}\in A$ we have $\mathcal{A}\models\phi(a,a^{\prime})$

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

Now, fix a point $p\in{dom}(\mathcal{A})$. For each $L$-formula $\phi(\emph{x},y)$, define the Skolem function of $\phi$, $g_{\phi}:A^{n}\to A$ (with $A={dom}(\mathcal{A})$) by:

$p\in A^{n}\to$ some $p^{\prime}\in A$ such that $\mathcal{A}\models\phi(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 $\mathcal{B}$ whose domain $B$ is closed under the skolem functions. This means that the domain of $\mathcal{A}$ contains all the witnesses we’ve appropriately choosen. If we take an existential formula $\exists y\phi(\emph{x},y)$ and $b\in B^{k}$ and if we apply the Skolem function to $b$ we will have a witness for $\exists x\phi(\emph{b},x)$. In other words, this means that $\mathcal{A}\models\exists x\phi(b,x)\to\mathcal{A}\models\phi(b,g_{\phi}(b))$. By construction $g_{\phi}(b)$ is in $B$ and thus $\mathcal{B}$ meets the requirements of Tarski’s Lemma. We can find an elementary substructure of $\mathcal{A}$.

Let’s take $K$ of above and set $K_{0}:=K$ and $K_{i+1}$ is the set of the $g_{\phi}(p),p\in K_{i}\wedge g_{\phi}$ (with $g_{\phi}$ a Skolem function). Let $B:=\bigcup K_{i}$. Then $B$ is closed under Skolem functions. And we have $|K|\leq\omega.|L|+|K|=|L|+|K|$. This comes from the fact that $|L|+|K_{i}|=|\emph{SF}|+|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}|\leq\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 $\mathcal{A}$.

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^{\mathcal{A}}(p)$ at p:

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

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

for a constant symbol $c$, we have $c^{\mathcal{A}}=c^{\mathcal{B}}$ We have constructed a substructure $\mathcal{B}$ of $\mathcal{A}$.

Title proof of downward Lowenheim-Skolem theorem ProofOfDownwardLowenheimSkolemTheorem 2013-03-22 18:18:59 2013-03-22 18:18:59 GodelsTheorem (21277) GodelsTheorem (21277) 14 GodelsTheorem (21277) Proof msc 03C07