# Intuition behind the construction

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) 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 by (1). So $$f^*(n)< f_i(n)$$.

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

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

• Now the trick of magic has come out for me :) I thought most of that you said but I couldn't get my ideas together. Thanks for the clarification. Using this increasing sequence, I can construct the desired decrasing sequence, right? The proof my instructor gave seems more natural now. – Elif Nov 4 '20 at 18:00
• @Elif: You couldn’t use this directly, because there’s more going on in the construction of the decreasing sequence; I chose this example because it really is about as simple as the basic technique gets, so it gives the idea without getting too badly cluttered with details. – Brian M. Scott Nov 4 '20 at 18:24
• Yes, I see. I mean I can use the idea behind this. Your example is quite instructive. – Elif Nov 4 '20 at 18:31