Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2017/iii/paper-130/1/i/solution

Write and let be the given finite coloring of the edges of the complete graph on the positive integers. Construct an increasing sequence and nested infinite sets as follows. Set . Having chosen , take , partition by the color of , and use the infinite pigeonhole principle to choose an infinite set on which this color is constant, say . Every element of exceeds .
The infinite pigeonhole principle applied again to gives an infinite set of indices and a color such that for all . For in , nesting gives , so . Thus the infinite set is a monochromatic complete graph:
This proves the required infinite case of Ramsey's theorem; finiteness of the color set is used at both applications of the infinite pigeonhole principle.

New to topics? Read the docs here!