5
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ – Elif Nov 4 '20 at 18:00
  • $\begingroup$ @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. $\endgroup$ – Brian M. Scott Nov 4 '20 at 18:24
  • 1
    $\begingroup$ Yes, I see. I mean I can use the idea behind this. Your example is quite instructive. $\endgroup$ – Elif Nov 4 '20 at 18:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.