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:
“Let us then examine this point, and say, “God is, or he is not.” But to which side shall we incline? Reason can decide nothing here. There is an infinite chaos which separates us. A game is being played at the extremity of this infinite distance where heads or tails will turn up. What will you wager?”
—Blaise Pascal (1623–1662)
“Exercise is the yuppie version of bulimia.”
—Barbara Ehrenreich (b. 1941)
“On a huge hill,
Cragged, and steep, Truth stands, and he that will
Reach her, about must, and about must go;
And what the hill’s suddenness resists, win so;
Yet strive so, that before age, death’s twilight,
Thy Soul rest, for none can work in that night.
To will, implies delay, therefore now do:
Hard deeds, the body’s pains; hard knowledge too
The mind’s endeavours reach, and mysteries
Are like the Sun, dazzling, yet plain to all eyes.”
—John Donne (1572–1631)
“We know then the existence and nature of the finite, because we also are finite and have extension. We know the existence of the infinite and are ignorant of its nature, because it has extension like us, but not limits like us. But we know neither the existence nor the nature of God, because he has neither extension nor limits.”
—Blaise Pascal (1623–1662)