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:
“Henry B. Adams was the first in an infinite series to discover and admit to himself that he really did not care whether truth was, or was not, true. He did not even care that it should be proved true, unless the process were new and amusing. He was a Darwinian for fun.”
—Henry Brooks Adams (1838–1918)
“Exercise is the yuppie version of bulimia.”
—Barbara Ehrenreich (b. 1941)
“Mutual repect implies discretion and reserve even in love itself; it means preserving as much liberty as possible to those whose life we share. We must distrust our instinct of intervention, for the desire to make one’s own will prevail is often disguised under the mask of solicitude.”
—Henri-Frédéric Amiel (1821–1881)
“Sisters define their rivalry in terms of competition for the gold cup of parental love. It is never perceived as a cup which runneth over, rather a finite vessel from which the more one sister drinks, the less is left for the others.”
—Elizabeth Fishel (20th century)