Suppose you consider the collection of pairs of positive whole numbers, and each pair is colored either red or blue. Then there is an infinite set S of positive whole numbers such that any pair of items from S are the same color.
In symbols:
P = { (a,b) : a in N, b in N }
C : P -> {0,1}
There exists S an infinite subset of N and c in {0,1} such that for all a in S and b in S, C(a,b)=c.
The proof is quite simple, I use it regularly to boggle 13 and 14 year olds.
I figured out the proof on my drive in to work. It is simple.
At all points we're going to have an infinite set of integers to process, a clique of integers whose connections to each other and all of the integers left to process is red, and a clique of integers whose connections to each other and all of the integers left to process is blue. (red clique, blue clique)
We start with all of N as our set, and our cliques are empty sets.
At each point we take the first thing in our set, and remove it from the set. If there are an infinite number of things left in our set that it has a red connection to, then put it into the red clique and remove all things from the set that its connection is blue to. Else put it into the blue clique and remove all things from the set that its connection is red to. This step can always be done and leaves us with 2 cliques (one of which grew by one) and an infinite set of integers to process.
After we do this an infinite number of times at least one of the red and blue cliques must now be infinite in size. And we're done.
That's an elegant way to express it - thank you. My method has more of the "TA DA!" about it, and tends to generate a sense of "Gosh!", but I like the quiet elegance of yours.
what you talking about is exactly the black hole entropy - the maximum entropy achiveable, which is suprisingly not that _big_, i.e. it happens to be proportional to the surface area, not to the volume - the "Bekenstein-Hawking" limit :
I don't know if Ramsey's theorem really says anything as grand about disorder as Maxwell's demon and the like, but it does express something quantitative about the existence of subsets containing some specific properties as the size of the graph increases.
For me, Ramsey's theory is particularly interesting its rare that an open problem in mathematics can be explained to anyone with relatively little background in mathematics or logic for that matter. Mathematicians have discovered some bounds on R(n), but an exact solution looks like its no where in sight.
This is a sensationalist headline. Ramsey's theorem concerns patterns in a simple system, the coloring of edges in a graph. It says regardless of how the graph is colored you can always find a triangle of vertices with certain properties.
This does not mean complete disorder is impossible. It's just a combinatorial argument that says this simple game of coloring edges on a graph has some patterns to it.
But then maybe you're of the mindset that the universe is a complete graph and physics is a color by number game...in which case....oh god, we're all screwed...
10 comments
[ 2.8 ms ] story [ 42.5 ms ] threadSuppose you consider the collection of pairs of positive whole numbers, and each pair is colored either red or blue. Then there is an infinite set S of positive whole numbers such that any pair of items from S are the same color.
In symbols:
P = { (a,b) : a in N, b in N }
C : P -> {0,1}
There exists S an infinite subset of N and c in {0,1} such that for all a in S and b in S, C(a,b)=c.
The proof is quite simple, I use it regularly to boggle 13 and 14 year olds.
At all points we're going to have an infinite set of integers to process, a clique of integers whose connections to each other and all of the integers left to process is red, and a clique of integers whose connections to each other and all of the integers left to process is blue. (red clique, blue clique)
We start with all of N as our set, and our cliques are empty sets.
At each point we take the first thing in our set, and remove it from the set. If there are an infinite number of things left in our set that it has a red connection to, then put it into the red clique and remove all things from the set that its connection is blue to. Else put it into the blue clique and remove all things from the set that its connection is red to. This step can always be done and leaves us with 2 cliques (one of which grew by one) and an infinite set of integers to process.
After we do this an infinite number of times at least one of the red and blue cliques must now be infinite in size. And we're done.
Nice one.
Therefore the best king would be Pure Chance.
It is Pure Chance that rules the Universe; therefore,
and only therefore, life is good.
—Aleister Crowley, The Book of Lies
http://en.wikipedia.org/wiki/Black_hole_thermodynamics#Black...
For me, Ramsey's theory is particularly interesting its rare that an open problem in mathematics can be explained to anyone with relatively little background in mathematics or logic for that matter. Mathematicians have discovered some bounds on R(n), but an exact solution looks like its no where in sight.
This does not mean complete disorder is impossible. It's just a combinatorial argument that says this simple game of coloring edges on a graph has some patterns to it.
But then maybe you're of the mindset that the universe is a complete graph and physics is a color by number game...in which case....oh god, we're all screwed...