The strength of Ramsey Theorem for coloring relatively large sets

Details The strength of Ramsey Theorem for coloring relatively large sets The strength of Ramsey Theorem for coloring relatively large sets

2012-04-05

arxiv.org/abs/1204.1134v1

Mathematics

Logic

Scientific paper

We characterize the computational content and the proof-theoretic strength of a Ramsey-type theorem for bi-colorings of so-called {\em exactly large} sets. An {\it exactly large} set is a set $X\subset\Nat$ such that $\card(X)=\min(X)+1$. The theorem we analyze is as follows. For every infinite subset $M$ of $\Nat$, for every coloring $C$ of the exactly large subsets of $M$ in two colors, there exists and infinite subset $L$ of $M$ such that $C$ is constant on all exactly large subsets of $L$. This theorem is essentially due to Pudl\`ak and R\"odl and independently to Farmaki. We prove that --- over Computable Mathematics --- this theorem is equivalent to closure under the $\omega$ Turing jump (i.e., under arithmetical truth). Natural combinatorial theorems at this level of complexity are rare. Our results give a complete characterization of the theorem from the point of view of Computable Mathematics and of the Proof Theory of Arithmetic. This nicely extends the current knowledge about the strength of Ramsey Theorem. We also show that analogous results hold for a related principle based on the Regressive Ramsey Theorem. In addition we give a further characterization in terms of truth predicates over Peano Arithmetic. We conjecture that analogous results hold for larger ordinals.

Affiliated with

Also associated with

No associations

Rating

The strength of Ramsey Theorem for coloring relatively large sets does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The strength of Ramsey Theorem for coloring relatively large sets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The strength of Ramsey Theorem for coloring relatively large sets will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-212315