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 unique eludes us; yet we remain faithful to the ideal of it; and in spite of sense and of our merely abstract thinking, it becomes for us the most real thing in the actual world, although for us it is the elusive goal of an infinite quest.”
—Josiah Royce (1855–1916)
“Remember that you were a slave in the land of Egypt, and the LORD your God brought you out from there with a mighty hand and an outstretched arm; therefore the LORD your God commanded you to keep the sabbath day.”
—Bible: Hebrew, Deuteronomy 5:15.
See Exodus 22:8 for a different version of this fourth commandment.
“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)
“Put shortly, these are the two views, then. One, that man is intrinsically good, spoilt by circumstance; and the other that he is intrinsically limited, but disciplined by order and tradition to something fairly decent. To the one party man’s nature is like a well, to the other like a bucket. The view which regards him like a well, a reservoir full of possibilities, I call the romantic; the one which regards him as a very finite and fixed creature, I call the classical.”
—Thomas Ernest Hulme (1883–1917)