Pigeonhole principle for ordinal numbers

102 Views Asked by At

Using transfinite induction, I have been able to prove:

Let $a,b,c$ be nonzero ordinal numbers such that $c \times b < a$. Let $f: a \rightarrow b$ be an increasing function. Then there is $d<a$ such that $f$ is constant on the interval $\left[d,d+c\right]$.

But it seems like a stronger version might be true:

Lat $0<b<a$. Let $f: a \rightarrow b$ be an increasing function. Then there is $d<a$ such that $f$ is constant on the interval $\left[d,d+\inf\{c+1:c \times b < a\}\right)$.

However, I've had some difficulties proving it. Does it hold?

1

There are 1 best solutions below

0
On BEST ANSWER

Given a function $f: a \rightarrow b$ which is non-decreasing, let $f_{\gamma},\gamma<\mu_f$ be the strictly increasing enumeration of diameters of intervals where $f$ is constant. By that I mean that $f$ is constant on $[0,f_0)$, with $f(f_0)>f(0)$, then again constant on $[f_0,f_0+f_1)$ with $f(f_0+f_1)>f(f_0)$ and so on... Notice that this enumeration is uniquely determined by $f$.

I interpret your question as looking for a description of the function $\Psi:(a,b) \mapsto \min \{\sup \limits_{\gamma<\mu_f} f_{\gamma} : f: a\rightarrow b\}$.

Consider such function $f$ and write $c:=\sup \limits_{\gamma<\mu_f} f_{\gamma} $. You can see that we have $a=\sum \limits_{\gamma<\mu_f} f_{\gamma}$ so $a \leq c \ \mu_f$. Notice that this could be an equality. We also have a strictly increasing map $\mu_f \rightarrow b$ given by $\gamma \mapsto f(\sum \limits_{\eta<\gamma} f_{\eta})$, so $\mu_f\leq b$ (again, possibly an equality) so $a\leq c \ b$.

This proves that for $c'$ with $a>c' \ b$, we have $c+1\leq c$ so $c+1\leq \Psi(a,b)$. Thus your conjecture (which I assume is with $\sup$ instead of $\inf$) is true.