Preliminaries. I was wondering how much this specific example depends on the choice of ultrafilter. Let $\mathcal U$ be a free (i.e., non-principal) ultrafilter over $\mathbb N$ and consider the structures $$\mathcal A_n = \langle\{ 0, 1, 2, \dots, n\}, \leq \rangle.$$ Then the ultraproduct $$\left. \mathcal A = \left(\prod_{n \in \mathbb N}\mathcal A_n \right) \middle/ \mathcal U \right.$$ is totally-ordered, discrete and has a minimal and a maximal element, all by the Łoś Ultraproduct Theorem. We can even write down concrete representatives of the smallest (bottom) and biggest (top) elements $$\bot = [\langle 0, 0, 0, \dots\rangle]_{\mathcal U}\\ \top = [\langle 0, 1, 2, \dots\rangle]_{\mathcal U}$$ respectively, independent of $\mathcal U$. In fact, the successor $\bot_+$ of $\bot$ also has an explicit representative, namely $\bot_+=[\langle 0, 1, 1, \dots\rangle]_{\mathcal U}$. Continuing like this, we get explicit representatives of all finite successors of the bottom element.

Similarly, the predecessor $\top_-$ of $\top$ is $[\langle 0, 0, 1, 2, \dots \rangle]_\mathcal U$ (because it is the predecessor at all but finitely many indices). So we also get explicit representatives of all finite predecessors of $\top$.

Question. The above makes it seem reasonable to ask whether the ultraproduct $\mathcal A$ is isomorphic to the structure $$ \mathcal B = \mathcal N \sqcup \mathcal N^{\text{op}},$$ where $\mathcal N$ is the natural numbers with the standard order, $\mathcal N^{\text{op}}$ is the natural numbers with the opposite of the standard order, and $\sqcup$ denotes the disjoint union. Is this true? If not, does the isomorphism type of $\mathcal A$ depend on the ultrafilter $\mathcal U$?

  • 2
    $\begingroup$ The ultraproduct is uncountable, so definitely not $\cal B$. $\endgroup$
    – Asaf Karagila
    Nov 7, 2019 at 14:49
  • 2
    $\begingroup$ This is kinda standard, show that there is a continuum size family of almost disjoint sets whose characteristics are $\cal U$ distinct. Work out from there. Perhaps easier, show that any countably many functions can be bounded almost everywhere and conclude the confilaity of your order is uncountable. $\endgroup$
    – Asaf Karagila
    Nov 7, 2019 at 15:09
  • 1
    $\begingroup$ Levi, "Didn't see that coming, how can you see this?" Suppose $A,B$ are almost disjoint, that is, $A\cap B$ is finite and $A,B$ are infinite subsets of $\mathbb N$. Show that their characteristic functions are different modulo $\mathcal U$. There is a family of size $\mathfrak c$ of pairwise almost disjoint subsets of $\mathbb N$. This shows that the ultrapower has size continuum. $\endgroup$ Nov 7, 2019 at 15:09
  • 1
    $\begingroup$ More generally, in one of Shelah's first papers he shows by a cute argument coding fragments of arithmetic that any infinite ultrapower of finite structures has size $\lambda$, where $\lambda^{\aleph_0}=\lambda$. You are looking at the particular case where the ultrafilter is on $\mathbb N$. $\endgroup$ Nov 7, 2019 at 15:12
  • 3
    $\begingroup$ @Levi Any question about ultraproducts that can't be answered by just appealing to Łoś's theorem usually turns out to secretly be about set theory! $\endgroup$ Nov 7, 2019 at 17:22

1 Answer 1


First, let me make the pedantic point that if $\mathcal{U}$ is a principal ultrafilter (generated by $n\in \mathbb{N}$), then the ultraproduct will be isomorphic to $\mathcal{A}_n$. Ok, so let's agree to consider only non-principal ultrafilters from now on.

