# Elementary end extensions of models of Peano Arithmetic in uncountable languages

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$?

-
My (now deleted) incorrect answer at least showed that the order of quantifiers is not important. If for every $\theta \gt \kappa$ there is a model $N$ of size $\kappa$ with an eee of size at least $\theta$, then the answer to the question is positive by a simple counting argument. –  François G. Dorais Sep 11 '13 at 14:07
Also, we can as well assume that $T$ has Skolem functions, so it is enough if for every $\theta>\kappa$, there is a model of $T$ of size $\theta$ with an initial submodel of size $\kappa$. –  Emil Jeřábek Sep 11 '13 at 14:14
A sufficient condition is that $T$ contains all arithmetic assertions provable in ZFC (or much less), since then $T$ has a model $M$ that appears standard inside a nonstandard (class-sized) model of set theory, and we may consider its ultrapowers as constructed inside that model. These will all be end-extensions, since the ZFC model thinks $M$ is standard. –  Joel David Hamkins Sep 11 '13 at 14:23
The question asks in effect whether the theory $T+{}$ “$I$ is an initial (elementary) substructure” with an extra predicate $I(x)$ has a model of type $(\theta,\kappa)$ for every $\theta>\kappa\ge|L|$. There should be something relevant in the extensive literature on two-cardinal theorems (which I’m unfortunately quite unfamiliar with). –  Emil Jeřábek Sep 11 '13 at 15:26
I think $N$ will have an eee iff the algebra of definable subsets of $N$ supports an ultrafilter $U$ which is "$N$-saturated" in the sense that every definable $f:N \to N$ with bounded range is constant on a set in $U$. I think this is iterable. We can expand $T$ to a second-order theory $ET$ containing $ACA_0$, add a predicate for an ultrafilter $U$ and the axioms to make $U$ a $N$-saturated ultrafilter. If we take the $U$-ultrapower of a model of $ET$, we get an eee which is also a model of $ET$ and we can keep going until we reach $\theta$. Does this make sense or did I miss something? –  François G. Dorais Sep 11 '13 at 16:06

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.


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$.

-
The OP only asked for the existence of $N$ for every $T$. I might be missing something, but if you include in $T^+$ a new symbol $\mathcal U$ and axioms making it an “$N$-saturated” ultrafilter (call this $T^{++}$, say), the existence of $N$ follows from the consistency of $T^{++}$, which in turn should follow from the fact that the usual proof of the MacDowell–Specker theorem applies to any finite sublanguage of $L$. –  Emil Jeřábek Sep 12 '13 at 12:48
@Emil: Yes, $T^{++}$ is what I was thinking all along; it's the natural theory for Fact 3. The intermediate $T^+$ was just simpler to explain. I had to stop before I looked into the consistency of $T^{++}$ but I think your argument works. I'm still stuck with getting the ultrafilter to be admissible. That seems essential for Fact 2... –  François G. Dorais Sep 12 '13 at 13:05
It seems I omitted the sentence that explains that this is not a complete answer to the OP's question. You're more than welcome to finish it if you are so inclined, @Emil. –  François G. Dorais Sep 12 '13 at 13:07
I meant to include admissibility in $T^{++}$, too. The MacDowell–Specker theorem gives not only a proper elementary extension $N\subseteq M$, but one that is conservative in the sense that the intersection with $M$ of any set definable (with parameters) in $N$ is definable in $M$. I believe this makes the $\mathcal U$ defined as in your Fact 1 admissible. –  Emil Jeřábek Sep 12 '13 at 13:14
Well, what I should do is to finally start preparing the tutorial on bounded arithmetic I’m supposed to give in a couple of days, but I’ll see what I can do. –  Emil Jeřábek Sep 12 '13 at 13:56

This is a comment on François Dorais’s excellent post, to show that it in fact yields an affirmative answer to the original question.

Let $T^{++}$ be the extension of $T^+$ in the language $L^{++}=L^+\cup\{U\}$ where $U(X)$ is a unary predicate on the second sort, and axioms postulating that $U$ is a nonprincipal admissible “$N$”-saturated ultrafilter ($N$ being the first-order universe), i.e. \begin{gather*} U(-(X\cap Y))\leftrightarrow\neg(U(X)\land U(Y)),\\ \neg U(\{a\}),\\ \forall x\,\exists y<a\,\langle x,y\rangle\in X\to\exists y<a\,U(\{x:\langle x,y\rangle\in X\}),\\ \exists Y\,\forall x\,(x\in Y\leftrightarrow U(\{y:\langle x,y\rangle\in X\})). \end{gather*} François Dorais’s answer shows that the $L$-reduct of any model of $T^{++}$ is a model of $T$ with arbitrarily large elementary end-extensions, so it suffices to prove that $T^{++}$ is consistent.

