= Solution
The <Downward Lowenheim-Skolem theorem> says that for an $L$-structure $M$ and a <subset> $S\subseteq M$, there is an <elementary substructure> $N\preccurlyeq M$ containing $S$ with
$$
\boxed{|N|\le\max(|S|,|L|,\aleph_0).}
$$
If an infinite cardinal $\kappa$ satisfies $\max(|L|,\aleph_0)\le\kappa\le|M|$, one can in particular obtain size exactly $\kappa$ by starting with a <subset> of that size.
Choose a default element $a_0\in M$. For every <logical formula> $\exists x\phi(x,\vec y)$ choose a <Skolem function> $F_\phi$ which returns a witness in $M$ when one exists, and returns $a_0$ otherwise. Begin with $S$, the interpretations of the <first-order language>'s constants, and $a_0$. Successively adjoin the values of all the original <functions> and these <Skolem functions> on finite <tuples> already chosen. Let $N$ be the <union> of the resulting <countable> sequence of closure stages.
There are at most $\max(|L|,\aleph_0)$ <logical formulas>, and each <function> has finite arity. With $\kappa=\max(|S|,|L|,\aleph_0)$, each closure stage has size at most $\kappa$, and so does their <countable> <union>. Closure under the original <functions> makes $N$ an $L$-substructure. Whenever $M\models\exists x\phi(x,\vec a)$ for parameters in $N$, its chosen Skolem witness belongs to $N$, since the finitely many parameters lie in some common stage. The Tarski–Vaught test therefore gives $N\preccurlyeq M$.
For the exact-cardinality version, choose an initial <set> of $\kappa$ elements, enlarged to contain any prescribed <subset> of size at most $\kappa$. The construction gives an upper bound $\kappa$ while containment gives the matching lower bound.
Back to article page
