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?
Intuition behind downwards Lowenheim-Skolem Theorem
intuitionlogicmodel-theoryset-theory
Related Solutions
Let’s take the second question first. The important thing is that $F(A)$ contains at most one element for each $\varphi\in\sigma$ and each finite tuple in $\bigcup_{n\in\omega}A^n$. Assuming that $A$ is infinite, $$\left|\bigcup_{n\in\omega}A^n\right|=|A|\;,$$
so $|F(A)|\le|\sigma|\cdot|A|=\max\{|\sigma|,|A|\}=|\sigma|+|A|$. The extra $\aleph_0$ term covers the case in which $\sigma$ and $A$ are both finite.
To see why $F^\omega$ is a closure operator, note first that $A\subseteq F(A)\subseteq F^2(A)\subseteq\ldots$. Now suppose that $b\in F\big(F^\omega(A)\big)$; then there are a $\varphi\in\sigma$ and $a_1,\dots,a_n\in F^\omega(A)$ such that $b=f_\varphi(a_1,\dots,a_n)$.
For $k=1,\dots,n$ there is an $F^{m_k}(A)$ such that $a_k\in F^{m_k}(A)$; let $m=\max\{m_1,\dots,m_n\}$. Then $\{a_1,\dots,a_n\}\subseteq F^m(A)$, so $b\in F\big(F^m(A)\big)=F^{m+1}(A)\subseteq F^\omega(A)$. Thus, $$F\big(F^\omega(A)\big)\subseteq F^\omega(A)\subseteq F\big(F^\omega(A)\big)\;,$$ and hence $F\big(F^\omega(A)\big)=F^\omega(A)$, i.e., $F^\omega$ is a closure operator.
Well, given an infinite set $A$, in order to prove $|A\times A|=|A|$, you only really care about the cardinality of $A$: in other words, it suffice to prove that $|B\times B|=|B|$ for some $B$ such that $|B|=|A|$ (since you can transport a bijection $B\times B\to B$ along a bijection between $B$ and $A$). So it doesn't matter what specific sets we get in our models, as long as we hit every possible cardinality.
Unfortunately, though, your argument doesn't work: starting from $\omega$ and going up and down as your statement of Löwenheim-Skolem allows, you cannot reach all infinite cardinalities in the absence of AC. In particular, your version of Downward Löwenheim-Skolem will never guarantee the existence of a model of any cardinality that is not greater than or equal to $\aleph_0$ (because the conclusion has $|N|\leq |A|+\aleph_0+|L|$ rather than just $|N|\leq |A|$). Without AC, it is not necessarily true that every infinite cardinality is greater than or equal to $\aleph_0$.
Here, then, is a more careful version of the argument you propose in the special case that $|A|\geq \aleph_0$. Starting from the model $\omega$, Upward Löwenheim-Skolem gives a model $M$ of cardinality at least $|A|$. Picking a subset of $M$ which is in bijection with $A$, Downward Löwenheim-Skolem then gives a submodel $N$ of $M$ such that $|A|\leq |N|$ (since $N$ contains our chosen subset of size $|A|$) and $|N|\leq |A|+\aleph_0$. But since $|A|\geq \aleph_0$, $|A|+\aleph_0=|A|$ (since $|A|\geq\aleph_0$, we can write $|A|=\aleph_0+|B|$ for some $B$, and then $|A|+\aleph_0=(|B|+\aleph_0)+\aleph_0=|B|+(\aleph_0+\aleph_0)=|B|+\aleph_0=|A|$). Thus $|N|=|A|$, and since we have $|N\times N|=|N|$ we conclude that $|A\times A|=|A|$.
Of course, this still leaves the issue: what if $|A|\not\geq\aleph_0$? Well, it turns out that if you look at the proof that $|A\times A|=|A|$ for all infinite $A$ implies AC, it actually only ever uses sets $A$ such that $|A|\geq\aleph_0$. (Specifically, it uses $A$ of the form $X\sqcup \aleph(X)$ where $X$ is an infinite set and $\aleph(X)$ is its Hartogs number, and $\aleph(X)$ always contains $\omega$.) So actually, the weaker conclusion obtained above is still enough to deduce AC.
Best Answer
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.
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 ^_^