[proofplan] We extend an arbitrary elementary map $f: A \to B$ with $|A|, |B| < \kappa$ to an automorphism of $M$ by a back-and-forth construction of length $\kappa$. At each stage the current domain and range have cardinality $< \kappa$, because $\kappa$ is regular, so $\kappa$-saturation can realize the transported type needed to add one new element on either side. Alternating forth and back steps makes the final union both total and surjective. Since the union preserves truth of all formulas on finite tuples, it is an elementary bijection $M \to M$, hence an automorphism. [/proofplan] [step:Start with a small elementary partial map] Let $A, B \subset M$ satisfy $|A|, |B| < \kappa$, and let \begin{align*} f: A \to B \end{align*} be an elementary map, meaning that $f$ is a bijection from $A$ onto $B$ and, for every first-order $L$-formula $\varphi(x_1,\dots,x_n)$ and every tuple $(a_1,\dots,a_n) \in A^n$, \begin{align*} M \models \varphi(a_1,\dots,a_n) \quad \Longleftrightarrow \quad M \models \varphi(f(a_1),\dots,f(a_n)). \end{align*} We will construct an increasing chain of elementary maps \begin{align*} f_\alpha: A_\alpha \to B_\alpha \end{align*} for ordinals $\alpha < \kappa$, where $A_\alpha, B_\alpha \subset M$, $|A_\alpha|, |B_\alpha| < \kappa$, and $f_0 = f$. Choose a map \begin{align*} e: \kappa \to M \end{align*} with the following cofinal repetition property: for every $m \in M$ and every ordinal $\gamma<\kappa$, there are ordinals $\alpha,\beta$ with $\gamma<\alpha,\beta<\kappa$, $\alpha$ even, $\beta$ odd, and \begin{align*} e(\alpha)=m=e(\beta). \end{align*} We construct such a map explicitly. Since $|M|=\kappa$, fix a surjection \begin{align*} q: \kappa \to M. \end{align*} The sets of even and odd ordinals below $\kappa$ each have cardinality $\kappa$, so partition the even ordinals into pairwise disjoint cofinal subsets $(E_\xi)_{\xi<\kappa}$ and partition the odd ordinals into pairwise disjoint cofinal subsets $(O_\xi)_{\xi<\kappa}$. Define $e(\alpha)=q(\xi)$ whenever $\alpha\in E_\xi\cup O_\xi$. Given $m\in M$ and $\gamma<\kappa$, choose $\xi<\kappa$ with $q(\xi)=m$. Since $E_\xi$ and $O_\xi$ are cofinal in $\kappa$, there are $\alpha\in E_\xi$ and $\beta\in O_\xi$ with $\gamma<\alpha,\beta<\kappa$, and then $\alpha$ is even, $\beta$ is odd, and $e(\alpha)=m=e(\beta)$. [/step] [step:Realize the transported type in a forth extension] Suppose $g: C \to D$ is an elementary map between subsets $C,D \subset M$ with $|C|, |D| < \kappa$, and let $c \in M$. We construct an elementary extension of $g$ whose domain contains $c$. If $c \in C$, take the extension to be $g$. Otherwise, define a set of formulas $p_g(y)$ over parameters from $D$ as follows. For each formula $\varphi(y,z_1,\dots,z_n)$ and each tuple $(a_1,\dots,a_n) \in C^n$, put \begin{align*} \varphi(y,g(a_1),\dots,g(a_n)) \in p_g(y) \end{align*} exactly when \begin{align*} M \models \varphi(c,a_1,\dots,a_n). \end{align*} This is the transported complete type of $c$ over $C$ along $g$. We verify finite satisfiability in $M$. Let $\Delta(y)$ be a finite subset of $p_g(y)$. Then there are formulas $\varphi_i(y,z_{i,1},\dots,z_{i,n_i})$ and tuples $a_i \in C^{n_i}$, for $1 \le i \le r$, such that \begin{align*} \Delta(y)=\{\varphi_i(y,g(a_i)) : 1 \le i \le r\}, \end{align*} where $g(a_i)$ denotes the coordinatewise image of the tuple $a_i$. By the definition of $p_g(y)$, \begin{align*} M \models \bigwedge_{i=1}^r \varphi_i(c,a_i). \end{align*} Hence \begin{align*} M \models \exists y\, \bigwedge_{i=1}^r \varphi_i(y,a_i). \end{align*} Since $g$ is elementary, applying elementarity to the displayed existential formula gives \begin{align*} M \models \exists y\, \bigwedge_{i=1}^r \varphi_i(y,g(a_i)). \end{align*} Thus every finite subset of $p_g(y)$ is realized in $M$. By the [Compactness Theorem](/page/Compactness%20Theorem), this finite satisfiability implies that $p_g(y)$ is a consistent type over $D$. The set of parameters used by $p_g(y)$ is contained in $D$, and the number of formulas in $p_g(y)$ is at most $|L|+|D|+\aleph_0<\kappa$, using $\kappa>|L|$, $|D|<\kappa$, and regularity of $\kappa$. Therefore $p_g(y)$ is a consistent type over a parameter set of size $<\kappa$ and has size $<\kappa$. By the definition of [$\kappa$-saturation](/page/Saturated%20Model), there is $d \in M$ realizing $p_g(y)$. Since $c\notin C$, for each $a\in C$ the equality-language formula $y\ne a$ is true of $c$ over $C$, so $p_g(y)$ contains $y\ne g(a)$. Hence $d\ne g(a)$ for every $a\in C$, and therefore $d\notin D$. Define \begin{align*} g': C \cup \{c\} &\to D \cup \{d\} \end{align*} by $g'|_C=g$ and $g'(c)=d$. Then $g'$ is elementary. Let $\psi(x_1,\dots,x_n)$ be any first-order $L$-formula and let $(u_1,\dots,u_n)\in (C\cup\{c\})^n$. Let $I=\{i: u_i=c\}$, and let $(a_1,\dots,a_r)$ list the distinct elements of $\{u_i: u_i\in C\}$. If $I=\varnothing$, preservation of $\psi$ follows from the elementarity of $g$. If $I\ne\varnothing$, form the formula $\theta(y,z_1,\dots,z_r)$ by replacing every coordinate $x_i$ with $y$ when $u_i=c$ and with the appropriate variable $z_j$ when $u_i=a_j$. The definition of $p_g(y)$ and the choice of $d$ give \begin{align*} M \models \theta(c,a_1,\dots,a_r) \quad \Longleftrightarrow \quad M \models \theta(d,g(a_1),\dots,g(a_r)). \end{align*} Unwinding the definition of $\theta$, this is exactly \begin{align*} M \models \psi(u_1,\dots,u_n) \quad \Longleftrightarrow \quad M \models \psi(g'(u_1),\dots,g'(u_n)). \end{align*} Hence $g'$ is an elementary extension of $g$ with $c$ in its domain. [guided] The problem in a forth step is this: we already know how $g$ moves the old parameter set $C$, and we want to decide where a new element $c \in M$ should go so that all formulas remain true after applying the enlarged map. The correct target element must have exactly the same first-order behaviour over $D$ that $c$ has over $C$, after translating parameters through $g$. Assume first that $c \notin C$. We define the transported type $p_g(y)$ over $D$ by declaring that, for each formula $\varphi(y,z_1,\dots,z_n)$ and each tuple $(a_1,\dots,a_n) \in C^n$, \begin{align*} \varphi(y,g(a_1),\dots,g(a_n)) \in p_g(y) \end{align*} if and only if \begin{align*} M \models \varphi(c,a_1,\dots,a_n). \end{align*} Thus $p_g(y)$ records all formulas true of $c$ over the old domain, but with every old parameter $a_i$ replaced by its image $g(a_i)$. We must check that this type can be realized in $M$. Let $\Delta(y)$ be a finite subset of $p_g(y)$. Then $\Delta(y)$ has the form \begin{align*} \Delta(y)=\{\varphi_i(y,g(a_i)) : 1 \le i \le r\}, \end{align*} where each $a_i$ is a finite tuple from $C$. By construction of $p_g(y)$, the element $c$ realizes the corresponding untranslated formulas: \begin{align*} M \models \bigwedge_{i=1}^r \varphi_i(c,a_i). \end{align*} Therefore \begin{align*} M \models \exists y\, \bigwedge_{i=1}^r \varphi_i(y,a_i). \end{align*} Now use the fact that $g$ is elementary. The displayed formula has parameters from $C$, so replacing each parameter tuple $a_i$ by $g(a_i)$ preserves truth: \begin{align*} M \models \exists y\, \bigwedge_{i=1}^r \varphi_i(y,g(a_i)). \end{align*} This says exactly that the finite set $\Delta(y)$ is realized in $M$. Hence every finite subset of $p_g(y)$ is satisfiable in $M$. By the [Compactness Theorem](/page/Compactness%20Theorem), finite satisfiability gives that $p_g(y)$ is a consistent type over the parameter set $D$. The parameter set of $p_g(y)$ is contained in $D$, and $|D|<\kappa$. Also, the type has size $<\kappa$: there are fewer than $\kappa$ formulas because the language has size $|L|<\kappa$, the parameter set has size $|D|<\kappa$, and $\kappa$ is regular and infinite. Thus $p_g(y)$ is a consistent type over a parameter set of size $<\kappa$ and has size $<\kappa$. Since $M$ is [$\kappa$-saturated](/page/Saturated%20Model), some $d \in M$ realizes all of $p_g(y)$. We also need the new image $d$ to be outside the old range $D$, otherwise the enlarged map would not be injective. This follows from the transported type itself. For every $a\in C$, the formula $y\ne a$ is true of $c$ because $c\notin C$. Therefore $p_g(y)$ contains the translated formula $y\ne g(a)$. Since $d$ realizes $p_g(y)$, we have $d\ne g(a)$ for every $a\in C$. As $D=g(C)$, this proves $d\notin D$. Define \begin{align*} g': C \cup \{c\} &\to D \cup \{d\} \end{align*} by $g'|_C=g$ and $g'(c)=d$. We must check preservation for an arbitrary finite tuple, not only for a tuple in which the new element occurs once. Let $\psi(x_1,\dots,x_n)$ be a first-order $L$-formula and let $(u_1,\dots,u_n)\in (C\cup\{c\})^n$. Let $I=\{i: u_i=c\}$, and let $(a_1,\dots,a_r)$ list the distinct old elements among the coordinates $u_i\in C$. If $I=\varnothing$, elementarity of $g$ gives preservation of $\psi$. If $I\ne\varnothing$, define $\theta(y,z_1,\dots,z_r)$ by substituting $y$ into every coordinate occupied by $c$ and substituting $z_j$ into every coordinate occupied by $a_j$. Since $d$ realizes $p_g(y)$, \begin{align*} M \models \theta(c,a_1,\dots,a_r) \quad \Longleftrightarrow \quad M \models \theta(d,g(a_1),\dots,g(a_r)). \end{align*} This is exactly \begin{align*} M \models \psi(u_1,\dots,u_n) \quad \Longleftrightarrow \quad M \models \psi(g'(u_1),\dots,g'(u_n)). \end{align*} Therefore $g'$ is elementary. If $c \in C$, no extension is needed, and $g$ itself already has $c$ in its domain. [/guided] [/step] [step:Realize the transported type in a back extension] Suppose $g: C \to D$ is an elementary map between subsets $C,D \subset M$ with $|C|, |D| < \kappa$, and let $d \in M$. Apply the forth-extension argument to the inverse elementary map \begin{align*} g^{-1}: D \to C \end{align*} and the element $d$. This gives an elementary extension \begin{align*} h: D \cup \{d\} \to C \cup \{c\} \end{align*} of $g^{-1}$ for some $c \in M$. Then \begin{align*} h^{-1}: C \cup \{c\} \to D \cup \{d\} \end{align*} is an elementary extension of $g$ whose range contains $d$. [/step] [step:Build the back-and-forth chain of length $\kappa$] We define $(f_\alpha)_{\alpha<\kappa}$ by transfinite recursion. At $\alpha=0$, set \begin{align*} A_0=A,\qquad B_0=B,\qquad f_0=f. \end{align*} At a limit ordinal $\lambda<\kappa$, define \begin{align*} A_\lambda=\bigcup_{\alpha<\lambda} A_\alpha,\qquad B_\lambda=\bigcup_{\alpha<\lambda} B_\alpha,\qquad f_\lambda=\bigcup_{\alpha<\lambda} f_\alpha. \end{align*} Because the maps are increasing, $f_\lambda$ is a well-defined bijection from $A_\lambda$ onto $B_\lambda$. Since every formula contains only finitely many parameters, its truth under $f_\lambda$ is checked at some earlier stage $\alpha<\lambda$; hence $f_\lambda$ is elementary. At a successor stage $\alpha+1$, write $m_\alpha=e(\alpha)$. If $\alpha$ is even, apply the forth-extension step to $f_\alpha$ and $m_\alpha$, obtaining an elementary extension $f_{\alpha+1}$ whose domain contains $m_\alpha$. If $\alpha$ is odd, apply the back-extension step to $f_\alpha$ and $m_\alpha$, obtaining an elementary extension $f_{\alpha+1}$ whose range contains $m_\alpha$. For every $\alpha<\kappa$, the sets $A_\alpha$ and $B_\alpha$ have cardinality $<\kappa$. Indeed, at each successor stage at most one element is added to each side, and at a limit stage $\lambda<\kappa$ the union has size at most \begin{align*} |A|+|B|+|\lambda|+\aleph_0 < \kappa, \end{align*} using regularity of $\kappa$ and the assumptions $|A|,|B|<\kappa$. [/step] [step:Take the union and obtain an automorphism extending the original map] Define \begin{align*} F: M \to M \end{align*} by \begin{align*} F=\bigcup_{\alpha<\kappa} f_\alpha. \end{align*} For any map $H$, let $\operatorname{dom}(H)$ denote its domain and let $\operatorname{Range}(H)$ denote its range. The map $F$ is well-defined and elementary because the chain is increasing and every formula involves only finitely many parameters, all of which appear in some stage $\alpha<\kappa$. We show that $F$ is total. Let $m \in M$. By the cofinal repetition property of $e$, choose an even ordinal $\beta<\kappa$ such that $e(\beta)=m$. The construction at stage $\beta+1$ puts $m$ into the domain. Thus $\operatorname{dom}(F)=M$. We show that $F$ is surjective. Let $m\in M$. By the cofinal repetition property of $e$, choose an odd ordinal $\beta<\kappa$ such that $e(\beta)=m$. At the successor stage $\beta+1$, the construction applies the back-extension step to $f_\beta$ and $m$, so $m$ lies in the range of $f_{\beta+1}$. Since $f_{\beta+1}\subset F$, we have $m\in \operatorname{Range}(F)$. Thus $\operatorname{Range}(F)=M$. Therefore $F$ is an elementary bijection from $M$ onto $M$. An elementary bijection from an $L$-structure to itself preserves all relation symbols, function symbols, and constants, so it is an automorphism of $M$. Since $f_0=f$ and the chain is increasing, $F$ extends $f$. This proves that $M$ is $\kappa$-homogeneous. [/step]