Let $\mathcal A$ be an $\mathcal L$-structure, let $\dot{\triangleleft}$ be a new binary predicate symbol, let $\triangleleft$ be a wellordering of $A$, and let ${\mathcal A}^*$ be the expansion of $\mathcal A$ to $\mathcal L^* := {\mathcal L}\cup\{\dot{\triangleleft}\}$ interpreting $\dot{\triangleleft}$ by $\triangleleft$. Let $X \subseteq A$, and let $H$ consist of all elements of $A$ definable in $\mathcal A^*$ from parameters in $X$. Prove that $H$ is the universe of an elementary substructure of $\mathcal A^*$, and hence also the universe of an elementary substructure of $\mathcal A$. Furthermore, prove that (with the same notation) if $\mathcal B^* \equiv \mathcal A^*$, then the same holds for $\mathcal B^*$.
I am lost on this problem. I know that for all $h \in H$ there is some ${\mathcal L}^*$-formula $\varphi_h(\vec{x},y)$ and $\vec{a} \in X^n$ such that $h$ is the unique element in $A$ such that $\mathcal A^* \models \varphi_h(\vec{a},h)$. How can I start on this problem?
When in doubt, induct on the number of quantifiers.
Let's call our substructure $\mathcal{H}$.
Let $\varphi(z)$ be a formula with parameters in $X$ with one free variable $z$.
I claim that $\mathcal{A}^* \models [\exists z](\varphi(z))$ implies that $H$ contains a witness of this fact. Namely the sole solution to $\varphi(z) \land [\forall w](w \neq z \land \varphi(w) \to z \triangleleft w)$. This is where we use the fact that $\triangleleft$ is a well-order; it lets us pick out an element of every nonempty definable set.
If $\varphi(z)$ is unsatisfiable, then there's no witness in $H$.
Armed with this lemma, let's show that $\mathcal{H}$ is a substructure of $\mathcal{A}^*$ by inducting on the number of quantifiers in an arbitrary formula with parameters $\psi$.
First, assume without loss of generality that $\psi$ is in prenex normal form.
Let's consider the case when $\psi$ is quantifier-free. All of the terms in the expressions are recursively built from parameters, constant symbols, and functions. This means that the interpretation of all of these terms are already in $H$.
Now we consider the inductive case. Suppose it holds that $\mathcal{H} \models \psi \iff \mathcal{A}^* \models \psi$ for all formulas $\psi$ with parameters with strictly fewer than $n$ quantifiers and we want to show that $\mathcal{H} \models \psi \iff \mathcal{A}^*$ for all formulas with parameters with exactly $n$ quantifiers.
Suppose $\psi$ is of the form $[\exists z](\chi(z))$. Suppose $\mathcal{A}^* \models \psi$, then there exists a least $z$ such that $\chi(z)$, which will be in $H$. Suppose $\mathcal{H} \models [\exists z](\chi(z))$, then there exists an $h$ in $H$ such that $\chi(h)$ holds in $\mathcal{H}$, by induction it holds in $\mathcal{A}^*$ too.
Suppose $\psi$ is of the form $[\forall z](\chi(z))$. Suppose $\mathcal{A}^* \models [\forall z](\chi(z))$, then $\mathcal{H}$ does too because $\chi(h)$ for all $h$ in $H$ would hold in both structures by the inductive hypothesis. Suppose $\mathcal{A}^* \not\models [\forall z](\chi(z))$, then there would exist a least witness of $\lnot \chi(z)$ (converted to prenex normal form), and that least witness would be in $\mathcal{H}$, hence $\mathcal{H} \not\models [\forall z](\chi(z))$.