Infinite Version Implies The Finite
It is possible to deduce the finite Ramsey theorem from the infinite version by a proof by contradiction. Suppose the finite Ramsey theorem is false. Then there exist integers such that for every integer, there exists a -colouring of without a monochromatic set of size . Let denote the -colourings of without a monochromatic set of size .
For any k, the restriction of a colouring in to (by ignoring the colour of all sets containing ) is a colouring in . Define to be the colourings in which are restrictions of colourings in . Since is not empty, neither is .
Similarly, the restriction of any colouring in is in, allowing one to define as the set of all such restrictions, a non-empty set. Continuing so, define for all integers .
Now, for any integer, and each set is non-empty. Furthermore, is finite as . It follows that the intersection of all of these sets is non-empty, and let . Then every colouring in is the restriction of a colouring in . Therefore, by unrestricting a colouring in to a colouring in, and continuing doing so, one constructs a colouring of without any monochromatic set of size . This contradicts the infinite Ramsey theorem.
If a suitable topological viewpoint is taken, this argument becomes a standard compactness argument showing that the infinite version of the theorem implies the finite version.
Read more about this topic: Ramsey's Theorem
Famous quotes containing the words infinite, version, implies and/or finite:
“Hath not the morning dawned with added light?
And shall not evening call another star
Out of the infinite regions of the night,
To mark this day in Heaven? At last, we are
A nation among nations; and the world
Shall soon behold in many a distant port
Another flag unfurled!”
—Henry Timrod (1828–1867)
“Truth cannot be defined or tested by agreement with ‘the world’; for not only do truths differ for different worlds but the nature of agreement between a world apart from it is notoriously nebulous. Rather—speaking loosely and without trying to answer either Pilate’s question or Tarski’s—a version is to be taken to be true when it offends no unyielding beliefs and none of its own precepts.”
—Nelson Goodman (b. 1906)
“The student may read Homer or Æschylus in the Greek without danger of dissipation or luxuriousness, for it implies that he in some measure emulate their heroes, and consecrate morning hours to their pages.”
—Henry David Thoreau (1817–1862)
“God is a being of transcendent and unlimited perfections: his nature therefore is incomprehensible to finite spirits.”
—George Berkeley (1685–1753)