# Regressive problem with ordinals regarding countability

• November 16th 2009, 09:52 AM
tcRom
Unanswered - Regressive problem with ordinals regarding countability
I've spent a lot of time thinking about this problem, but I'm running out of time and need a skeleton of the process to solve it if someone wants to tackle it...

Prove:
If $f: \omega_{1} \rightarrow \omega_{1} \wedge \forall \alpha \in \omega_{1} (f(\alpha)<\alpha \vee f(\alpha)=0) \exists \alpha_{0} \in \omega_{1}$ such that the set $\{ \alpha \in \omega_{1}: f(\alpha)= \alpha_{0} \}$ is uncountable.

I've been trying to do this by finding a counterexample to the following sentence

let $f: \omega_{1} \rightarrow \omega_{1} \wedge \forall \alpha \in \omega_{1} (f(\alpha)<\alpha \vee f(\alpha)=0), \Rightarrow \forall \alpha_{0} \in \omega_{1}$ the set $\{ \alpha \in \omega_{1}: f(\alpha)= \alpha_{0} \}$ is countable.

If I can find a single counterexample, then the original problem is true. I've looked at unions to see if I can get high enough in the ordinals so that uncountably many things drop to $\alpha$ when applying the function, but that would mean $\forall \gamma \in \omega_{1} \exists \alpha \in \omega_{1} (\cup \gamma = \alpha, \alpha < \gamma)$ is true. Which, according to my professor, it is not.

• November 16th 2009, 10:02 AM
gmatt
is omega a subset of the reals? or just any set. Are there any other conditions on f?
• November 16th 2009, 10:14 AM
tcRom
In this case, $\omega_{1}$ is the first uncountable ordinal. f is just a function that maps $f:\omega_{1} \rightarrow \omega_{1}$ where the output is less than the input or equal to 0.

For example, if we were using the naturals the following could be possible:
f(0) = 0
f(1) = 0
f(2) = 0 or 1
f(3) = 0 or 1 or 2
.
:
f(n) = anything less than n

So, f is not actually defined in the problem, that's what I am trying to do; define f so that it maps an uncountable number of things to $\alpha_{0}:\alpha_{0} \in \omega_{1}$. I hope that clarifies things.
• November 16th 2009, 10:27 AM
gmatt
I'm pretty sure to prove that statement you have to show that any function that satisfies the criteria will have a a_0 so that the preimage of a_0 is uncountable. I'll think about this and see if I can come up with anything, my intuition says that to show uncountablility you may have to use cantor's trick: Cantor's diagonal argument - Wikipedia, the free encyclopedia this is just my intuition though, I'll think about it.
• November 18th 2009, 09:11 AM
tcRom
What about doing this with limit ordinals? Say we choose an $\alpha_{0}$ and look at the limit of it's inverse image, then we do the same for everything in $\alpha_{0}$. So, the next thing we choose above $\alpha_{0}$ must come from above the highest limit ordinal that anything in $\alpha_{0}$ mapped to. If we keep going with this, we'll eventually find a $\beta$ that maps to itself, a contradiction. Thus, the assumption that everything in our set is countable is false, making the original statement true.

Any thoughts?