2
$\begingroup$

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$).

1 Answers 1

3

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 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$$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$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.

  • 0
    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$)?2012-03-16
  • 0
    Hi Paul. Sure, that should have been an equality. I've edited accordingly.2012-03-16
  • 0
    Thanks, I was being a bit pedantic but it was mainly to check that my logic was sound.2012-03-17