A well-known theorem of Mills asserts that there is a model of Peano Arithmetic $M$ in an uncountable language such that $M$ has no elementary end extension (e.e.e.). I ask whether every complete extension of $PA$ in an uncountable language can have models of every cardinality with arbitrary large e.e.e.'s. To put it in more precise form, suppose $L$ is an uncountable language expanding the language of arithmetic $\{+,.,0,1,<\}$. By $PA(L)$ we mean $PA^{-}$ plus the induction axiom for all $L$-formulas $\phi(x,\bar{y})$. Let $T$ be a complete $L$-theory extending $PA(L)$ and let $\kappa$ be a cardinal $\geq |L|$.


Question. Does $T$ have a model $N$ such that $|N|=\kappa$ and $N$ has e.e.e.'s of every cardinality $\geq\kappa$?



Elementary end extensions of models of Peano Arithmetic in uncountable languages
Apologies for completely rewriting this answer. It took a long time to organize and verify all the details.


The following outlines a proof of the following:


**Theorem.** *Every model $N$ of $T$ which has an expansion to a model $(N,\mathcal{X})$ of $T^+$ for which there is an admissible $N$-saturated ultrafilter on $\mathcal{X}$ has arbitrarily large elementary end-extensions.*


Terms and notations are defined below. Fact 1 below shows that the hypotheses are not that exceptional and the above might be reasonably close to a characterization of all models of $T$ that admit arbitrarily large elementary end-extensions.


Also note that Joel's comment is a special case of the above. Indeed, if $N$ is an expansion of the natural numbers in a model $V$ of ZFC, then $(N,\mathcal{P}(N)^V)$ is a model of $T^+$ and any ultrafilter on $\mathcal{P}(N)^V$ inside $V$ is admissible and $N$-saturated.




---


$\newcommand{\EL}{L^+}\newcommand{\ET}{T^+}$
Let $\EL$ be the expansion of $L$ with another sort for sets of numbers and a membership relation $\in$ between numbers and sets. I will try to separate the two sorts by using lower case for numbers and upper case for sets. There is no equality for sets, instead I will write $X = Y$ to abbreviate $\forall n(n \in X \leftrightarrow n \in Y)$ and similarly for the usual set notions such as $X \subseteq Y$, $Z = X \cap Y$, etc. A formula of $\EL$ without set quantifiers (but possibly unquantified set variables) will be called an *arithmetical formula*.


Let $\ET$ be the theory in the language $\EL$ that contains $T$, has comprehension for arithmetical formulas and induction for sets. A model of $\ET$ can be thought of as a pair $(N,\mathcal{X})$ where $N$ is the number sort and $\mathcal{X}$ is a collection of actual subsets of $N$. There is no requirement for the set sort to consist of actual subsets of $N$ but these models are sufficient for all purposes. Note that if $N$ is a model of $T$ then $(N,\mathcal{X})$ is a model of $\ET$ where $\mathcal{X}$ consists of all subsets of $N$ that are definable (with parameters).


The sets of a model of $\ET$ can encode a variety of things, especially when used in conjunction with a primitive recursive pairing function $\langle m, n \rangle$. For example, functions $N \to N$ can be encoded by their graphs and functions $N \to \mathcal{X}$ can be encoded by $n \mapsto X\_n = \{m \in N : \langle m, n \rangle \in X\}$. Functions that can be represented in this way will be called *coded functions*.


Then $(N,\mathcal{X})$ is a model of $\ET$ then $\mathcal{X}$ is an algebra of subsets of $N$ since the comprehension axioms ensure that $\mathcal{X}$ is closed under union, intersection and complements. Let $\mathcal{U}$ be an ultrafilter on $\mathcal{X}$. We say that $\mathcal{U}$ is *$N$-saturated* if every coded function $N \to N$ with bounded range is constant on a set from $\mathcal{U}$. We say that $\mathcal{U}$ is *admissible* if $\{ n \in N : X\_n \in \mathcal{U}\} \in \mathcal{X}$ for every $X \in \mathcal{X}$.


