proof of Ramsey’s theorem


is proven by inductionMathworldPlanetmath on n.

If n=1 then this just states that any partitionMathworldPlanetmathPlanetmath of an infinite setMathworldPlanetmath into a finite number of subsets must include an infinite set; that is, the union of a finite number of finite setsMathworldPlanetmath is finite. This is simple enough to prove: since there are a finite number of sets, there is a largest set of size x. Let the number of sets be y. Then the size of the union is no more than xy.



then we can show that


Let f be some coloringMathworldPlanetmath of [S]n+1 by k where S is an infinite subset of ω. Observe that, given an x<ω, we can define fx:[S{x}]nk by fx(X)=f({x}X). Since S is infinite, by the induction hypothesis this will have an infinite homogeneous set.

Then we define a sequence of integers niiω and a sequence of infinite subsets of ω, Siiω by induction. Let n0=0 and let S0=ω. Given ni and Si for ij we can define Sj as an infinite homogeneous set for fni:[Sj-1]nk and nj as the least element of Sj.

Obviously N={ni} is infinite, and it is also homogeneousPlanetmathPlanetmath, since each ni is contained in Sj for each ji.

Title proof of Ramsey’s theoremMathworldPlanetmath
Canonical name ProofOfRamseysTheorem
Date of creation 2013-03-22 12:55:52
Last modified on 2013-03-22 12:55:52
Owner mathcam (2727)
Last modified by mathcam (2727)
Numerical id 8
Author mathcam (2727)
Entry type Proof
Classification msc 05D10