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 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'. 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, 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.

  • 0
    Thanks, I was being a bit pedantic but it was mainly to check that my logic was sound.2012-03-17