[proofplan] We choose, inside $\mathcal{M}$, one witness function for each existential formula. Starting from $A$ together with the interpretations of constant symbols, we close under the original function symbols of $L$ and under these witness functions. The resulting set has the desired cardinal bound because it is obtained by countably many applications of at most $\max\{|L|,\aleph_0\}$ finitary operations. Closure under the witness functions gives the existential preservation condition, and an induction on formulas then shows that the induced substructure is elementary. [/proofplan] [step:Choose witnesses for all existential formulas] Let $\lambda := \max\{|L|,\aleph_0\}$. For each $L$-formula $\varphi(x,y_1,\dots,y_n)$ with displayed free variables among $x,y_1,\dots,y_n$, choose a function \begin{align*} F_\varphi: M^n &\to M \end{align*} with the following property: for every tuple $b=(b_1,\dots,b_n) \in M^n$, if \begin{align*} \mathcal{M} \models \exists x\,\varphi(x,b_1,\dots,b_n), \end{align*} then \begin{align*} \mathcal{M} \models \varphi(F_\varphi(b),b_1,\dots,b_n). \end{align*} If no such witness is required for a tuple $b$, choose $F_\varphi(b)$ arbitrarily in $M$. This is possible because $M \neq \varnothing$. The number of first-order $L$-formulas with finitely many free variables is at most $\lambda$, since formulas are finite strings formed from the symbols of $L$ together with countably many logical symbols and variables. [guided] The purpose of this step is to make existential quantifiers constructive inside $\mathcal{M}$. For every formula $\varphi(x,y_1,\dots,y_n)$, we want a chosen element of $M$ witnessing $\exists x\,\varphi(x,b_1,\dots,b_n)$ whenever such a witness exists. Formally, for each such formula define a map \begin{align*} F_\varphi: M^n &\to M. \end{align*} For a tuple $b=(b_1,\dots,b_n) \in M^n$, if $\mathcal{M} \models \exists x\,\varphi(x,b_1,\dots,b_n)$, then the set \begin{align*} W_{\varphi,b}:=\{a \in M : \mathcal{M} \models \varphi(a,b_1,\dots,b_n)\} \end{align*} is nonempty, and we choose $F_\varphi(b) \in W_{\varphi,b}$. If $W_{\varphi,b}=\varnothing$, then no witness is needed, and because $M$ is nonempty we choose any element of $M$ as $F_\varphi(b)$. We also record the cardinal count. An $L$-formula is a finite string built from the symbols of $L$, countably many variables, and countably many logical symbols. Hence the set of all formulas with finitely many free variables has cardinality at most \begin{align*} \lambda := \max\{|L|,\aleph_0\}. \end{align*} Thus we have introduced at most $\lambda$ many auxiliary finitary functions. [/guided] [/step] [step:Build the Skolem hull by closing under all relevant finitary operations] Let $C \subset M$ be the set of interpretations in $\mathcal{M}$ of all constant symbols of $L$. If the strengthened cardinal conclusion is required, choose a subset $B \subset M$ such that $A \subset B$ and $|B|=\kappa$, where $\kappa=\max\{|A|,|L|,\aleph_0\}$; this is possible when $A$ is infinite and $\kappa \leq |M|$. Otherwise set $B:=A$. Define a sequence $(H_k)_{k \in \mathbb{N}\cup\{0\}}$ of subsets of $M$ by \begin{align*} H_0 &:= B \cup C, \end{align*} and, once $H_k$ is defined, let $H_{k+1}$ be the union of $H_k$ with all values \begin{align*} f^\mathcal{M}(a_1,\dots,a_m) \end{align*} where $f$ is an $m$-ary function symbol of $L$ and $(a_1,\dots,a_m) \in H_k^m$, together with all values \begin{align*} F_\varphi(a_1,\dots,a_n) \end{align*} where $\varphi(x,y_1,\dots,y_n)$ is an $L$-formula and $(a_1,\dots,a_n) \in H_k^n$. Finally define \begin{align*} H := \bigcup_{k=0}^{\infty} H_k. \end{align*} Then $A \subset H$, all $L$-constants are interpreted in $H$, $H$ is closed under every function symbol of $L$, and $H$ is closed under every chosen witness function $F_\varphi$. [guided] We now generate the smallest set we need. The initial set must contain the parameters $A$, and it must also contain the interpretations of all constant symbols, because a substructure must contain every named constant. Let $C \subset M$ denote the set of all elements $c^\mathcal{M}$ where $c$ ranges over constant symbols of $L$. If we only need the upper bound, set $B:=A$. If we also want equality in the infinite case, put \begin{align*} \kappa := \max\{|A|,|L|,\aleph_0\}. \end{align*} When $A$ is infinite and $\kappa \leq |M|$, cardinal arithmetic allows us to choose $B \subset M$ with $A \subset B$ and $|B|=\kappa$: extend $A$ by adding elements of $M$ until the size is $\kappa$. Define \begin{align*} H_0 := B \cup C. \end{align*} Then recursively define $H_{k+1}$ by adding to $H_k$ every value obtained by applying either an original function symbol of $L$ or one of the auxiliary witness functions $F_\varphi$ to a finite tuple from $H_k$. Finally set \begin{align*} H := \bigcup_{k=0}^{\infty} H_k. \end{align*} This construction ensures three closure properties at once: $H$ contains $A$, contains all named constants, and is closed under every function needed to interpret the language and to witness existential formulas. [/guided] [/step] [step:Control the cardinality of the hull] Let \begin{align*} \mu := \max\{|B|,|L|,\aleph_0\}. \end{align*} Then $|H_k| \leq \mu$ for every $k \in \mathbb{N}\cup\{0\}$, and therefore \begin{align*} |H| \leq \mu. \end{align*} Indeed, $|H_0| \leq \mu$ because $|C| \leq |L|$. If $|H_k| \leq \mu$, then for each fixed finite arity $m$ one has $|H_k^m| \leq \mu$, and there are at most $|L|$ many original function symbols and at most $\lambda \leq \mu$ many witness functions. Hence $|H_{k+1}| \leq \mu$. Taking the countable union gives $|H| \leq \mu$. In the ordinary case $B=A$, this gives \begin{align*} |H| \leq \max\{|A|,|L|,\aleph_0\}. \end{align*} In the strengthened case, $|B|=\kappa$ and $B \subset H$, so \begin{align*} \kappa = |B| \leq |H| \leq \kappa, \end{align*} and hence $|H|=\kappa$. [guided] We verify that the construction has not made the set too large. Define \begin{align*} \mu := \max\{|B|,|L|,\aleph_0\}. \end{align*} First, \begin{align*} |H_0| = |B \cup C| \leq \mu, \end{align*} because $|C| \leq |L|$: each element of $C$ is the interpretation of some constant symbol of $L$. Assume $|H_k| \leq \mu$. For every finite $m$, cardinal arithmetic for infinite cardinals gives \begin{align*} |H_k^m| \leq \mu^m = \mu. \end{align*} There are at most $|L| \leq \mu$ original function symbols of $L$, and there are at most \begin{align*} \lambda := \max\{|L|,\aleph_0\} \leq \mu \end{align*} chosen witness functions. Thus applying all these finitary operations to all finite tuples from $H_k$ adds at most $\mu$ many elements. Therefore \begin{align*} |H_{k+1}| \leq \mu. \end{align*} By induction, $|H_k| \leq \mu$ for every $k$. Finally, $H$ is a countable union of the sets $H_k$, so \begin{align*} |H| \leq \aleph_0 \cdot \mu = \mu. \end{align*} If $B=A$, this is exactly the desired upper bound. If the strengthened case was arranged by choosing $|B|=\kappa$, then $B \subset H$ gives $|H|\geq \kappa$, while the estimate gives $|H|\leq \kappa$, so $|H|=\kappa$. [/guided] [/step] [step:Form the induced substructure on the hull] Let $\mathcal{N}$ be the induced $L$-substructure of $\mathcal{M}$ with universe \begin{align*} N := H. \end{align*} This is well-defined because $H$ contains the interpretation of every constant symbol of $L$ and is closed under every function symbol of $L$. For each relation symbol $R$ of arity $m$, define \begin{align*} R^\mathcal{N} := R^\mathcal{M} \cap H^m. \end{align*} For each function symbol $f$ of arity $m$, define $f^\mathcal{N}$ to be the restriction of $f^\mathcal{M}$ to $H^m$. For each constant symbol $c$, define $c^\mathcal{N}:=c^\mathcal{M}$. [/step] [step:Use witness closure to prove existential preservation] We claim that for every $L$-formula $\varphi(x,y_1,\dots,y_n)$ and every tuple $b=(b_1,\dots,b_n) \in H^n$, if \begin{align*} \mathcal{M} \models \exists x\,\varphi(x,b_1,\dots,b_n), \end{align*} then there exists $a \in H$ such that \begin{align*} \mathcal{M} \models \varphi(a,b_1,\dots,b_n). \end{align*} Indeed, by the defining property of $F_\varphi$, \begin{align*} \mathcal{M} \models \varphi(F_\varphi(b),b_1,\dots,b_n), \end{align*} and closure of $H$ under $F_\varphi$ gives $F_\varphi(b) \in H$. [guided] This is the point of adding the witness functions. Fix an $L$-formula $\varphi(x,y_1,\dots,y_n)$ and a tuple \begin{align*} b=(b_1,\dots,b_n) \in H^n. \end{align*} Assume \begin{align*} \mathcal{M} \models \exists x\,\varphi(x,b_1,\dots,b_n). \end{align*} When we chose $F_\varphi$, we required it to return a genuine witness whenever one exists. Hence \begin{align*} \mathcal{M} \models \varphi(F_\varphi(b),b_1,\dots,b_n). \end{align*} Because $H$ is closed under $F_\varphi$ and $b \in H^n$, the element $F_\varphi(b)$ belongs to $H$. Thus every existential statement over parameters from $H$ that is true in $\mathcal{M}$ already has a witness lying in $H$. [/guided] [/step] [step:Derive elementarity from existential preservation] We prove by induction on $L$-formulas $\psi(z_1,\dots,z_m)$ that for every tuple $a=(a_1,\dots,a_m) \in H^m$, \begin{align*} \mathcal{N} \models \psi(a_1,\dots,a_m) \quad\iff\quad \mathcal{M} \models \psi(a_1,\dots,a_m). \end{align*} For atomic formulas this follows from the definition of the induced substructure: function symbols are interpreted by restriction, constant symbols agree, equality is equality in the common universe, and relation symbols are restricted from $\mathcal{M}$ to $H$. The Boolean connectives are preserved by the induction hypothesis. It remains to handle existential quantifiers. Let $\psi(z_1,\dots,z_m)$ be $\exists x\,\theta(x,z_1,\dots,z_m)$, and let $a \in H^m$. If \begin{align*} \mathcal{N} \models \exists x\,\theta(x,a), \end{align*} then some $h \in H$ satisfies $\mathcal{N}\models \theta(h,a)$, so the induction hypothesis gives $\mathcal{M}\models \theta(h,a)$ and hence $\mathcal{M}\models \exists x\,\theta(x,a)$. Conversely, if \begin{align*} \mathcal{M}\models \exists x\,\theta(x,a), \end{align*} then existential preservation gives $h \in H$ such that $\mathcal{M}\models \theta(h,a)$. The induction hypothesis gives $\mathcal{N}\models \theta(h,a)$, so $\mathcal{N}\models \exists x\,\theta(x,a)$. Thus $\mathcal{N}\preccurlyeq \mathcal{M}$. [guided] We now turn the witness property into full elementarity. We prove, by induction on formulas, that every formula has the same truth value in $\mathcal{N}$ and $\mathcal{M}$ when its parameters lie in $H$. For an atomic formula, the result follows from how $\mathcal{N}$ was defined. Terms have the same values in $\mathcal{N}$ and $\mathcal{M}$ because the function symbols in $\mathcal{N}$ are restrictions of the function symbols in $\mathcal{M}$. Relation symbols also agree on tuples from $H$, since \begin{align*} R^\mathcal{N} = R^\mathcal{M} \cap H^m \end{align*} for every $m$-ary relation symbol $R$. Equality is the same equality relation because $H \subset M$. The induction steps for negation, conjunction, disjunction, and implication follow directly from the induction hypothesis and the truth definitions for Boolean connectives. The only substantive point is the existential quantifier. Let \begin{align*} \psi(z_1,\dots,z_m) := \exists x\,\theta(x,z_1,\dots,z_m), \end{align*} and let $a=(a_1,\dots,a_m) \in H^m$. Suppose first that \begin{align*} \mathcal{N} \models \exists x\,\theta(x,a). \end{align*} Then there is $h \in H$ such that \begin{align*} \mathcal{N}\models \theta(h,a). \end{align*} By the induction hypothesis applied to $\theta$, this implies \begin{align*} \mathcal{M}\models \theta(h,a), \end{align*} and therefore \begin{align*} \mathcal{M}\models \exists x\,\theta(x,a). \end{align*} Conversely, suppose \begin{align*} \mathcal{M}\models \exists x\,\theta(x,a). \end{align*} The existential preservation property proved in the previous step gives some $h \in H$ such that \begin{align*} \mathcal{M}\models \theta(h,a). \end{align*} Applying the induction hypothesis to $\theta$ again gives \begin{align*} \mathcal{N}\models \theta(h,a), \end{align*} and hence \begin{align*} \mathcal{N}\models \exists x\,\theta(x,a). \end{align*} Thus every formula with parameters from $H$ has the same truth value in $\mathcal{N}$ as in $\mathcal{M}$. This is precisely $\mathcal{N}\preccurlyeq \mathcal{M}$. [/guided] [/step] [step:Conclude the required size and containment properties] Since $A \subset B \subset H=N$, the substructure $\mathcal{N}$ contains $A$. The cardinality estimate above gives \begin{align*} |N| \leq \max\{|A|,|L|,\aleph_0\} \end{align*} in the ordinary case. In the strengthened case, when $A$ is infinite and $\kappa=\max\{|A|,|L|,\aleph_0\}\leq |M|$, the construction gives \begin{align*} |N|=\kappa. \end{align*} Together with the elementarity proved above, this completes the proof. [/step]