Finite vs infinite Ramsey theorem - what's the difference?

312 Views Asked by At

The finite Ramsey theorem states that given a $k$ and an $r$, there exists an $N$ such that every $r$ coloring of the edges of $K_N$ contains a monochromatic clique of size $k$.

The infinite version says that every coloring $c:\binom{\mathbb{N}}{2}\mapsto [r]$ of the set of all pairs of integers contains an infinite monochromatic set $\{x_1,x_2\cdots\}$ such that every pair $\{x_i,x_j\}$ is of the same color.

My question is, why is the infinite version any different from the finite version? We were told that they are actually different and were given separate proofs which I understood. But doesn't the finite version simply imply the infinite version, because we can find arbitrarily large monochromatic cliques for sufficiently large $N$'s? Why is arbitrarily large not the same as infinite?

So if we are given a coloring of the set of pairs of all integers, then given any $k$, we can always find a monochromatic set of size $k+1$. Isn't that sufficient to prove the existence of an infinite clique (in a way similar to Euclid's proof of infinitude of primes )

1

There are 1 best solutions below

4
On BEST ANSWER

Why is arbitrarily large not the same as infinite?

Well, there are arbitrarily large finite natural numbers but there are no infinite natural numbers.

More seriously, consider (for example) the graph $G$ consisting of the disjoint union of a copy of $K_n$ for each $n\in\mathbb{N}$, where $K_n$ is the complete graph on $n$ vertices. Arbitrarily large finite cliques occur in $G$, but there is no infinite clique in $G$.

The issue is that a priori we might not be able to "piece together" the increasingly large finite configuration of some type into a single infinite configuration of that type. Infinite Ramsey's theorem says that in one particular case we can find increasingly large finite configurations which do cohere appropriately.


Incidentally, we can make the idea that finite Ramsey's theorem doesn't trivially imply infinite Ramsey's theorem precise in a technical way: the theory $\mathsf{RCA_0+I\Sigma_2}$ proves finite Ramsey's theorem but not infinite Ramsey's theorem.

Another tool we can use here is computability theory. On the one hand, via brute-force search we can always computably locate a homogeneous set of size $k$ in a given computable $r$-coloring of pairs of natural numbers. On the other hand, we can whip up a computable two-coloring of pairs of natural numbers with no computable infinite homogeneous set. Basically, there will be lots of "dead ends" - finite cliques which can't be extended to larger cliques - and there's no computable way to detect these.