×

zbMATH — the first resource for mathematics

Embeddings between well-orderings: computability-theoretic reductions. (English) Zbl 07189161
Summary: We study the computational content of various theorems with reverse mathematical strength around Arithmetical Transfinite Recursion \((\mathsf{ATR}_0)\) from the point of view of computability-theoretic reducibilities, in particular Weihrauch reducibility. Our main result states that it is equally hard to construct an embedding between two given well-orderings, as it is to construct a Turing jump hierarchy on a given well-ordering. This answers a question of Marcone. We obtain a similar result for Fraïssé’s conjecture restricted to well-orderings.
MSC:
03B30 Foundations of classical theories (including reverse mathematics)
03D30 Other degrees and reducibilities in computability and recursion theory
03D80 Applications of computability and recursion theory
03F35 Second- and higher-order arithmetic and fragments
03D55 Hierarchies of computability and definability
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Astor, Eric P.; Dzhafarov, Damir D.; Solomon, Reed; Suggs, Jacob, The uniform content of partial and linear orders, Ann. Pure Appl. Log., 168, 6, 1153-1171 (2017) · Zbl 1390.03040
[2] Brattka, Vasco; Gherardi, Guido; Marcone, Alberto, The Bolzano-Weierstrass theorem is the jump of weak König’s lemma, Ann. Pure Appl. Log., 163, 6, 623-655 (2012) · Zbl 1245.03097
[3] Vasco Brattka, Gherardi Guido, Arno Pauly, Weihrauch complexity in computable analysis, Unpublished manuscript. · Zbl 06700060
[4] Brattka, Vasco; Pauly, Arno, On the algebraic structure of Weihrauch degrees, Log. Methods Comput. Sci., 14, 4, Article 4 pp. (2018) · Zbl 06970801
[5] Chen, Keh Hsun, Recursive well-founded orderings, Ann. Math. Log., 13, 2, 117-147 (1978) · Zbl 0384.03027
[6] Dorais, François G.; Dzhafarov, Damir D.; Hirst, Jeffry L.; Mileti, Joseph R.; Shafer, Paul, On uniform relationships between combinatorial problems, Trans. Am. Math. Soc., 368, 2, 1321-1359 (2016) · Zbl 06560459
[7] Dzhafarov, Damir D., Cohesive avoidance and strong reductions, Proc. Am. Math. Soc., 143, 2, 869-876 (2015) · Zbl 1386.03055
[8] Friedman, Harvey M.; Hirst, Jeffry L., Weak comparability of well orderings and reverse mathematics, Ann. Pure Appl. Log., 47, 1, 11-29 (1990) · Zbl 0706.03044
[9] Le Goh, Jun, Measuring the relative complexity of mathematical constructions and theorems (2019), Cornell University, PhD thesis
[10] Greenberg, Noam; Montalbán, Antonio, Ranked structures and arithmetic transfinite recursion, Trans. Am. Math. Soc., 360, 3, 1265-1307 (2008) · Zbl 1135.03026
[11] Jockusch, C. G.; McLaughlin, T. G., Countable retracing functions and \(\operatorname{\Pi}_2^0\) predicates, Pac. J. Math., 30, 67-93 (1969) · Zbl 0181.30602
[12] Takayuki Kihara, Alberto Marcone, Arno Pauly, Searching for an analogue of ATR in the Weihrauch lattice, Unpublished manuscript.
[13] Laver, Richard, On Fraïssé’s order type conjecture, Ann. Math. (2), 93, 89-111 (1971) · Zbl 0208.28905
[14] Montalbán, Antonio, Fraïssé’s conjecture in \(\operatorname{\Pi}_1^1\)-comprehension, J. Math. Log., 17, 2, Article 1750006 pp. (2017) · Zbl 06815212
[15] Pauly, Arno, Computability on the countable ordinals and the Hausdorff-Kuratowski theorem (2015), CoRR · Zbl 06482752
[16] Sacks, Gerald E., Higher Recursion Theory, Perspectives in Mathematical Logic (1990), Springer-Verlag: Springer-Verlag Berlin · Zbl 0716.03043
[17] Shore, Richard A., On the strength of Fraïssé’s conjecture, (Logical Methods. Logical Methods, Ithaca, NY, 1992. Logical Methods. Logical Methods, Ithaca, NY, 1992, Progr. Comput. Sci. Appl. Logic, vol. 12 (1993), Birkhäuser Boston: Birkhäuser Boston Boston, MA), 782-813 · Zbl 0820.03037
[18] Simpson, Stephen G., Subsystems of Second Order Arithmetic, Perspectives in Logic (2009), Cambridge University Press, Association for Symbolic Logic: Cambridge University Press, Association for Symbolic Logic Cambridge, Poughkeepsie, NY · Zbl 1181.03001
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.