**Fact 1.** *A model $N$ of $T$ admits an elementary end extension if and only if it has an expansion to a model $(N,\mathcal{X})$ of $\ET$ such that $\mathcal{X}$ has an $N$-saturated ultrafilter.*


The forward direction uses all definable subsets of $N$ to interpret the set sort. It's not hard to see that comprehension and induction hold for all arithmetic formulas. To interpret $\mathcal{U}$, we fix an elementary end-extension $M$ and some $u \in M - N$. The set $X$ is in $\mathcal{U}$ iff some (hence every) defining formula $\phi(n)$ for $X$ holds at $u$. It's easy to check that this is a nonprincipal ultrafilter. For the saturation axiom, suppose $\phi(x,y)$ defines a function $f:N \to N$ with range bounded by $z$. Then, by elementarity, $\phi(x,y)$ also defines a function $f':M\to M$ whose range is still bounded by $z \in N$. Since $N$ is an initial segment of $M$, $f(u)$ is an element of $N$ and the definable set $\{n \in N : \phi(n,f(u))\}$ must be in $\mathcal{U}$.


For the reverse direction, we will use a sort of ultrapower construction with the given $N$-saturated ultrafilter $\mathcal{U}$. The end extension $N^\*$ will consist of equivalence classes $[F]$ of coded functions $F:N \to N$, where $F,G:N \to N$ are $\mathcal{U}$-equivalent if $\{ n \in N : F(n) = G(n)\} \in \mathcal{U}$. The non-logical symbols of $L$ are interpreted in the usual manner, e.g. $[F] \leq [G]$ iff $\{n \in N : F(n) \leq G(n)\} \in \mathcal{U}$. Arithmetic comprehension ensures that Łoś's theorem works for this context, and therefore we have an elementary embedding $N \to N^\*$ via equivalence classes of constant functions. The fact that $\mathcal{U}$ is $N$-saturated ensures that $N^\*$ is an end-extension. Indeed, $N$-saturation plainly says that every coded function $F:N \to N$ which is bounded by a constant function is equivalent to a constant function.


Unfortunately, Fact 1 does not ensure that the elementary end-extension $N^\*$ also has an elementary end-extension. To do that, we can add the requirement that the ultrafilter is admissible.


**Fact 2.** *If a $(N,\mathcal{X})$ is a model of $\ET$ and there is an admissible $N$-saturated ultrafilter on $\mathcal{X}$ then $(N,\mathcal{X})$ has an end-extension $(N^\*,\mathcal{X}^\*)$ which is elementary for arithmetic formulas and such that there is also an admissible $N^\*$-saturated ultrafilter on $\mathcal{X}^\*$.*


Let $\mathcal{U}$ be an admissible $N$-saturated ultrafilter on $\mathcal{X}$. We can define the elementary end-extension $N^\*$ as above and then expand to a model $(N^\*,\mathcal{X}^\*)$ of $\ET$ as follows. The elements of $\mathcal{X}^\*$ are of the form $$|X| = \{ [F] \in N^\* : \{n \in N : F(n) \in X\_n\} \in \mathcal{U}\}.$$ The embedding $N \to N^\*$ extends to $\mathcal{X} \to \mathcal{X}^\*$ via constant functions, i.e. the image of $X$ under this embedding is the set $$\{[F] \in N^\* : \{ n \in N : F(n) \in X\} \in \mathcal{U}\}.$$


Łoś's theorem extends to arithmetial formulas but since $(N,\mathcal{X})$ may lack countable choice for sets, this cannot usually be extended to formulas with set quantifiers. It follows that the embedding $(N,\mathcal{X}) \to (N^\*,\mathcal{X}^\*)$ is elementary for arithmetical formulas. Łoś's theorem for arithmetial formulas also shows that $(N^\*,\mathcal{X}^\*)$ satisfies arithmetic comprehension.


