PlanetMath: proof of downward Lowenheim-Skolem theorem

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (232)
Orphanage
Unclass'd
Unproven (519)
Corrections (22)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Entry average rating: No information on entry rating

proof of downward Lowenheim-Skolem theorem

(Proof)

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 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 -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 -formula $\phi(\emph{x},y)$ with $a \in A$ and $b \in B$ , we have $\mathcal{B}\models \phi(a,b)$ <-> For some $a' \in A$ we have $\mathcal{A}\models \phi(a,a')$

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 -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' \in A$ such that $\mathcal{A}\models \phi(p,p')$ if such a exists and otherwise. The set of Skolem functions has a cardinality equal to that of .

The purpose here is to construct a model $\mathcal{B}$ whose domain 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 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 and thus $\mathcal{B}$ meets the requirements of Tarski's Lemma. We can find an elementary substructure of $\mathcal{A}$ .

Let's take of above and set 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 is closed under Skolem functions. And we have $\vert K\vert\leq \omega .\vert L\vert+\vert K\vert= \vert L\vert+\vert K\vert$ . This comes from the fact that $\vert L\vert+\vert K_i\vert=\vert\emph{SF}\vert+\vert K_i\vert= \sum_{k \in \m... ..._k\vert+\vert K_i\vert= \sum_{k \in \mathbb{N} }\vert(SF)_k\vert*\vert K_i\vert$ but we have $\vert K_{i+1}\vert \leq \sum_{k \in \mathbb{N} }\vert(SF)_k\vert*\vert K_i\vert$ . We need now to provide interpretations of relations, predicates, functions and constants so it can fit $\mathcal{A}$ .