On the strength of some first-order problems corresponding to Ramseyan principles
Given a represented space X, we say that a problem f with dom(f)⊆ X is first-order if its codomain is ℕ. In this talk, we will study, from the point of view of Weihrauch reducibility, some first-order problems corresponding to Ramseyan combinatorial principles.
We will start by analyzing some problems that can be seen naturally as first-order: more specifically, after mentioning some well-established results due to Brattka and Rakotoniaina [1], we will proceed to study some principles whose strengths, form a reverse mathematical perspective, lie around IΣ20, as proved mainly in [2].
We will then move to study the first-order part 1f of problems f which cannot be presented as first-order ones: intuitively speaking, 1f corresponds the strongest first-order problem Weihrauch reducible to f. The first-order part operator was introduced by Dzhafarov, Solomon and Yokoyama in unpublished work, and it has already proved to be a valuable tool to gauge the strengths of various problems according to Weihrauch reducibility. After giving some technical results on this operator, we will focus on 1(RT22), presenting various results on the position of its degree in the Weihrauch lattice.
The results presented are joint work with Arno Pauly, Pierre Pradic, and Manlio Valenti.
References
- [1]
- Vasco Brattka and Tahina Rakotoniaina, On the uniform computational content of Ramsey’s theorem, The Journal of Symbolic Logic, vol. 82 (2015), no. 4, pp. 1278–1316
- [2]
- Leszek A. Kolodziejczyk, Henryk Michalewski, Pierre Pradic, and Michał Skrzypczak, The logical strength of Büchi’s decidability theorem, 25th EACSL Annual Conference on Computer Science Logic (CSL 2016) (Marseille, France), (Jean-Marc Talbot and Laurent Regnier), vol. 62, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2016, pp. 36:1–36:16.
This document was translated from LATEX by HEVEA.