Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This a specific question about Ramsey type colorings.

The arrow notation: If $\kappa$, $\lambda$, $\mu$ are cardinals and $n<\omega$, then $$\kappa\rightarrow(\lambda)^n_\mu$$ if for any function $f:[\kappa]^n\longrightarrow\mu$ (where $[\kappa]^n$ is the set of subsets of $\kappa$ of size $n$), there is a subset $A\subseteq\kappa$ of size $\lambda$ such that $f$ is constant on $[A]^n$.

I am aware of the traditional Ramsey's Theorem, which talks about this arrow notation for countable cardinals; as well as the Erdős-Rado theorem, which says $$(\beth_n(\kappa))^+\rightarrow(\kappa^+)^{n+1}_{\kappa}$$ for any infinite $\kappa$.

My questions are:

  1. For what infinite cardinals $\kappa$ is it true that $\kappa^+\rightarrow(\omega)^2_\kappa$

  2. For what infinite cardinals $\kappa$ is it true that $2^\kappa\rightarrow(\omega)^2_\kappa$

share|improve this question
    
I'm pretty sure the answer is never, but I don't recall the proof off hand. In fact, I think you can replace $\omega$ with 3. –  Shawn Henry Oct 25 '12 at 18:57
    
@Shawn: Your memory’s correct. –  Brian M. Scott Oct 25 '12 at 19:17

1 Answer 1

up vote 2 down vote accepted

It’s a result of Erdős and Kakutani that $2^\kappa\not\to(3)^2_\kappa$. Let $\Sigma={^\kappa\{0,1\}}$, and define

$$\varphi:[\Sigma]^2\to\kappa:\{\sigma,\tau\}\mapsto\min\{\xi<\kappa:\sigma(\xi)\ne\tau(\xi)\}\;.$$

Let $\rho,\sigma,\tau$ be distinct elements of $\Sigma$; if $\varphi(\rho,\sigma)=\varphi(\sigma,\tau)=\xi$, then $\rho(\xi)=\tau(\xi)$, and therefore $\varphi(\rho,\tau)\ne\xi$.

In particular, $2^\omega\not\to(3)^2_\omega$, and hence $\omega_1\not\to(3)^2_\omega$. It follows that $2^\kappa\not\to(\omega)^2_\kappa$ and $\kappa^+\not\to(\omega)^2_\kappa$ for any infinite cardinal $\kappa$.

share|improve this answer

Your Answer

 
discard

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.