# How does Ramsey Theory relate to Godel Incompleteness theorem?

My knowledge in math is not too advanced but I am super interested in this topic and although I think I know part of the answer, I do not know for sure how these two theories are related.

Also, if there is some proof done in Peano Arithmetic, that would be helpful to see . Thanks

## 1 Answer

There is a two-step connection between Ramsey theory and unprovability:

• Theorems in Ramsey theory often correspond to the totality of particular fast-growing computable functions - namely, functions of the form $$F(k)=$$ the least $$n$$ such that every "A-configuration" of size $$n$$ has a "B-configuration" of size $$k$$ for some notions of "A-configuration" and "B-configuration."

• In general, we can show that a sentence is unprovable in a theory $$T$$ by analyzing the provably total functions of $$T$$ and then showing that that sentence implies the totality of a computable function not in that class.

For example, the provably total functions of $$I\Sigma_1$$ are exactly the primitive recursive functions, so any sentence implying for example that the Ackermann function is always defined is automatically unprovable in $$I\Sigma_1$$. The provably total functions of $$\mathsf{PA}$$ are much harder to describe, but we can still get similar results. The particular role Ramsey theory plays is simply as a vehicle for producing fast-growing functions.