1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.