# Ramsey’s theorem

*Ramsey’s theorem* states that a particular arrows relation,

$$\omega \to {(\omega )}_{k}^{n}$$ |

holds for any integers $n$ and $k$.

In words, if $f$ is a function^{} on sets of integers of size $n$ whose range is finite then there is some infinite $X\subseteq \omega $ such that $f$ is constant on the subsets of $X$ of size $n$.

As an example, consider the case where $n=k=2$, and $f:{[\omega ]}^{2}\to \{0,1\}$ is defined by:

$$f(\{x,y\})=\{\begin{array}{cc}1\hfill & \text{if}x={y}^{2}\text{or}y={x}^{2}\hfill \\ 0\hfill & \text{otherwise}\hfill \end{array}$$ |

Then let $X\subseteq \omega $ be the set of integers which are not perfect squares^{}. This is clearly infinite, and obviously if $x,y\in X$ then neither $x={y}^{2}$ nor $y={x}^{2}$, so $f$ is homogeneous on $X$.

Title | Ramsey’s theorem |
---|---|

Canonical name | RamseysTheorem |

Date of creation | 2013-03-22 12:55:49 |

Last modified on | 2013-03-22 12:55:49 |

Owner | mathcam (2727) |

Last modified by | mathcam (2727) |

Numerical id | 9 |

Author | mathcam (2727) |

Entry type | Theorem |

Classification | msc 05D10 |

Related topic | RamseysTheorem2 |

Related topic | GraphTheory |