0
$\begingroup$

I understand the formal proof of the Downwards Lowenheim-Skolem Theorem, and could probably reproduce it if I were asked to, but I'm not so certain about the intuition behind the proof and what we're "doing" in the proof. From what I understand, it works by taking some countable subset of a model and recursively adding all definable sets from the previous level. This produces a countable model (assuming the language is countable) because our base set was countable, the language only has countable many formulas, and there are only countably many levels. Am I mistaken? Could anyone explain where my explanation fails?

$\endgroup$
1
  • 4
    $\begingroup$ I don't usually think of it in terms of adding definable sets, but rather adding a witness for each existential sentence with parameters from the previous level (or similarly, in one go, taking the closure under a set of Skolem functions). It would be good to attach a proof, or at least a sketch as a reference here, so we're all on the same page, since the theorem can be proved in different ways. $\endgroup$ Jul 3 at 5:17

1 Answer 1

4
$\begingroup$

Welcome to mse ^_^

This is definitely the right intuition. Let's look at an instructive simplified example: subgroups.

Say $S \subseteq G$, and we want to find the smallest subgroup of $G$ containing $S$. How can we build such a subgroup? Well, on day $0$ start with $S$. On day $1$, we add in all the $s^{-1}$ and all the $s_1 s_2$ from things we started with on day $0$. On day $2$, we add in inverses and products for things we had on day $1$. In general, on day $n+1$ we add in inverses and products of things that existed on day $n$. We say the first day on which $s$ shows up is the birthday of $s$.

Then let's look at all the elements which show up eventually. This is closed under inverses, since (by assumption) each element has a birthday, say day $n$, and then its inverse must have been added on day $n+1$. Similarly, if $s_1$ and $s_2$ exist, then they have birthdays $n_1$ and $n_2$, and we know that $s_1 s_2$ must have birthday at the latest $\max(n_1,n_2) + 1$.

So we've successfully found a subgroup of $G$ containing $S$, and by construction each element of this subgroup is built as a product of (possibly inverted) elements in $S$, so it's the smallest subgroup containing $S$!


What does this have to do with löwenheim-skolem? Well recall the tarski-vaught test says that $\mathcal{M}$ is elementary in $\mathcal{N}$ if and only if each $\varphi(x, \overline{y})$, if $\overline{m} \in \mathcal{M}$ and some $n \in \mathcal{N}$ makes $\varphi(n, \overline{m})$ true, then actually there's a $m' \in \mathcal{M}$ so that $\varphi(m', \overline{m})$ is true.

In a slogan: To check if $\mathcal{M}$ is elementary in $\mathcal{N}$, it sfufices to check that whenever a witness to $\exists x. \varphi(x, \mathcal{m})$ exists in $\mathcal{N}$, then a witness also exists in $\mathcal{M}$

This gives us a very concrete way to force elementarity, in a similar way that we were able to force subgroup-ness! All we have to do is add in witnesses to every existential statement. The clever way to do this is by skolemizing our language.

We add function symbols for each formula $\varphi$, and add axioms saying that if $\varphi(x,\overline{y})$ is satisfiable, then actually we can take $x = f_\varphi(\overline{y})$ (we need to be slightly more careful, since once we add these function symbols there are new formulas we can write, which should themselves have witnessing functions. We can get around this with a similar "birthday" argument to before).

Now, though, we have a subset $M$ of $\mathcal{N}$, and we would like to puff it out to an elementary submodel. But by the tarski-vaught test, we just need to know that our puffed out version of $M$ witnesses every existential witnessed in $\mathcal{N}$. But then it's enough to know the puffed out version is closed under all of the $f_\varphi$!

So to finish, we just do to $M$ what we did to $S$ before, except on day $n+1$ we add in $f_\varphi(\overline{m})$ for each $\overline{m}$ born by day $n$.


So, to close, what's the intuition for downwards löwenheim-skolem? In the same way we can close $S \subseteq G$ under multiplication and inverses, we want to close $M \subseteq \mathcal{N}$ under "existential witnesses", made precise by skolem functions. Just like the closure of $S$ gives a subgroup, tarski-vaught says that the closure of $M$ gives an elementary substructure.


I hope this helps ^_^

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.