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
Canonical name	ProofOfDownwardLowenheimSkolemTheorem
Date of creation	2013-03-22 18:18:59
Last modified on	2013-03-22 18:18:59
Owner	GodelsTheorem (21277)
Last modified by	GodelsTheorem (21277)
Numerical id	14
Author	GodelsTheorem (21277)
Entry type	Proof
Classification	msc 03C07