3
$\begingroup$

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 \,$?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\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.