×

zbMATH — the first resource for mathematics

The uniform content of partial and linear orders. (English) Zbl 1390.03040
The authors use Weihrauch and computable reducibility to separate combinatorial principles related to \(\text{ADS}\) (ascending/descending sequence), \(\text{CAC}\) (chain/antichain), and their stable versions. The separated principles are provably equivalent in \(\text{RCA}_0\), so the results illustrate how reducibility results can refine the usual reverse mathematical hierarchy. For example, the new principle \(\text{ADC}\) is introduced and shown to be equivalent to \(\text{ADS}\) over \(\text{RCA}_0\). However, \(\text{ADC}\) is strictly weaker than \(\text{ADS}\) under Weihrauch reducibility, denoted \(\text{ADC} <_W \text{ADS}\). Similar results for stable versions include \(\text{SADS} <_W \text{General-SADS} <_W \text{ADS}\), \(\text{SADC} <_W \text{General-SADC} <_W \text{ADC}\), \(\text{SADC} <_W \text{SADS}\), \(\text{General-SADC} <_W \text{General-SADS}\), and \(\text{ADC} <_W \text{ADS}\). For computable reducibility, \(\text{WSCAC} <_W \text{SCAC}\). Versions of these principles appear in work of D. R. Hirschfeldt and R. A. Shore [J. Symb. Log. 72, No. 1, 171–206 (2007; Zbl 1118.03055)], D. R. Hirschfeldt and C. G. Jockusch jun. [J. Math. Log. 16, No. 1, Article ID 1650002, 59 p. (2016; Zbl 1373.03068)], C. G. Jockusch jun. et al. [J. Symb. Log. 74, No. 2, 693–711 (2009; Zbl 1171.03034)], and in Chapter 9 of D. R. Hirschfeldt’s book [Slicing the truth. On the computable and reverse mathematics of combinatorial principles. Hackensack, NJ: World Scientific (2014; Zbl 1304.03001)].

MSC:
03D80 Applications of computability and recursion theory
03B30 Foundations of classical theories (including reverse mathematics)
03D30 Other degrees and reducibilities in computability and recursion theory
05D10 Ramsey theory
03F35 Second- and higher-order arithmetic and fragments
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Astor, Eric P.; Dzhafarov, Damir D., The RM zoo, website: · Zbl 1390.03040
[2] Brattka, Vasco, Bibliography on weihrauch complexity, website: · Zbl 1140.03040
[3] Vasco Brattka, Tahina Rakotoniaina, On the uniform computational content of Ramsey’s theorem, in press. · Zbl 1422.03132
[4] Cholak, Peter A.; Jockusch, Carl G.; Slaman, Theodore A., On the strength of Ramsey’s theorem for pairs, J. Symbolic Logic, 66, 1, 1-55, (2001) · Zbl 0977.03033
[5] Cholak, Peter A.; Dzhafarov, Damir D.; Hirst, Jeffry L.; Slaman, Theodore A., Generics for computable Mathias forcing, Ann. Pure Appl. Logic, 165, 9, 1418-1428, (2014) · Zbl 1320.03072
[6] Cholak, Peter A.; Dzhafarov, Damir D.; Soskova, Mariya I., Genericity for Mathias forcing over general Turing ideals, Israel J. Math., 216, 2, 583-604, (2016) · Zbl 1377.03031
[7] Chong, C. T.; Lempp, Steffen; Yang, Yue, On the role of the collection principle for \(\operatorname{\Sigma}^0_2\)-formulas in second-order reverse mathematics, Proc. Amer. Math. Soc., 138, 3, 1093-1100, (2010) · Zbl 1195.03015
[8] Dorais, François G.; Dzhafarov, Damir D.; Hirst, Jeffry L.; Mileti, Joseph R.; Shafer, Paul, On uniform relationships between combinatorial problems, Trans. Amer. Math. Soc., 368, 2, 1321-1359, (2016) · Zbl 06560459
[9] Downey, R. G., Computability theory and linear orderings, (Handbook of Recursive Mathematics, vol. 2, Stud. Logic Found. Math., vol. 139, (1998), North-Holland Amsterdam), 823-976 · Zbl 0941.03045
[10] Dzhafarov, Damir D., Cohesive avoidance and strong reductions, Proc. Amer. Math. Soc., 143, 2, 869-876, (2015) · Zbl 1386.03055
[11] Dzhafarov, Damir D., Strong reductions between combinatorial principles, J. Symbolic Logic, (2016), in press · Zbl 1368.03044
[12] Dzhafarov, Damir D.; Patey, Ludovic; Solomon, Reed; Brown Westrick, Linda, Ramsey’s theorem for singletons and strong computable reducibility, Proc. Amer. Math. Soc., (2016), in press · Zbl 1423.03159
[13] Frittaion, Emanuele; Patey, Ludovic, Coloring the rationals in reverse mathematics, Computability, (2016), in press · Zbl 1420.03026
[14] Gura, Kirill; Hirst, Jeffry L.; Mummert, Carl, On the existence of a connected component of a graph, Computability, 4, 2, 103-117, (2015) · Zbl 1337.03086
[15] Hirschfeldt, Denis R., Slicing the truth: on the computable and reverse mathematics of combinatorial principles, Lecture Notes Series, (2014), Institute for Mathematical Sciences, National University of Singapore. World Scientific Publishing Company Incorporated · Zbl 1304.03001
[16] Hirschfeldt, Denis R.; Shore, Richard A., Combinatorial principles weaker than Ramsey’s theorem for pairs, J. Symbolic Logic, 72, 1, 171-206, (2007) · Zbl 1118.03055
[17] Hirschfeldt, Denis R.; Jockusch, Carl G., On notions of computability theoretic reduction between \(\operatorname{\Pi}_2^1\) principles, J. Math. Log., (2016), in press · Zbl 1373.03068
[18] Jockusch, Carl G., Ramsey’s theorem and recursion theory, J. Symbolic Logic, 37, 268-280, (1972) · Zbl 0262.02042
[19] Jockusch, Carl G.; Kastermans, Bart; Lempp, Steffen; Lerman, Manuel; Solomon, Reed, Stability and posets, J. Symbolic Logic, 74, 2, 693-711, (2009) · Zbl 1171.03034
[20] Lerman, Manuel; Solomon, Reed; Towsner, Henry, Separating principles below Ramsey’s theorem for pairs, J. Math. Log., 13, 2, (2013), 44 · Zbl 1326.03021
[21] Patey, Ludovic, The weakness of being cohesive, thin or free in reverse mathematics, Israel J. Math., (2016), in press · Zbl 1368.03018
[22] Richard A. Shore, Lecture notes on Turing degrees, in: Computational Prospects of Infinity II: AII Graduate Summer School, in: Lect. Notes Ser. Inst. Math. Sci. Natl. Univ. Singap., World Sci. Publ., Hackensack, NJ, in press.
[23] Simpson, Stephen G., Subsystems of second order arithmetic, Perspectives in Logic, (2009), Cambridge University Press Cambridge · Zbl 1181.03001
[24] Soare, Robert I., Computability theory and applications, Theory and Applications of Computability, (2017), Springer New York · Zbl 1350.03001
[25] Weihrauch, K., The degrees of discontinuity of some translators between representations of the real numbers, (1992), International Computer Science Institute Berkeley, Technical report TR-92-050
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.