# Does an ultrapower of an Aronszajn tree have an $\omega_{1}$-branch?

Throughout this question, I shall let $A^{\mathcal{U}}$ denote the ultrapower of a structure $A$ by an ultrafilter $\mathcal{U}$. Suppose that $T$ is an Aronszajn tree and $\mathcal{U}$ is an ultrafilter on a countable set $I$. Let $T_{\alpha}$ denote the $\alpha$-th level of a tree $T$. Let $T^{(\mathcal{U})}$ denote the tree where the $\alpha$-th level of $T^{(\mathcal{U})}$ is the ultrapower $(T_{\alpha})^{\mathcal{U}}$ and where if $(x_{i})_{i\in I}/\mathcal{U}\in(T_{\alpha})^{\mathcal{U}},(y_{i})_{i\in I}/\mathcal{U}\in (T_{\beta})^{\mathcal{U}}$, then $(x_{i})_{i\in I}/\mathcal{U}<(y_{i})_{i\in I}/\mathcal{U}$ iff $\{i\in I|x_{i}<y_{i}\}\in\mathcal{U}$. Then $T^{(\mathcal{U})}$ is clearly a tree. In other words, we trim the ultrapower $T^{\mathcal{U}}$ so that it becomes a tree $T^{(\mathcal{U})}$.

Does the tree $T^{(\mathcal{U})}$ have a branch of length $\omega_{1}$? What about when we assume that $T$ is a Suslin tree? What happens when we consider ultraproducts of countably many Aronszajn trees instead of ultrapowers?

• of interest: matwbn.icm.edu.pl/ksiazki/fm/fm118/fm118113.pdf – saf Oct 30 '13 at 19:55
• Contrasting the case of trees of height $\omega_{1}$, if $\kappa$ is a weakly compact cardinal, $|I|<\kappa$, $\mathcal{U}$ is an ultrafilter on $I$ and $T_{i}$ is a tree of height $\kappa$ for $i\in I$, then the $\kappa$-branches of the trimmed ultraproduct of trees $\prod_{i\in I}T_{i}/(\mathcal{U})$ are simply the ultraproducts of the $\kappa$-branches of the trees $T_{i}$ (i.e. taking an ultraproduct does not add any more branches then we have to). The proof of this fact is a straightforward application of the partition relation for weakly compact cardinals. – Joseph Van Name Oct 31 '13 at 21:43
• More generally, assume that if $\kappa,\mu,\lambda$ are cardinals with $\kappa$ regular, $\mu$ measurable or $\mu=\aleph_{0}$, and $\kappa\rightarrow[\kappa]_{\lambda,<\mu}^{2}$. Furthermore, assume that $\mathcal{U}$ is a $\mu$-complete ultrafilter on a set $I$ generated by a set of $\lambda$ many elements and $T_{i}$ is a tree on $\kappa$ of height $\kappa$ for $i\in I$. Then the only $\kappa$ branches on the trimmed ultraproduct of trees $\prod_{i\in I}T_{i}/(\mathcal{U})$ are the ones induced by the ultraproducts of the $\kappa$-branches of the $T_{i}'s$. – Joseph Van Name Oct 31 '13 at 22:06
• Here the partition relation $\kappa\rightarrow[\alpha]^{2}_{\lambda,<\mu}$ means that if $f:[\kappa]^{2}\rightarrow\lambda$, then there is some subset $K\subseteq\kappa$ with $|K|=\alpha$ where $|f[[K]^{2}]|<\mu$. I am unsure if the condition that these conditions are necessary though. – Joseph Van Name Oct 31 '13 at 22:06

