Some parts of the proof of downward Löwenheim–Skolem theorem I need to clarify

logicmodel-theory

Downward Löwenheim–Skolem theorem states that, for every signature $\sigma$ of a first order language, every infinite $\sigma$-structure $\mathscr M$ with domain $M$ and every infinite cardinal number $\kappa \ge \vert\sigma\vert$, there is a $\sigma$-structure $\mathscr N$ with domain $N$, such that $\vert N\vert = κ$ and such that if $κ < \vert M\vert$, then $\mathscr N$ is an elementary substructure of $\mathscr M$.

So, here is a sketch of the proof, from Wikipedia:

For each first-order $\sigma$-formula $\phi(y,x_1,…,x_n)$, the axiom of choice implies the existence of a function $f_\phi:M^n\rightarrow M$ such that, for all $a_1,…,a_n\in M$, either $\mathscr M\vDash \phi \bigl(f_\phi(a_1,a_2,…,a_n),a_1,a_2,…,a_n \bigl)$ or $\mathscr M\vDash\lnot\exists y\phi(y,a_1,a_2,…,a_n)$.

The family of functions $f_\phi$
gives rise to a preclosure operator $F$ on the power set of $M$, $F(A) = \lbrace f
_\phi(a_1,a_2,…,a_n)\in M\ \vert\ \phi \in \sigma\ ;\ a_1,a_2,…,a_n \in A\rbrace$, 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 $\vert A\vert =\kappa$, and having defined $N=F^\omega (A)$, one can see that also $\vert N\vert = \kappa$. Then, $\mathscr N$ is an elementary substructure of $\mathscr M$, by the Tarski–Vaught test.

  1. What about formulas $\phi$ with only one variable? I guess then, functions $f_\phi$ are of zero arity, and thus, they are constants, is that right?
  2. It is not clear to me, how $A\subseteq F(A)$, as is should, in order for $F$ to be a preclosure operator. In the definition of $F(A)$, only elements of M that satisfy some $\sigma$-formula are selected by the $f_\phi$'s. But, $A$, on the other hand, is an arbitrary subset of $M$ with cardinality $\kappa$. So, it may contains elements that do not satisfy any $\sigma$-formula, is that right? If it does, then, how do these elements get in $F(A)$, since they are not going to be selected by any $f_\phi$?
  3. "Iterating $F$ countably many times", actually means that $F^\omega (A)= \lbrace a\in F^m(A)\ \vert\ m\in\Bbb N \rbrace$, is that right?

Best Answer

For $(1)$ and $(3)$: yes, that's right.

For $(2)$: you're right that elements of $A$ need not be definable, and so we're not going to be able to get them in $F(A)$ via one-variable formulas (a la point $(1)$). However, we can get around this: consider the formula $$\varphi_{id}:\equiv y=x_1.$$ The corresponding $f_{\varphi_{id}}:M\rightarrow M$ is just the identity map, and so we do indeed get $F(A)\supseteq A$.

Related Question