Intuition behind the construction

Question

This is one of my old homework questions, and my instructor gave a solution. I think I understand why this is true, but its intuition is not obvious. I mean this is kinda magic :) I couldn't think in that way. If you share your ideas or give different answers, it would be great.

Here is the question:

Let $(\mathfrak{M}_n)_{n\in \mathbb{N}}$ be a family of infinite well-orderings, considered in $\mathcal{L}_{ord}=\{<\}$. Let $U$ be a non-principal ultrafilter on $\mathbb{N}$, and let $\mathfrak{M}_U$ be the ultraproduct of the $\mathfrak{M}_n$ with respect to $U$. Prove that there is strictly decreasing sequence in $\mathfrak{M}_U$ of length $\aleph_1$. In particular, $\mathfrak{M}_U$ is not a well-ordering.

This is the sketch proof:

Wlog, we may assume each $\mathfrak{M}_n$ is $(\mathbb{N},\leq)$. We claim that if the sequence $f_i\in \prod \mathfrak{M}_n$ be monotone and unbounded, then there is $f^*\in \prod \mathfrak{M}_n$ monotone and unbounded such that $ [f^*] <_U [f_i] $ for all $i$. From this, we can get $(f_{\alpha})_{\alpha < \omega_1}$, decreasing in $<_U$.

To prove this, we will make sure for each $i$, $\{n| f^*(n)<f_i(n)\}$ is cofinite so that it will be in the ultrafilter $U$, and we are done.

Set $a_0=0$, let $a_k$ be the least such that $a_k>a_{k-1}$ and

$(\forall n \geq a_k) f_0(n), \cdots, f_{k-1}(n)>k$. (1)

Set $f^*(n):=$ least $k$ s.t. $n\geq a_k$. Then we have for $n\in [a_k,a_{k+1})$; $f^*(n)=k$, $f_i(n)>k$ for $i<k$ by (1). So $f^*(n)< f_i(n)$.

Thanks in advance.

Answer 1

It’s hard for me to know what to say, because to me that does seem the natural thing to do: if you have only countably many functions, you can take care of them (i.e., get ‘under’ them) one at a time — not completely, but from some point on, which is good enough. Natural or not, the basic idea is a pretty standard one that you will likely see again.

It might seem a little more natural if you saw a simpler application of the same idea.

Proposition. ${^\omega}\omega$ is the family of functions from $\omega$ to $\omega$. Define a relation $<^*$ on ${^\omega}\omega$ by $f<^*g$ iff $\{n\in\omega:f(n)\ge g(n)\}$ is finite. There is a family $F=\{f_\alpha:\alpha<\omega_1\}\subseteq{^\omega}\omega$ such that $f_\alpha<^*\beta$ whenever $\alpha<\beta<\omega_1$.

Note that $f<^*g$ says that $f(n)<g(n)$ for almost every $n\in\omega$, where almost all means all but finitely many; we might say that $f$ is almost strictly less than $g$. The proposition then says that there is an almost strictly increasing $\omega_1$-sequence in ${^\omega}\omega$. This may at first seem surprising, since there clearly is no strictly increasing $\omega_1$-sequence in ${^\omega}\omega$. But it turns out that almost gives us a great deal of leeway.

The idea of the proof is to construct the functions $f_\alpha$ recursively — one at a time, so to speak — in such a way that when we construct $f_\alpha$, we ensure that $f_\xi<^*f_\alpha$ for each $\xi<\alpha$. We’re able to do this because there are only countably many functions $f_\xi$ with $\xi<\alpha$.

Say there are countably infinitely many of them, and we temporarily enumerate them as $\{g_n:n\in\omega\}$ instead of $\{f_\xi:\xi<\alpha\}$. The idea is to define $f_\alpha$ so that

• $f_\alpha(k)>g_0(k)$ for all $k\in\omega$,
• $f_\alpha(k)>g_1(k)$ for all $k\ge 1$,
• $f_\alpha(k)>g_2(k)$ for all $k\ge 2$,

and so on. This is actually pretty easy: just let

• $f_\alpha(0)=g_0(0)+1$,
• $f_\alpha(1)=\max\{g_0(1),g_1(1)\}+1$,
• $f_\alpha(2)=\max\{g_0(2),g_1(2),g_2(2)\}+1$,

and so on. At each $k\in\omega$ we can ensure that $f_\alpha$ ‘rises above’ one more of the functions $g_n$, and since there are only countably many of those functions, we can force $f_\alpha$ to be above each of them eventually. It’a bit like the diagonal argument for proving the uncountability of the reals: we have countably infinitely many ‘things to take care of’, and we have just enough things to define — here the values $f_\alpha(k)$ — to ‘take care of’ each of them.

Of course and so on won’t do for a proper proof, but now that we have the basic idea, writing it up properly is mostly a matter of experience and practice. Here’s one possible version.

Proof. For $n\in\omega$ let $f_n(k)=n$ for each $k\in\omega$; clearly $f_m<^*f_n$ whenever $m<n<\omega$.¹ We construct $f_\alpha$ for $\omega\le\alpha<\omega_1$ by recursion. Suppose that $\omega\le\alpha<\omega_1$, and $f_\xi$ has been defined for each $\xi<\alpha$. We temporarily re-index $\{f_\xi:\xi<\alpha\}$ as $\{g_n:n\in\omega\}$ and define $f_\alpha$ by setting $$f_\alpha(k)=1+\max\{g_i(k):i\le k\}$$ for each $k\in\omega$. If $\xi<\alpha$, there is some $i\in\omega$ such that $f_\xi=g_i$, and $f_\alpha(k)>g_i(k)=f_\xi(k)$ for all $k\ge i$, so $f_\xi<^*f_\alpha$. Clearly we can carry out this construction as long as $\alpha$ is countable, so in this way we can construct the desired family $F$. $\dashv$

¹ It isn’t actually necessary to start by defining the functions $f_n$ for $n\in\omega$, but it makes matters just a little simpler by letting me start the recursion at $\alpha=\omega$: that way I don’t have to worry about whether $\{f_\xi:\xi<\alpha\}$ is finite or countably infinite. This doesn’t really make the argument any simpler, but it does make the explanation a bit simpler.