Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $\kappa$ be an infinite cardinal, and let $m$ be a cardinal. I want to prove the following statement:

For every onto function $F:\kappa \rightarrow m$ there exists a subset $H \subseteq \kappa$ of size $\lambda$ such that $F$ is constant on $H$ $\iff$ $\kappa > \lambda$ or $\kappa = \lambda $ and $\operatorname{cf}\kappa > m$.

I am having some difficulty however. We may of course assume that $\kappa > m$ and $\kappa \ge \lambda$. So proving the $(\implies)$ direction, suppose that $\kappa \not> \lambda$, i.e. $\kappa = \lambda$. I want to show that $\operatorname{cf} \kappa > m$. However, I am making no progress with this. Similarly with the proof in the other direction.

Can anyone give me some ideas? Thanks very much.

share|cite|improve this question
I'm pretty sure that in the converse, if we suppose that $\kappa > \lambda$ and that we had a partition with less than $\lambda$ in each partition set, then there would be at most $m\lambda$ elements of $\kappa$, which is less than $\kappa$. Again I am having trouble with the cofinality part of the proof. – Paul Slevin Mar 16 '12 at 18:36
up vote 5 down vote accepted

($\Rightarrow$) I'll just demonstrate that $\kappa \rightarrow ( \kappa )^1_{\mathrm{cf} (\kappa)}$ fails.

Denoting $\mathrm{cf} ( \kappa)$ by $m$, let $\langle \alpha_i \rangle_{i < m}$ be a strictly increasing sequence cofinal in $\kappa$. Define $f : \kappa \to m$ by setting $f(\alpha)$ to be the least $i$ such that $\alpha \leq \alpha_i$. It is easy to see that any $f$-homogeneous set must be bounded, and, since $\kappa$ is a cardinal, bounded subsets have cardinality strictly less than $\kappa$.

($\Leftarrow$) Assume first that $\kappa > \lambda$ (and $\kappa > m$), then given $f : \kappa \to m$, consider $\{ f^{-1} \{i\} : i < m \}$. If none of these sets has size at least $\lambda$, then $$\kappa = | \kappa | = \left| \bigcup_{i < m} f^{-1} \{ i \} \right| \leq \sum_{i < m} \left| f^{-1} \{ i \} \right| \leq m \cdot \lambda < \kappa,$$ a contradiction!

If $\kappa = \lambda$ and $\mathrm{cf} (\kappa) > m$, given $f : \kappa \to m$, consider $\{ f^{-1} \{i\} : i < m \}$. If none of these sets has size $\kappa$, I claim that there is a $\mu < \kappa$ such that $\left| f^{-1} \{ i \} \right| \leq \mu$ for all $i < m$.

  • If $\kappa$ is a successor cardinal, then $\kappa = \mu^+$ for some $\mu$, and it easily follows from the above that $\left| f^{-1} \{ i \} \right| \leq \mu$ for all $i < m$.
  • If $\kappa$ is a limit cardinal, then the family of all cardinals $\mu < \kappa$ is cofinal in $\kappa$. As $\left\{ \left| f^{-1} \{ i \} \right| : i < m \right\}$ is a family of $\,\leq m < \mathrm{cf} (\kappa)$ cardinals less than $\kappa$, it follows that it cannot be cofinal in $\kappa$, and so there must be a $\mu < \kappa$ with $\left| f^{-1} \{ i \} \right| \leq \mu$ for all $i < m$.

Taking such a $\mu$, it follows that $$\kappa = | \kappa | = \left| \bigcup_{i < m} f^{-1} \{ i \} \right| \leq \sum_{i < m} \left| f^{-1} \{ i \} \right| \leq m \cdot \mu < \kappa,$$ a contradiction!

share|cite|improve this answer
Is the function you defined in $( \implies )$ onto? – Paul Slevin Mar 17 '12 at 0:03
@Paul: Possibly not, but only for trivial reasons. Change the definition of $f(\alpha)$ to the least $i$ such that $\alpha\le\alpha_i$, and it’s certainly onto, since $f(\alpha_i)=i$. – Brian M. Scott Mar 17 '12 at 0:19
Thank you for this, it's been very helpful – Paul Slevin Mar 17 '12 at 0:21
@Brian: Thanks for the fix. I've included it above (as well as a couple other things that I had originally overlooked). – arjafi Mar 17 '12 at 8:38

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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