Ramsey’s theorem under a computable perspective

Abstract:

Given a $k$-coloring of $\[\mathbb{N}\]^n$, a set $H$ is homogeneous if every $n$-tuple over $H$ has the same color. Ramsey’s theorem asserts, for every $k$-coloring of $\[\mathbb{N}\]^n$, the existence of an infinite homogeneous set.
The study of Ramsey’s theorem in computability theory was started by Jockusch in 1972 [4]. However, this is the program of reverse mathematics which made Ramsey’s theorem receive a substantial interest from the computability-theoretic community. This program, founded by Friedman and Simpson, seeks to determine the optimal axioms for ordinary mathematics. Based on a theory ($\mathsf{RCA}_0$) capturing “computable mathematics”, the early reverse mathematics yielded the observation that the vast majority of ordinary theorems could be classified in five subsystems of second-order arithmetics [9], namely, $\mathsf{RCA}_0$, $\mathsf{WKL}_0$, $\mathsf{ACA}_0$, $\mathsf{ATR}_0$ and $\Pi_1^1$-$\matsf{CA}$. Ramsey’s theorem for pairs is historically the first theorem proven to avoid this classification [8]. Since then, many combinatorial statements, coming in majority from Ramsey’s theory, have been proven to belong to their own subsystem, yielding a chaotic structure of relations between mathematical statements [3, 10, 5].
Besides its reverse mathematical interest, Ramsey’s theorem has been a fruitful source of motivated questions requiring the development of new proof techniques in computability theory [5] and proof theory [7], among others. In particular, the question whether Ramsey’s theorem for pairs is equivalent to its stable version yielded the rediscovery of the Weihrauch reduction [1] and the introduction of the computable reduction [2] and its omniscient variants [6].
In this talk, we will revisit the main results about the study of Ramsey’s theorem in the light of the most recent developments. In particular, we will try to emphasize the common combinatorial core of Ramsey-type theorems. Finally, we will mention some remaining open questions and will speculate on the future of the study of Ramsey’s theorem.

References

1. Dorais, F.G., Dzhafarov, D.D., Hirst, J.L., Mileti, J.R., Shafer, P.: On uniform relationships between combinatorial problems. Trans. Amer. Math. Soc. 368(2), 1321-1359 (2016), http://dx.doi.org/10.1090/tran/6465
2. Dzhafarov, D.D.: Strong reductions between combinatorial principles. J. Symb.Log. 81(4), 1405-1431 (2016), http://dx.doi.org/10.1017/jsl.2016.1
3. Hirschfeldt, D.R., Shore, R.A.: Combinatorial principles weaker than Ramsey’s theorem for pairs. Journal of Symbolic Logic 72(1), 171-206 (2007)
4. Jockusch, C.G.: Ramsey’s theorem and recursion theory. Journal of Symbolic Logic 37(2), 268-280 (1972)
5. Lerman, M., Solomon, R., Towsner, H.: Separating principles below Ramsey’s theorem for pairs. Journal of Mathematical Logic 13(02), 1350007 (2013)
6. Monin, B., Patey, L.: $\Pi_1^0$ encodability and omniscient reductions. Notre (2017), available at http://arxiv.org/abs/1603.01086.
7. Patey, L., Yokoyama, K.: The proof-theoretic strength of Ramseys theorem for pairs and two colors (2015), submitted. Available at http://arxiv.org/abs/1601.00050.
8. Seetapun, D., Slaman, T.A.: On the strength of Ramsey’s theorem. Notre Dame Journal of Formal Logic 36(4), 570-582 (1995)
9. Simpson, S.G.: Subsystems of Second Order Arithmetic. Cambridge University Press (2009)
10. Wang, W.: The denability strength of combinatorial principles (2014), to appear. Available at http://arxiv.org/abs/1408.1465