The usual MacDowell–Specker theorem states that every model of PA has a proper elementary end-extension. In fact, the theorem shows more: every model $N\models\mathrm{PA}$ has a proper elementary conservative extension $M$, meaning that for every set $X$ definable (with parameters) in $M$, the set $X\cap N$ is definable in $N$. Moreover, the proof of the theorem also applies to extensions of PA with full induction as long as the language is countable.

This is enough to show that every finite fragment of $T^{++}$ is consistent: if $T_0$ is the fragment of $T$ in a finite (or countable) language $L_0\subseteq L$, we take any model $N\models T_0$, and the MacDowell–Specker theorem guarantees the existence of its proper elementary conservative extension $M$. Fix $u\in M\smallsetminus N$, and let $N^{++}=\langle N,\mathcal X,\mathcal U\rangle$, where $\mathcal X$ is the collection of all definable subsets of $N$, and if $X\in\mathcal X$ is defined by a formula $\phi(x,a)$ with $a\in N$, we put $X\in\mathcal U$ iff $M\models\phi(u,a)$. François Dorais shows in Fact 1 that this is an $N$-saturated ultrafilter. It is also admissible: if $X$ is defined by $\phi(x,a)$, then $$\{x\in N:\{y:\langle x,y\rangle\in X\}\in\mathcal U\}=\{x\in N:M\models\phi(\langle x,u\rangle,a)\}$$ is in $\mathcal X$ by the conservativity of the extension. Thus, $N^{++}\models T_0^{++}$.

EDIT: One more comment.

It is easy to see that if $\mathcal U$ is admissible, the ultrapower $N^*$ in Fact 2 is a conservative extension of $N$ (actually, if $|X|\in\mathcal X^*$, then $|X|\cap N\in\mathcal X$). Since conservativity of elementary extensions is transitive and preserved under unions of elementary chains, we get the stronger result that for every theory $T$ and $\kappa$ as in the question, $T$ has a model $N$ of size $\kappa$ with conservative elementary extensions of arbitrary cardinality.

-
Excellent, Emil! This is well deserving of a high-five! –  François G. Dorais Sep 12 '13 at 16:42
High five!‍‍‍‍‍ –  Emil Jeřábek Sep 12 '13 at 17:10
@François: Very well-done both of you. Thanks a lot for your successive efforts which finally solved the problem in this amazing way. Though I was completely unfamiliar with these kinds of arguments (and also with that part of arithmetic that the Tennenbaum phenomena begins to appear), but now I have a good idea of what is going on in the proof. –  shahram Sep 12 '13 at 20:12
That coding in set theory which prepared the ground for using the MacDowell-Specker theorem through a compactness argument was amazing and completely the opposite of what I hoped to occur in this problem. Namely the existence of an eee for a model of arithmetic while the method of MacDowell-Specker doesn’t work. –  shahram Sep 12 '13 at 20:13
@shahram: No problem! We love great questions on MO! Situations like this is when MO gets really fun! (And useful...) Retrospectively, I think Emil deserves the checkmark more than I do since he got the final nail and he merely used my answer as a lemma! –  François G. Dorais Sep 12 '13 at 23:17

It may be of interest to note that Jerabek and Dorais's positive solution to the above question and their use of the MacDowell-Specker theorem motivated me to take a closer look at the following paper of myself:

Sh.Mohsenipour, On Keisler Singular-Like Models, Math. Logic Quart. 54 (2008), 324-330,

in order to obtain another proof and then I realized that the following model theoretic result can be easily derived from the main result of the paper:

Theorem. Suppose $L=\{<,\dots\}$ is a first-order language where $<$ is a linear order and $T$ is an
$L$-theory such that for any finite $T^{'}\subset T$, there is a strong limit cardinal $\theta$ so that $T^{'}$ has a $\theta-$like model $M$ and also $M$ can be represented as the union of an e.e.e. chain of its submodels. Let $\lambda$ be a cardinal $\geq|L|$, then: (i) $T$ has a model $N$ of cardinality $\lambda$ such that $N$ has e.e.e.'s of every cardinality $\geq\lambda$. (ii) If $\lambda$ is a singular cardinal, then the above $N$ can be a $\lambda-$like model with the additional property that for any singular cardinal $\lambda^{'}$ with $cf(\lambda^{'})<\lambda$ and $\lambda^{'}>\lambda$, $N$ has a $\lambda^{'}-$like e.e.e.

Now turning to the above question it is easily seen that the MacDowelـ‎Specker theorem implies that every completion $T$ of $PA(L)$ satisfies the hypothesis of the above theorem and therefore by part (i) we get another solution to the question.

This is a magic property of MO that makes you understand even your own work better!

-