[proofplan] We prove the easy direction by combining Łoś's theorem with invariance of first-order truth under isomorphism. For the converse, define a cardinal $\lambda$ that dominates $|L|$, $|M|$, $|N|$, and $\aleph_0$, then choose an infinite cardinal $\mu$ with \begin{align*} \lambda \leq 2^\mu \end{align*} and set \begin{align*} \kappa := 2^\mu. \end{align*} We use the Keisler-Shelah ultrapower saturation theorem in the cardinal form needed here: for the chosen $\mu$ and $\kappa=2^\mu$, there is an ultrafilter on an index set of size $\mu$ that makes ultrapowers of all structures of size at most $\kappa$ in languages of size at most $\kappa$ $\kappa^+$-saturated. The cardinal estimate \begin{align*} |A^I/\mathcal U|\leq |A|^\mu\leq \kappa \end{align*} keeps both ultrapowers small enough for a back-and-forth of length $\kappa$. Since $M \equiv N$, Łoś's theorem transfers elementary equivalence to the ultrapowers, and the saturated back-and-forth construction produces an $L$-isomorphism between them. [/proofplan] [step:Show that isomorphic ultrapowers force elementary equivalence] Assume there are a set $I$, an ultrafilter $\mathcal U$ on $I$, and an $L$-isomorphism \begin{align*} \Phi: M^I / \mathcal U &\to N^I / \mathcal U. \end{align*} Let $\varphi$ be an $L$-sentence. By [Łoś's theorem](/theorems/???), applied to the ultrapower of $M$ over $I$ and $\mathcal U$, \begin{align*} M \models \varphi \quad \Longleftrightarrow \quad M^I / \mathcal U \models \varphi. \end{align*} Because $\Phi$ is an $L$-isomorphism, first-order satisfaction of sentences is preserved under $\Phi$, so \begin{align*} M^I / \mathcal U \models \varphi \quad \Longleftrightarrow \quad N^I / \mathcal U \models \varphi. \end{align*} Applying Łoś's theorem again to $N$ gives \begin{align*} N^I / \mathcal U \models \varphi \quad \Longleftrightarrow \quad N \models \varphi. \end{align*} Thus $M \models \varphi$ if and only if $N \models \varphi$ for every $L$-sentence $\varphi$, which is exactly $M \equiv N$. [guided] Suppose first that the desired ultrapowers already exist. Thus there are a set $I$, an ultrafilter $\mathcal U$ on $I$, and an $L$-isomorphism \begin{align*} \Phi: M^I / \mathcal U &\to N^I / \mathcal U. \end{align*} To prove $M \equiv N$, let $\varphi$ be an arbitrary $L$-sentence. [Łoś's theorem](/theorems/???) applies to the ultrapower $M^I/\mathcal U$, because $\mathcal U$ is an ultrafilter on $I$. It gives \begin{align*} M \models \varphi \quad \Longleftrightarrow \quad M^I / \mathcal U \models \varphi. \end{align*} The map $\Phi$ is an $L$-isomorphism, so it preserves the interpretation of every symbol of $L$ and hence preserves truth of every $L$-sentence: \begin{align*} M^I / \mathcal U \models \varphi \quad \Longleftrightarrow \quad N^I / \mathcal U \models \varphi. \end{align*} Finally, applying Łoś's theorem to $N^I/\mathcal U$ gives \begin{align*} N^I / \mathcal U \models \varphi \quad \Longleftrightarrow \quad N \models \varphi. \end{align*} Combining the three equivalences shows that $M$ and $N$ satisfy the same $L$-sentences. [/guided] [/step] [step:Choose a good ultrafilter large enough for both structures] Assume now that $M \equiv N$. Define the cardinal \begin{align*} \lambda := \max\{|L|, |M|, |N|, \aleph_0\}. \end{align*} Choose an infinite cardinal $\mu$ such that \begin{align*} \lambda \leq 2^\mu, \end{align*} and define \begin{align*} \kappa := 2^\mu. \end{align*} By the Keisler-Shelah ultrapower saturation theorem in this cardinal form, there exist a set $I$ with \begin{align*} |I| = \mu \end{align*} and a $\kappa^+$-good regular ultrafilter $\mathcal U$ on $I$ such that, for every $L$-structure $A$ with \begin{align*} |L| \leq \kappa \qquad\text{and}\qquad |A| \leq \kappa, \end{align*} the ultrapower $A^I/\mathcal U$ is $\kappa^+$-saturated. Applying this theorem to $A=M$ and $A=N$ gives that both \begin{align*} M^I / \mathcal U \qquad \text{and} \qquad N^I / \mathcal U \end{align*} are $\kappa^+$-saturated. Their cardinalities are at most $\kappa$: for $A\in\{M,N\}$, \begin{align*} |A^I / \mathcal U| \leq |A|^{|I|} \leq \lambda^\mu \leq (2^\mu)^\mu = 2^{\mu\cdot \mu} = 2^\mu = \kappa. \end{align*} Here $\mu$ is infinite, so $\mu\cdot\mu=\mu$. [guided] The hard set-theoretic input is an ultrafilter that makes both ultrapowers saturated enough for a back-and-forth argument. Define \begin{align*} \lambda := \max\{|L|, |M|, |N|, \aleph_0\}. \end{align*} Thus the language and both structures have size at most $\lambda$. Choose an infinite cardinal $\mu$ satisfying \begin{align*} \lambda \leq 2^\mu \end{align*} and put \begin{align*} \kappa := 2^\mu. \end{align*} The Keisler-Shelah ultrapower saturation theorem supplies a set $I$ with \begin{align*} |I| = \mu \end{align*} and a $\kappa^+$-good regular ultrafilter $\mathcal U$ on $I$ such that every $L$-structure $A$ of cardinality at most $\kappa$ has a $\kappa^+$-saturated ultrapower $A^I/\mathcal U$. The hypotheses apply to $M$ and $N$ because \begin{align*} |L| \leq \lambda \leq \kappa, \qquad |M| \leq \lambda \leq \kappa, \qquad |N| \leq \lambda \leq \kappa. \end{align*} Therefore $M^I/\mathcal U$ and $N^I/\mathcal U$ are both $\kappa^+$-saturated. We also need their sizes to be at most $\kappa$. For $A\in\{M,N\}$, the quotient map $A^I\to A^I/\mathcal U$ cannot increase cardinality, and $|I|=\mu$. Hence \begin{align*} |A^I / \mathcal U| \leq |A|^{|I|} \leq \lambda^\mu \leq (2^\mu)^\mu = 2^{\mu\cdot \mu} = 2^\mu = \kappa. \end{align*} Since $\mu$ is infinite, $\mu\cdot\mu=\mu$. Thus both ultrapowers are simultaneously $\kappa^+$-saturated and of cardinality at most $\kappa$. [/guided] [/step] [step:Transfer elementary equivalence to the ultrapowers] Since $M \equiv N$, the structures $M$ and $N$ satisfy the same $L$-sentences. Let $\varphi$ be an $L$-sentence. By [Łoś's theorem](/theorems/???), \begin{align*} M^I / \mathcal U \models \varphi \quad \Longleftrightarrow \quad M \models \varphi \quad \Longleftrightarrow \quad N \models \varphi \quad \Longleftrightarrow \quad N^I / \mathcal U \models \varphi. \end{align*} Hence \begin{align*} M^I / \mathcal U \equiv N^I / \mathcal U. \end{align*} [guided] Let $\varphi$ be an arbitrary $L$-sentence. Łoś's theorem applies to both ultrapowers over the same index set $I$ and ultrafilter $\mathcal U$. Therefore \begin{align*} M^I / \mathcal U \models \varphi \quad \Longleftrightarrow \quad M \models \varphi \end{align*} and \begin{align*} N \models \varphi \quad \Longleftrightarrow \quad N^I / \mathcal U \models \varphi. \end{align*} The assumption $M\equiv N$ gives \begin{align*} M \models \varphi \quad \Longleftrightarrow \quad N \models \varphi. \end{align*} Combining these equivalences yields \begin{align*} M^I / \mathcal U \models \varphi \quad \Longleftrightarrow \quad N^I / \mathcal U \models \varphi. \end{align*} Since $\varphi$ was arbitrary, the two ultrapowers are elementarily equivalent. [/guided] [/step] [step:Build an isomorphism by saturated back-and-forth] Let \begin{align*} P &:= M^I / \mathcal U, & Q &:= N^I / \mathcal U. \end{align*} From the previous steps, $P \equiv Q$, both $P$ and $Q$ are $\kappa^+$-saturated, and both have cardinality at most $\kappa$. Enumerate their underlying sets as \begin{align*} P &= \{a_\alpha : \alpha < \kappa\}, & Q &= \{b_\alpha : \alpha < \kappa\}, \end{align*} allowing repetitions if a structure has cardinality strictly smaller than $\kappa$. We construct by transfinite recursion a chain $(f_\alpha)_{\alpha<\kappa}$ of partial elementary maps from $P$ to $Q$. At each successor stage, first extend to include $a_\alpha$ in the domain and then extend to include $b_\alpha$ in the image. If $f:A\to B$ is a partial elementary map with \begin{align*} |A|<\kappa^+ \qquad\text{and}\qquad |B|<\kappa^+, \end{align*} and if $a\in P$, then the type $\operatorname{tp}_P(a/A)$ transports along $f$ to a type over $B$. Every finite subset of the transported type is realized in $Q$ by partial elementarity of $f$, so $\kappa^+$-saturation of $Q$ realizes the whole type. This gives $b\in Q$ such that $f\cup\{(a,b)\}$ is partial elementary. For the backward extension, take $b\in Q$ and transport the type $\operatorname{tp}_Q(b/B)$ along the inverse partial elementary map $f^{-1}:B\to A$. Every finite subset of the transported type is realized in $P$, and $\kappa^+$-saturation of $P$ gives $a\in P$ such that $f\cup\{(a,b)\}$ is partial elementary. At a limit ordinal $\delta<\kappa$, define \begin{align*} f_\delta := \bigcup_{\alpha<\delta} f_\alpha. \end{align*} Every formula mentions only finitely many parameters, so the union of an increasing chain of partial elementary maps is partial elementary. The final union \begin{align*} f := \bigcup_{\alpha<\kappa} f_\alpha \end{align*} has every $a_\alpha$ in its domain and every $b_\alpha$ in its image. Therefore $f:P\to Q$ is a bijective partial elementary map, hence an $L$-isomorphism. [guided] Set \begin{align*} P &:= M^I / \mathcal U, & Q &:= N^I / \mathcal U. \end{align*} We have proved \begin{align*} P \equiv Q, \end{align*} and both structures are $\kappa^+$-saturated of cardinality at most $\kappa$. Enumerate their underlying sets as \begin{align*} P &= \{a_\alpha : \alpha < \kappa\}, & Q &= \{b_\alpha : \alpha < \kappa\}. \end{align*} We build partial elementary maps $f_\alpha:P\rightharpoonup Q$ by back-and-forth. Suppose $f:A\to B$ is already partial elementary with \begin{align*} |A|<\kappa^+ \qquad\text{and}\qquad |B|<\kappa^+. \end{align*} To add $a\in P$ to the domain, take the complete type $\operatorname{tp}_P(a/A)$ and transport its parameters through $f$ to a type over $B$. Every finite part of that transported type is satisfiable in $Q$, because $f$ is partial elementary and $P\equiv Q$. Since $Q$ is $\kappa^+$-saturated and the type has fewer than $\kappa^+$ parameters, some $b\in Q$ realizes it. Then $f\cup\{(a,b)\}$ is partial elementary. To put a chosen $b\in Q$ into the image, apply the same argument to the inverse partial elementary map \begin{align*} f^{-1}:B\to A \end{align*} and use $\kappa^+$-saturation of $P$. Thus each successor stage can add the next element from $P$ and the next element from $Q$. At a limit ordinal $\delta<\kappa$, define \begin{align*} f_\delta := \bigcup_{\alpha<\delta} f_\alpha. \end{align*} The union is still partial elementary because any formula uses only finitely many parameters, all of which already occur together in some earlier $f_\alpha$. Finally set \begin{align*} f := \bigcup_{\alpha<\kappa} f_\alpha. \end{align*} Every element $a_\alpha$ appears in the domain and every element $b_\alpha$ appears in the image, so $f$ is a bijection $P\to Q$. Since it is partial elementary on all of $P$, it preserves all symbols of $L$ and is an $L$-isomorphism. [/guided] [/step] [step:Conclude the equivalence] The first step proves that isomorphic ultrapowers imply $M\equiv N$. Conversely, if $M\equiv N$, the ultrapower saturation construction and saturated back-and-forth give a set $I$, an ultrafilter $\mathcal U$ on $I$, and an $L$-isomorphism \begin{align*} M^I/\mathcal U \cong N^I/\mathcal U. \end{align*} This proves both directions. [guided] We have proved both implications. If $M^I/\mathcal U$ and $N^I/\mathcal U$ are isomorphic, then Łoś's theorem transfers every sentence from each structure to its ultrapower, and the isomorphism transfers truth between the ultrapowers. Hence $M\equiv N$. Conversely, assuming $M\equiv N$, we chose $I$ and $\mathcal U$ so that the ultrapowers \begin{align*} M^I/\mathcal U \qquad\text{and}\qquad N^I/\mathcal U \end{align*} are elementarily equivalent, $\kappa^+$-saturated, and of size at most $\kappa$. The back-and-forth construction then produced an $L$-isomorphism \begin{align*} M^I/\mathcal U \cong N^I/\mathcal U. \end{align*} Thus elementary equivalence is exactly the existence of isomorphic ultrapowers over a common index set and ultrafilter. [/guided] [/step]