Proof of Lowenheim-Skolem theorem

For each first-order $\sigma \,$-formula $\varphi(y,x_{1}, \ldots, x_{n}) \,,$ the axiom of choice implies the existence of a function $f_{\varphi}: M^n\to M$ such that, for all $a_{1}, \ldots, a_{n} \in M$, either $M\models\varphi(f_{\varphi} (a_1, \dots, a_n), a_1, \dots, a_n)$ or $M\models\neg\exists y \varphi(y, a_1, \dots, a_n) \,.$

Applying the axiom of choice again we get a function from the first order formulas $\varphi$ to such functions $f_{\varphi} \,.$

The family of functions $f_{\varphi}$ gives rise to a preclosure operator $F \,$ on the power set of $M \,$ $F(A) = \{b \in M \mid b = f_{\varphi}(a_1, \dots, a_n); \, \varphi \in \sigma ; \, a_1, \dots, a_n \in A \}$

for $A \subseteq M \,.$

Iterating $F \,$ countably many times results in a closure operator $F^{\omega} \,.$ Taking an arbitrary subset $A \subseteq M$ such that $\left\vert A \right\vert = \kappa$, and having defined $N = F^{\omega}(A) \,,$ one can see that also $\left\vert N \right\vert = \kappa \,.$ $N \,$ is an elementary substructure of $M \,$ by the Tarski–Vaught test. The trick used in this proof is essentially due to Skolem, who introduced function symbols for the Skolem functions $f_{\varphi}$ into the language. One could also define the $f_{\varphi}$ as partial functions such that $f_{\varphi}$ is defined if and only if $M \models \exists y \varphi(y,a_1,\dots,a_n) \,.$ The only important point is that $F \,$ is a preclosure operator such that $F(A) \,$ contains a solution for every formula with parameters in $A \,$ which has a solution in $M \,$ and that $\left\vert F(A) \right\vert \leq \left\vert A \right\vert + \left\vert \sigma \right\vert + \aleph_0 \,.$ (Downward Lowenheim-Skolem theorem proof)

The first question is, how does $F^\omega$ become closure operator?

The second question is, why is $\left\vert F(A) \right\vert \leq \left\vert A \right\vert + \left\vert \sigma \right\vert + \aleph_0 \,$?

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.

To the first question, note that if $M\models\exists x\varphi(x,u_1,\ldots,u_n)$ for $u_i\in F^\omega$, then there exists some $k$ such that $u_1,\ldots,u_n\in F^k(A)$. Therefore there is some $f_\varphi(u_1,\ldots,u_n)=b\in F^{n+1}(A)$ such that $M\models\varphi(b,u_1,\ldots,u_n)$.

So $F^\omega(A)$ is closed under the Skolem functions, that is to say $F(F^\omega(A))=F^\omega(A)$.

As for the cardinality argument, there are only $|\sigma|^{<\omega}$ formulas in the language, which is equal to $\max\{|\sigma|,\aleph_0\}=|\sigma|\cdot\aleph_0=|\sigma|+\aleph_0$, and clearly all the members of $A$ are in $F(A)$, so we have $A$ itself with perhaps $|\sigma|+\aleph_0$ additions to spare.