Witnessing expansion of a first-order language and the use of the Axiom of Choice to expand any structure in the language

Question

Understanding the use of the Axiom of Choice in the constructions mentioned in this question prompted the following, which I will state as a Lemma:

Lemma: Let $\mathcal{M}$ be any $\mathcal{L}$-structure of a first-order language $\mathcal{L}$, and let $\mathcal{L}^{*}$ be its witnessing expansion (see Lemma 2.1.8 page 38 in the linked question for details - the witnessing constants are denoted by $c_{\phi}$) then there is an assignment of the constant symbols of $\mathcal{L}^{*}$ to elements in the domain of $\mathcal{M}$ so that the expansion of $\mathcal{M}$ to $\mathcal{L}^{*}$ satisfies all of the $L^{*}$-sentences: $$(\exists v\,\phi(v))\Rightarrow \phi(c_{\phi}).$$

Proof: We accomplish this by assigning elements in the domain of $\mathcal{M}$ to the constants added at each step in the construction of $\mathcal{L}_{i}$ (again, see Lemma 2.1.8 for details). For example, the first step $$\mathcal{L}_{1}=\mathcal{L}\cup\{c_{\phi}:\phi(v)\;\mbox{an $\mathcal{L}$-formula}\}.$$ Let $C_{1}$ denote the set of new constants above (added to $\mathcal{L}$). Then if $c_{\phi}\in C_{1}$ the sentence $\exists v\,\phi(v)$ makes sense in $\mathcal{M}$.

1. If $\mathcal{M}\vDash \exists v\,\phi(v)$, choose some $a$ in the domain of $\mathcal{M}$ such that $\mathcal{M}\vDash\phi(a)$ and assign $c_{\phi}$ the element $a$, i.e. $c_{\phi}^{\mathcal{M}}=a$.
2. If $\mathcal{M}\vDash \neg\exists v\,\phi(v)$, assign $c_{\phi}$ any element arbitrarily.

The process carries on to constants in subsequent sets $C_{2}, C_{3},$ etc.

Two questions:

First, the set of constants $c_{\phi}$ in $C_{1}$ (and subsequent steps) may be infinite and thus Choice appears to be needed to obtain the $a$'s in (1). Is this use of Choice avoidable?

Second, the Lemma above seems to have echoes of Lindenbaum's theorem, which is ZF equivalent to the ultrafilter theorem. But the Lemma appears weaker, as countable Choice is all it seems to require. Is this correct?

Answer 1

The use of choice is indeed unavoidable.

One form of the axiom of choice states that for all surjective $f : A \to B$, where $B$ is nonempty, there is some $g : B \to A$ such that $f \circ g = 1_B$. We will prove this form of the axiom of choice from your Lemma.

Consider a surjective function $f : A \to B$.

Let us consider a two-sorted theory, one sort $\mathscr{A}$ with Latin letter variables, the other sort $\mathscr{B}$ with Greek letter variables. Since we have a finite number of sorts, we can rephrase our results to fit into one-sorted logic, if this is what your book requires.

Our vocabulary with consist of a single function symbol $\mathscr{f} : \mathscr{A} \to \mathscr{B}$ together with, for each $b \in B$, a constant symbol $q_b \in \mathscr{B}$. This vocabulary we shall call $\mathscr{L}$.

Let $M$ be the obvious structure for this language; $\mathscr{A}$ corresponds with $A$, $\mathscr{B}$ with $B$, $\mathscr{f}$ with $f$, and each $q_b$ with $b$. Consider some extension of the structure on $M$ to an $\mathscr{L}^*$ structure.

For all $b \in B$, define $\phi_b(a) :\equiv \mathscr{f}(a) = q_b$. Now for all $b \in B$, we have $M \vDash \exists a (\phi_b(a))$, since $f$ is surjective. Therefore, for all $b \in B$, we have $M \vDash \phi_b(c_{\phi_b})$. In particular, we have $f((c_{\phi_b})_M) = b$.

Define $g : B \to A$ by $g(b) = (c_{\phi_b})_M$. Then we see that for all $b \in B$, we have $f(g(b)) = b$. So $f \circ g = 1_B$.

So we have proved the axiom of choice.