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:
“[The human mind] finds more facility in assenting to the self-existence of an invisible cause possessing infinite power, wisdom, and goodness, than in the self-existence of the universe, visibly destitute of these attributes, and which may be the effect of them.”
—James Madison (1751–1836)
“It is never the thing but the version of the thing:
The fragrance of the woman not her self,
Her self in her manner not the solid block,
The day in its color not perpending time,
Time in its weather, our most sovereign lord,
The weather in words and words in sounds of sound.”
—Wallace Stevens (1879–1955)
“We have two kinds of “conference.” One is that to which the office boy refers when he tells the applicant for a job that Mr. Blevitch is “in conference.” This means that Mr. Blevitch is in good health and reading the paper, but otherwise unoccupied. The other type of “conference” is bona fide in so far as it implies that three or four men are talking together in one room, and don’t want to be disturbed.”
—Robert Benchley (1889–1945)
“Are not all finite beings better pleased with motions relative than absolute?”
—Henry David Thoreau (1817–1862)