The required ultrafilter on $\mathcal{X}^\*$ is $$\mathcal{U}^\* = \left\{|X| \in \mathcal{X}^\* : \{n \in N : X\_n \in \mathcal{U}\} \in \mathcal{U}\right\}.$$ This is well-defined since $\mathcal{U}$ is admissible and it is not hard to see that this is indeed an ultrafilter on $\mathcal{X}^\*$. To see that $\mathcal{U}^\*$ is admissible, note that for $|X| \in \mathcal{X}^\*$ and $[F] \in N^\*$, we have $$|X|\_{[F]} = |\{\langle m, n \rangle : m \in X\_{F(n)}\}|.$$ Therefore, $|X|\_{[F]} \in \mathcal{U}^\*$ if and only if $$\left\{ n \in N : F(n) \in \{m \in N : X\_m \in \mathcal{U}\}\right\} \in \mathcal{U}.$$ In other words, the required set $$\{[F] \in N^\* : |X|\_{[F]} \in \mathcal{U}^\*\}$$ is simply the image of $\{ n \in N : X\_n \in \mathcal{U}\}$ under the embedding $\mathcal{X} \to \mathcal{X}^\*$.


To see that $\mathcal{U}^\*$ is $N^\*$-saturated, suppose that $|H| \in \mathcal{X}^\*$ encodes the graph of a function whose values are bounded above by $[F] \in N^\*$. By Łoś's theorem for arithmetial formulas, there is a set $U \in \mathcal{U}$ such that if $n \in U$ then $H\_n$ is the graph of a function $N \to N$ whose values are bounded by $F(n)$. Since $\mathcal{U}$ is $N$-saturated, there is a $m \leq F(n)$ such theat $H\_n^{-1}(m) \in \mathcal{U}$. Because $\mathcal{U}$ is admissible, the set $$G = \{ \langle m, n \rangle \in N : (n \notin U \land m = 0) \lor (n \in U \land H\_n^{-1}(m) \in \mathcal{U}) \}$$ exists in $\mathcal{X}$. Furthermore, $G$ is the graph of a function $N \to N$ such that $|H|$ is constant with value $G$ on a set in $\mathcal{U}^\*$.


Having dealt with successor steps of the iteration, we now deal with limit steps of the iteration. Suppose $$(N\_0,\mathcal{X}\_0) \to (N\_1,\mathcal{X}\_1) \to \cdots$$ is a sequence of end-extensions of models of $\ET$, each step of which is elementary for arithmetic formulas. It's easy to see that the limit $(N\_\omega,\mathcal{X}\_\omega)$ is a model of $\ET$ and the extension $(N\_i,\mathcal{X}\_i) \to (N\_\omega,\mathcal{X}\_\omega)$ is elementary for arithmetic formulas. To ensure that this sequence can be continued further, we record the following simple observation.


**Fact 3.** If at each step of the sequence above we have an admissible $N\_i$-saturated ultrafilter $\mathcal{U}\_i$ on $\mathcal{X}\_i$ and the image of $\mathcal{U}\_i$ is through the embedding $\mathcal{X}\_i \to \mathcal{X}\_{i+1}$ contained in $\mathcal{U}\_{i+1}$, then the limit of these $\mathcal{U}\_i$ is an adimissible $N\_\omega$-saturated ultrafilter $\mathcal{U}\_\omega$ on $\mathcal{X}\_\omega$.


Observe that the construction for Fact 2 is that $\mathcal{U}^\*$ extends the image of $\mathcal{U}$ through the embedding $\mathcal{X} \to \mathcal{X}^\*$. Therefore, using Fact 2 at successor steps leads to a situation where we can use Fact 3. Although it was only stated for sequences of length $\omega$ for the sake of simplicity, Fact 3 obviously generalizes to arbitrary lengths. Iterating for $\theta$ steps leads to an end extension of size $\theta$.


