lowenheim-skolem theorem

 

lowenheim-skolem theorem is fundamental theorem to model theory with completeness and compactness theorem. we'll see this theorem for countable lanuage and expand to any infinite cardinal.

 

I assume readers have some set-theoretic knowledge.

 

define $\mathfrak{A}$ is finite iff $|\mathfrak{A}|$ is finite. $\mathcal{L}$ is finite iff the set of symbols is finite

 

(Lowenheim-Skolem for countable language) : If $\Gamma$ of formulas is satisfiable in countable language $\mathcal{L}$, then $\Gamma$ is satisfiable in countable structure $\mathfrak{C}$.

 

proof : by soundness,$\Gamma$ is consistent in $\mathcal{L}$. thus $\Gamma$ is satisfiable in some countable $\mathfrak{C}$ by completeness theorem(remind $\mathfrak{B}$ used in completeness theorem for FOL. we can map one-to-one $\mathfrak{B}$ to $\mathfrak{A}$ using axiom of choice).

 

we can generalize this to any transfinite cardinality. now give up and down theorem.

 

(Upward Lowenheim-Skolem theorem) : let $\Gamma$ be satisfiable in $\mathcal{L}$ where $Card\mathcal{L}=\lambda$ and in infinite structure. then $\Gamma$ is satisfiable in $\mathfrak{A}$ of which cardinality is $\kappa \geq\lambda$ for every $\kappa$.

 

proof : add $C$ a set of new constant symbols where every member of $C$ does not occur in $\mathcal{L} $ and cardinality $\kappa$. define $\Sigma=\{c_{\alpha}\neq c_{\beta}| \alpha\neq\beta, c_{\alpha},c_{\beta} \in C \}$. consider any finite subset of $\Gamma \cup \Sigma$. then we can make some structures satisfying this finite subset(consider infinite structure $T$ for $\Gamma$. then since $T$ is infinite, we can assign finite constant symbols differently). thus by compactness theorem, $\Gamma \cup \Sigma$ is satisfiable. since cardinality of $C$ is $\kappa$, $\Gamma \cup \Sigma$ is satisfiable in some structure whose cardinality is at least $\kappa$.

 

for above, we need compactness theorem for arbitrary language;thus completeness for arbitrary(i don't prove this here. you can use same method used in countable. different thing is for uncountable, you've to use ordinal numbers&zorn's lemma)

 

(Downward Lowenheim-Skolem theorem) : let $\Gamma$ be satisfiable in $\mathcal{L}$ where $Card\mathcal{L}=\lambda$ and in infinite structure. then $\Gamma$ is satisfiable in $\mathfrak{A}$ of which cardinality is $\kappa \leq \lambda$.

 

proof : consider lowenheim-skolem theorem for countable language. same method is used for uncountable and arbitrarily large cardinals if we know completeness for arbitrary language.

 

(Full Lowenheim-Skolem theorem) Let $\Gamma$ be satisfiable in a language $\mathcal{L}$ of transfinite cardinality $\lambda$. If $\Gamma$ is satisfiable in some infinite structures and $\lambda \leq \kappa$, there exists a structure $\mathfrak{A}$ whose cardinality is exactly $\kappa$($\kappa$ is any cardinal satisfying above).

 

proof : use 'up and down' lowenheim-skolem theorem.