Let $T$ be a complete first-order theory and $U$ a monster model. For a small subset $B\subset U$, define a language $L_B$ that contains a predicate $R_{\varphi(ub)}(u)$ for every formula $\varphi(ub)$ with parameters $b\in B$. Now any subset $A\subseteq U$ can be made into an $L_B$-structure $A_{\text{ind}(B)}$ in a natural way; take $A_{\text{ind}(B)}\models R_{\varphi(ub)}(a)$ to hold if and only if $U\models \varphi(ab)$. Given a small model $M\prec U$, and a small $|M|^+$-saturated elementary extension $M\prec O\prec U$, we refer to the structure $M_{\text{ind}(O)}$ as $M^{\text{Sh}}$, the "Shelah expansion" of $M$. The following is exercise 3.10 in Pierre Simon's book on NIP theories:
Let $M\prec U$ and let $\widehat{N}$ be an elementary extension of $M^{\text {Sh}}$ with $L$-reduct $N\prec U$. Show that, up to a renaming of the language, $\widehat{N}$ is equal to $N_{\text{ind}(B)}$ for some set $B\subset U$ of parameters.
I'm having a bit of trouble with this exercise. If I'm not mistaken, showing that $\widehat{N}$ is equal to $N_{\text{ind}(B)}$ means showing that the same sets of tuples from $N$ are definable in these structures. I'm able to find a subset $B\subset U$ such that every set definable in $\widehat{N}$ is definable in $N_{\text{ind}(B)}$ without much trouble, but I'm struggling to construct $B$ in such a way that $N_{\text{ind}(B)}$ doesn't have any new definable sets. Here is my approach.
Let $\varphi(uo)$ be any $O$-formula. Let $K=R_{\varphi(uo)}(\widehat{N})$, and consider the partial type in $w$ containing $\{\varphi(nw):n\in K\}$ and $\{\neg\varphi(nw):n\in N\setminus K\}$. Since $R_{\varphi(uo)}(M^{\text{Sh}})=\varphi(M;o)$, and since $M\prec U$, we know that, for any $k\in\omega$,
\begin{align}
M^{\text{Sh}}\models\forall u_1\dots u_k\forall v_1\dots v_k &\bigwedge_{i\in[k]}R_{\varphi(uo)}(u_i)\wedge\neg R_{\varphi(uo)}(v_i)\\
\to\exists w&\bigwedge_{i\in[k]}\varphi(u_iw)\wedge\neg\varphi(v_iw).
\end{align} Since $\widehat{N}\succcurlyeq M^{\text{Sh}}$, this carries up to $\widehat{N}$, and hence for any finite subsets $K_0\subseteq K$ and $K_1\subseteq N\setminus K$ we may find $e\in N$ such that $K_0\subseteq\varphi(Ne)$ and $K_1\subseteq\neg\varphi(Ne)$. So the partial type above is consistent, and hence there exists some $b_{\varphi(uo)}\in U$ such that $R_{\varphi(uo)}(\widehat{N})=\varphi(N;b_{\varphi(uo)})$.
Now if we take $B=\{b_{\varphi(uo)}:\varphi(uo)\in \text {Form}(O)\}$, then indeed every set definable in $\widehat{N}$ will be definable in $N_{\text{ind}(B)}$. But I don't think there any reason for the converse to hold in general; for example, this remark follows the exercise:
Observe that in general $\widehat{N}$ is a proper reduct of $N^{\text{Sh}}$.
I think I see why this is the case. For example, suppose $T$ is the theory of the random graph. Then for any model $N\prec U$, we know that every subset of $N$ is definable in $N^{\text{Sh}}$; in particular, $N^{\text{Sh}}$ has $2^{|N|}$ definable subsets. But the number of definable subsets of $\widehat{N}$ is bounded by $\operatorname{max}\{|N|,|L_O|\}$, and hence if $N$ is sufficiently large (eg if $2^{|N|}>|O|$), then there will be no way for $\widehat{N}$ to have all of the definable subsets that $N^{\text{Sh}}$ does, just for cardinality reasons. Is this right?
So we need to find a way of avoiding this kind of behavior, ie to do something further to ensure that $B$ cannot add new definable sets to $\widehat{N}$; I'm at a bit of a loss as to how to approach this. The fundamental issue I'm grappling with is that, if we have a partial type in new variables $w_{\varphi(uo)}$, the realizations of which we want to take as the set $B$, it's unclear to me how we might express that $\bar{w}$-definable sets are $L_O$-definable in a first-order way. Any insight, or a hint, would be much appreciated.
Best Answer
Why not try your approach, but for all formulas at once? That is, for every tuple $o$ from $O$, realize the partial type $p_o(w)$ saying that for all formulas $\varphi(x,o)$, an element is in the set defined by $\varphi(x,w)$ if and only if it satisfies $R_{\varphi(x,o)}$?
Ok, this doesn't quite work, because you need the tuples realizing these partial types to cohere appropriately. That is, if some tuples $o$ and $o'$ have some elements in common, you also want the tuples realizing $p_o(w)$ and $p_{o'}(w')$ to have the corresponding elements in common. Otherwise you could mix-and-match across tuples and possible get new definable sets.
So don't just handle all formulas at once, handle all formulas and all tuples at once. That is, generalize the above partial type to one in infinitely many variables, one for each element of $O$.
There are some details to check - this is more of a hint than a complete answer - but I think this idea works.