How does Ramsey Theory relate to Godel Incompleteness theorem?

89 Views Asked by At

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

There are 1 best solutions below

0
On BEST 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.