A proof of the simple pressing down lemma, is sup $x=x?$

Question

I am trying to practice working with ordinals, of which I have only a rudimentary knowledge. The simple pressing down lemma says that if $f:\omega_1\to \omega_1$ satisfies $f(x)<x\ \forall x\in \omega_1,\ $ then $f$ is constant on some unbounded set. The proof is by contradiction, and after being given copious hints, I think I understand the proof, except for the last step:

$1).$ If $g(t)=\sup f^{-1}(t)$ then it follows that $g(t)>t.$

$2).$ Define a sequence in $\omega_1$ by setting $x_0=0,$ and in general $x_{n+1}=\sup\left \{ g(t):t\le x_n \right \}.$

$3).\ x=:\sup \left \{ x_n \right \}$ exists because $\left \{ x_n \right \}$ is countable.

$4).$ The above shows that $x_n< g(x_n)\le g(x_{n+1})$ and now since $f(x)<x$ there is an integer $j$ and an $x_j$ such that $f(x)<x_j$ for otherwise, $f(x)$ would be an upper bound for $\left \{ x_n \right \}.$

$5).$ Then, it follows that $g(f(x))\in \left \{ g(t):t\le x_j \right \}$ so $g(f(x))\le x_{j+1}.$

The next step is where I am not sure if the argument is correct. Can you comment, or provide a more rigorous proof?

$6).$ On the other hand, $1).$ shows that $g(f(x))=\sup x$ and $4).$ implies that $x$ is not a successor ordinal, so $\sup x=\bigcup x=x,$ and we have $x\le x_{j+1}<x_{j+2}$, a contradiction.

Answer 1

I'm confused by your attempt... Here is an alternative proof (which I guess is close to what you had in mind).

Suppose $f$ is not constant on an unbounded set. In other words, for all $y \in \omega_1$ $$ f^{-1} \{y\} = \{x \in \omega_1 \mid f(x) = y \} $$ is bounded. Recursively construct a sequence $(x_n \mid n \le \omega)$ as follows

• $x_0 = \omega$,
• $x_{n +1} = x_n \oplus \min \{ x \in \omega_{1} \setminus \{0\} \mid \forall y \ge x \colon f(y) > x_n \} \ $ and
• $x_{\omega} = \sup_{n < \omega} x_n$.

Note that this is well-defined: $f^{-1} \{ z \mid z \le x_n \}$ is a countable union of bounded subsets of $\omega_1$ and hence bounded. Therefore there is some $x$ such that for all $y \ge x \colon f(y) > x_n$.

Also note that $(x_n \mid n < \omega)$ strictly increasing.

Now consider $f(x_{\omega})$. We have $f(x_{\omega}) < x_{\omega}$ and since $x_{\omega} = \sup_{n < \omega} x_n$ there is thus some $n < \omega$ such that $f(x_{\omega}) < x_n$. But $x_{n+1} < x_\omega$ and hence -- by definition of $x_{n+1}$ -- $f(x_{\omega}) > x_n$. Contradiction!

---

$\oplus$ denotes ordinal addition.