Joel David Hamkins asked for the saturation version of Martin Goldstern's argument; here it is. Like Martin, I assume that every node of $T$ has successors at all higher levels. I'll build, by induction on ordinals $\xi<\omega_1$, a branch $(x_\xi)$ in $T^{(U)}$, where $x_\xi$ is at level $\xi$. Of course, I start with the root of $T$ as $x_0$, and at successor steps I let $x_{\xi+1}$ be any immediate successor of $x_\xi$. The existence of an immediate successor follows from my initial assumption about $T$ because $T^U$ is an elementary extension of $T$, and $T^{(U)}$ agrees with $T^U$ at standard levels like $\xi$ and $\xi+1$. Now consider a limit ordinal $\delta$, and suppose we have $x_\xi$ for all $\xi<\delta$, forming a chain in $T^{(U)}$. In the ultrapower with respect to $U$ of the universe (or a part of the universe adequate for what I'm about to do), apply saturation to the type, in one variable $v$, that says "$v$ is an element of the ${}^*\delta$ level of ${}^*T$ and is above each $x_\xi$ for $\xi<\delta$." That's a countable set of formulas, using parameters ${}^*\delta$ (the element of the ultrapower corresponding to $\delta$ in the standard universe), ${}^*T$, and the earlier members $x_\xi$ of the branch. This type is finitely satisfiable; a finite subset requires $v$ to be above only finitely many of the $x_\xi$'s, and the highest of thhose $x_\xi$'s has a successor at level ${}^*\delta$ because of the initial assumption about $T$ (and elementarity). So, by saturation, the whole type is satisfiable, and an element satisfying it serves as $x_\delta$.

• Very nice, and more transparent than my argument. – Goldstern Oct 31 '13 at 8:14

An attempt: Assume that every element of $T$ has a successor on every level. I will define a branch of $T^{(U)}$.

Let $r$ be the root of $T$, and let $x_0$ be the $I$-tuple $(r,r,\ldots)$. (Or rather, its $U$-class.)

Given $x_\alpha$ in the $\alpha$-th level of $T^{(U)}$, define an $I$-tuple $x_{\alpha+1}$ such that $x_{\alpha+1}(i)$ (the $i$-th component of $x_{\alpha+1}$) is a successor of $x_\alpha(i)$.

Now let $\delta$ be a limit ordinal, and let $(\delta_n)$ be a sequence cofinal in $\delta$. For each $n<k$ in $\omega$ let $I_{n,k}:=\{i: x_{\delta_n}(i)< x_{\delta_k}(i)\}$, which by induction hypothesis is in $U$. Let $(I_k)$ be a decreasing sequence of elements of $U$ such that $I_k \subseteq I_{n,k}$ for all $n< k$.

Wlog the intersection of the $I_k$ is empty. For each $i\in I$ let $k=k(i)$ be maximal such that $i\in I_{k(i)}$. Let $x_\delta(i)$ be any element of $T$ on level $\delta$ which extends $x_{\delta_k}(i)$ (which itself extends $x_{\delta_n}(i)$, for all $n<k$).

We have now defined $x_\delta$ on level $\delta$ of $T^{(U)}$, and have to check $x_\gamma<x_\delta$ in $T^{(U)}$ for all $\gamma<\delta$.

It is enough to check this for $\gamma=\delta_n$. I claim that $x_\delta(i) > x_{\delta_n}(i)$ for all $i\in I_n$.

So let $i\in I_n$. Let $k:=k(i)$. Then $k\ge n$. By definition $x_{\delta}(i)>x_{\delta_k}(i) \ge x_{\delta_n}(i)$.

• Great! ${{{}}}$ – Joel David Hamkins Oct 31 '13 at 0:42
• Now that you've shown how to prove this, one can see that your argument for limit levels looks just like the proof that ultrapowers by non-principal ultrafilters on countable sets are $\aleph_1$-saturated (i.e., all countable types are realized). In fact, if one uses this saturation information, one can do the proof directly, without getting into any other ultrapower details. (I confess, though, that it didn't occur to me that there's an easy proof via saturation until after I read your proof.) – Andreas Blass Oct 31 '13 at 0:51
• @Andreas, would it be possible for you to post the saturation argument you have in mind? – Joel David Hamkins Oct 31 '13 at 1:06
• @JoelDavidHamkins: OK, I've posted the argument as an answer. Note though that it's really just Martin's argument; the only change is to invoke saturation rather than proving the particular instance of saturation that's needed. – Andreas Blass Oct 31 '13 at 1:34

This is a footnote to the solution by Blass, and provides a high level explanation (at least when CH holds). The reasoning provided below also takes care of the ultraproduct version of the question.

Theorem. Assume CH. Then the ultrapower $T^\cal{U}$, viewed as a ranked tree, has a proper elementary end extension.

(see top of p.333 of here for the official definition of a ranked tree).

Note that the above immediately implies that the subtree $T^\cal{(U)}$ of $T^\cal{U}$ has an $\omega_1$-branch because the set of predecessors of any node in the end extension, when intersected with $T^\cal{(U)}$, will result in an $\omega_1$-branch.

Outline of the proof of the above theorem: By classical model theory, $T^\cal{U}$ is $\omega_1$-saturated. On the other hand, using CH and elementary cardinal arithmetic, we see that the cardinality of $T^\cal{U}$ is $\omega_1$, and therefore $T^\cal{U}$ is a saturated structure.

We then observe that since $T$ is an $\omega_1$-tree, $T$ satisfies the regularity scheme (which asserts that definable maps from the tree onto a bounded subset of the tree can be made constant by restriction to an unbounded definable subset of the tree). This shows that the ultrapower $T^\cal{U}$ inherits the regularity scheme from $T$.

Recall that saturated structures are resplendent. Our proof is now completed by noting that resplendent ranked trees satisfying the regularity scheme have proper elementary end extensions. The proof of this latter fact uses a compactness argument that succeed, thanks to a theorem of Keisler that asserts that countable tree structures satisfying the regularity scheme have proper elementary end extensions. QED

Remark: Keisler´s aforementioned theorem is established using the same sort of omitting types argument that is used to show that countable models of ZF have proper elementary end extensions (Chang-Keisler, Model Theory, theorem 2.2.18).