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

Suppose that $n\in \omega$, $m$ is a cardinal and $\kappa, \lambda$ are infinite cardinals. Suppose that any onto function $F:[\kappa]^n \to m$ has the property that there exists a set $H \subseteq \kappa$ with $|H| = \lambda$, such that $F$ is constant on $[H]^n$.

How do I show that if the above is true, then the same is true if I replace $m$ by a smaller cardinal $m'$? I attempted to prove this by taking $F:[\kappa]^n \to m'$ and simply extending the range to $m$. F then becomes a function into $m$ which takes no values in $m \setminus m'$. Then there exists a set $H$ as above and $F$ is constant on $[H]^n$. Then I restricted the range of $F$ back to $m'$.

However this does not work because obviously $F:[\kappa]^n \to m$ is not onto. Does anyone have any ideas as to how to fix this? Thanks very much in advance.

(By $[S]^n$ I mean subsets of size $n$ of $S$).

share|cite|improve this question
up vote 3 down vote accepted

The idea of the argument is very natural, but the details are slightly more annoying than one would have anticipated.

First of all, I am going to assume that $\kappa\ge m$. Otherwise, the given assumption is vacuously true, as no function $F:[\kappa]^n\to m$ is onto. However, in this case the result you want to prove is false, as we can take $m'=\kappa<m$ and let $F:[\kappa]^n\to\kappa$ be a bijection, contradicting the existence of any homogeneous set of size larger than $n$.

So, assume $\kappa\ge m$. (Then actually $\kappa>m$, or else $\kappa=m$ and a bijection as above contradicts the given assumption.)

Ok, we are ready to start the proof. Suppose $F:[\kappa]^n\to m'$ is onto.

Redefine $F(a)$ for a few values $a\in[\kappa]^n$ so the new function is onto. To be specific: For some $i<m'$ there are more than $m$ many $a\in[\kappa]^n$ with $F(a)=i$. This is because the $\kappa$-sized set $[\kappa]^n$ partitions into $m'$ many sets according to the values assigned by $F$. But $m'<m<\kappa$. Now, if $$A_i=\{a\in[\kappa]^n\mid F(a)=i\}$$ has size $\le m$ for all $i$, then $[\kappa]^n$ would have size at most $m'\times m<\kappa$, a contradiction.

Fix some such $i$, and pick distinct sets $a_j\in A_i$ for ordinals $j\in m\setminus m'$. Note that $A_i\setminus\{a_j\mid j\in m\setminus m'\}$ is nonempty because $|A_i|>m\ge|m\setminus m'|$.

Define $F':[\kappa]^n\to m$ as follows: $F'(a)=F(a)$ unless $a=a_j\in A_i$, in which case $F'(a)=j$.

Note that $F'$ is onto $m$, because if $F(a)\ne i$ then $F'(a)=F(a)$, and there are are still values of $a$ such that $F'(a)=i$, since we only redefined $F$ at $|m\setminus m'|<|A_i|$ many places. So at least $F'$ is onto $m'$. But the $a_j$ ensure that $F'$ also takes all values in $m\setminus m'$. So it is onto $m$.

By assumption, this new function $F'$ admits a homogeneous $H$ of size $\lambda$. I claim that $H$ is also homogeneous for $F$. This will complete the proof.

The point is that if $a_j\subset H$ for some $j$ with $m'\le j<m$, then by homogeneity, $F'(a)=j$ for any $a\in[H]^n$. But the only $a\in[\kappa]^n$ with $F'(a)=j$ is $a_j$, by construction. So $|H|= n<\omega\le\lambda=|H|$, a contradiction. This means that if $a\in[H]^n$, then $F'(a)=F(a)$, so $H$ is homogeneous for $F$, as claimed.

share|cite|improve this answer
Thanks for your very helpful answer. In the last paragraph however, if there is only one $a \in [\kappa]^n$ with $F'(a) = j$, then surely that means $|[H]^n|=1$, i.e. that there is precisely one subset of $H$ of size $n$, so $|H| = n$ (as opposed to just $\le$)? – Paul Slevin Mar 16 '12 at 16:51
Hi Paul. Sure, that should have been an equality. I've edited accordingly. – Andrés E. Caicedo Mar 16 '12 at 19:05
Thanks, I was being a bit pedantic but it was mainly to check that my logic was sound. – Paul Slevin Mar 17 '12 at 1:56

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.