Here's what I can tell you about the situation:

  • Every ultraproduct of a family of structures (in a countable language) by a countably incomplete ultrafilter is $\aleph_1$-saturated (see Theorem 6.1.1 in Model Theory by Chang and Keisler, or Theorem 5.3 in this expository paper by Kyle Gannon). Every non-principal ultrafilter on $\mathbb{N}$ is countably incomplete, so every ultraproduct of the kind you're considering is $\aleph_1$-saturated.

  • In particular, if you write $\mathcal{N}$ for the initial segment isomorphic to $\mathbb{N}$ and $\mathcal{N}^*$ for the end segment isomorphic to $\mathbb{N}^{\text{op}}$, then the type $\{x > n\mid n\in \mathcal{N}\}\cup \{x < n \mid n\in \mathcal{N}^*\}$ is realized in the ultraproduct. So your ultraproduct is not isomorphic to $\mathcal{B}$. Actually, we don't need to appeal to the theorem to see that this type is realized: it's realized by $[\langle 0, 1, 1, 2, 2, 3, 3, \dots\rangle]_\mathcal{U}$.

  • Every ultraproduct of the $\mathcal{A}_n$ by a non-principal ultrafilter will be an infinite discrete linear order with endpoints by Łoś's theorem. The first-order theory $T$ of infinite discrete linear orders with endpoints is complete, so any two ultraproducts of the $\mathcal{A}_n$ will be elementarily equivalent. That is, the theory of the ultraproducts doesn't depend on the ultrafilter, but the isomorphism type might.

  • Any model of $T$ looks like $\mathcal{N} \sqcup \bigsqcup_{i\in \mathscr{L}} \mathcal{Z} \sqcup \mathcal{N}^{\text{op}}$, where $\mathcal{N}$ is the order type of the natural numbers, $\mathcal{N}^{\text{op}}$ is its opposite, each $\mathcal{Z}$ is the order type of the integers, and these copies of $\mathcal{Z}$ are ordered like an arbitrary linear order $\mathscr{L}$. This last claim is not too hard to prove just by thinking about what the axioms of $T$ say - the completeness of $T$ is a little tricker, but it follows from an Ehrenfeucht-Fraïssé game argument. So your question now comes down to: What order types $\mathscr{L}$ can arise from this ultraproduct?

  • Every ultraproduct of a countable family of finite structures of unbounded size by a non-principal ultrafilter has cardinality $2^{\aleph_0}$. (For example, see this answer.) This gives another reason why your ultraproduct is not isomorphic to $\mathcal{B}$.

  • Any two saturated (i.e. $\kappa$-saturated where $\kappa = |M|$) structures of the same cardinality which are elementarily equivalent are isomorphic. So if we assume that continuum hypothesis, then for any non-principal ultrafilters $\mathcal{U}_1$ and $\mathcal{U}_2$ on $\mathbb{N}$, we have $$\prod_{n\in \mathbb{N}} \mathcal{A}_n/\mathcal{U}_1\cong \prod_{n\in \mathbb{N}} \mathcal{A}_n/\mathcal{U}_2$$ because both structures are $\aleph_1$-saturated of cardinality $2^{\aleph_0} = \aleph_1$, and they are both models of the complete theory $T$ of discrete linear orders without endpoints. Thus, under CH, the choice of ultrafilter doesn't matter. The structure $\prod_{n\in \mathbb{N}} \mathcal{A}_n/\mathcal{U}_1$ is always isomorphic to $\mathcal{N} \sqcup \bigsqcup_{i\in \overline{\mathscr{L}}} \mathcal{Z} \sqcup \mathcal{N}^{\text{op}}$, where $\overline{\mathscr{L}}$ is the unique saturated linear order of size $2^{\aleph_0}$ (which exists if we assume CH).

  • On the other hand, if CH fails, we still know that the ultraproduct is isomorphic to $\mathcal{N} \sqcup \bigsqcup_{i\in \mathscr{L}} \mathcal{Z} \sqcup \mathcal{N}^{\text{op}}$, for some $\aleph_1$-saturated linear order $\mathscr{L}$ of size $2^{\aleph_0}$, but exact order type $\mathscr{L}$ of the copies of $\mathcal{Z}$ may depend on your choice of ultrafilter.

  • $\begingroup$ I thought it's not really about countable incompleteness, but rather regularity of the ultrafilters which is kinda trivial for free ultrafilters on $\omega$, no? $\endgroup$
    – Asaf Karagila
    Nov 7, 2019 at 15:18
  • $\begingroup$ Also, do you know if something like MA or PFA, or some reasonable forcing axiom, would prove that $\scr L$ is somehow unique? $\endgroup$
    – Asaf Karagila
    Nov 7, 2019 at 15:20
  • $\begingroup$ Didn't expect this to depend on the continuum hypothesis, nice answer. Could you, by any chance, provide a source (or explanation) of why the two structures in your fourth point are $\aleph_1$-saturated and how this implies that they are isomorphic? (I understand if that's too much effort, maybe I will encounter saturation later on in my course on model theory, in which case I might be able to work this out myself.) $\endgroup$
    – Levi
    Nov 7, 2019 at 15:39
  • 1
    $\begingroup$ @Levi The $\aleph_1$-saturation is by point 1, where I provided two sources (the textbook by Chang & Keisler and the expository paper by Gannon). The combinatorics are a bit tricky, so I can't give a proof summary that fits in this comment. For the theorem "Any two saturated models of the same complete theory which have the same cardinality are isomorphic", you can see any textbook in model theory. This one does have an easy summary: it's a back-and-forth argument. I also added a point that the ultraproducts must be elementarily equivalent. $\endgroup$ Nov 7, 2019 at 17:02
  • $\begingroup$ @AsafKaragila Well, an ultrafilter is countably incomplete if and only if it's ($\omega$-)regular. And yes, regularity is the key combinatorial condition in the proof. I stated it in terms of countable incompleteness because that notion is a little easier to understand, and that's how the theorem is stated in Chang & Keisler. $\endgroup$ Nov 7, 2019 at 17:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .