Embeddings between well-orderings: Computability-theoretic reductions

Annals of Pure and Applied Logic 171 (6):102789 (2020)
  Copy   BIBTEX

Abstract

We study the computational content of various theorems with reverse mathematical strength around Arithmetical Transfinite Recursion (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.

Categories

Keywords

Reprint years

DOI

10.1016/j.apal.2020.102789

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,386

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Lattice representations for computability theory.Peter A. Fejer - 1998 - Annals of Pure and Applied Logic 94 (1-3):53-74.
On self-embeddings of computable linear orderings.Rodney G. Downey, Carl Jockusch & Joseph S. Miller - 2006 - Annals of Pure and Applied Logic 138 (1):52-76.
On colimits and elementary embeddings.Joan Bagaria & Andrew Brooke-Taylor - 2013 - Journal of Symbolic Logic 78 (2):562-578.
The metamathematics of scattered linear orderings.P. Clote - 1989 - Archive for Mathematical Logic 29 (1):9-20.
Computability and Randomness.André Nies - 2008 - Oxford, England: Oxford University Press UK.
Degree spectra and computable dimensions in algebraic structures.Denis R. Hirschfeldt, Bakhadyr Khoussainov, Richard A. Shore & Arkadii M. Slinko - 2002 - Annals of Pure and Applied Logic 115 (1-3):71-113.
The veblen functions for computability theorists.Alberto Marcone & Antonio Montalbán - 2011 - Journal of Symbolic Logic 76 (2):575 - 602.
On Computable Self-Embeddings of Computable Linear Orderings.Rodney G. Downey, Bart Kastermans & Steffen Lempp - 2009 - Journal of Symbolic Logic 74 (4):1352 - 1366.
On the significance of the Burali-Forti paradox.G. Hellman - 2011 - Analysis 71 (4):631-637.
Embeddings into the recursively enumerable degreesi.Nsf Grant Dms92 - 1996 - In S. B. Cooper, T. A. Slaman & S. S. Wainer (eds.), Computability, Enumerability, Unsolvability: Directions in Recursion Theory. Cambridge University Press. pp. 185.
LD-Algebras Beyond I0.Vincenzo Dimonte - 2019 - Notre Dame Journal of Formal Logic 60 (3):395-405.
Review of Denis R. Hirschfeldt, Slicing the Truth: On the Computability Theoretic and Reverse Mathematical Analysis of Combinatorial Principles. [REVIEW]Benedict Eastaugh - 2017 - Studia Logica 105 (4):873-879.
A recursion principle for linear orderings.Juha Oikkonen - 1992 - Journal of Symbolic Logic 57 (1):82-96.
The order types of termination orderings on monadic terms, strings and multisets.Ursula Martin & Elizabeth Scott - 1997 - Journal of Symbolic Logic 62 (2):624-635.
Computability, enumerability, unsolvability, Directions in recursion theory, edited by S. B. Cooper, T. A. Slaman, and S. S. Wainer, London Mathematical Society lecture note series, no. 224, Cambridge University Press, Cambridge, New York, and Oakleigh, Victoria, 1996, vii + 347 pp. - Leo Harrington and Robert I. Soare, Dynamic properties of computably enumerable sets, Pp. 105–121. - Eberhard Herrmann, On the ∀∃-theory of the factor lattice by the major subset relation, Pp. 139–166. - Manuel Lerman, Embeddings into the recursively enumerable degrees, Pp. 185–204. - Xiaoding Yi, Extension of embeddings on the recursively enumerable degrees modulo the cappable degrees, Pp. 313–331. - André Nies, Relativization of structures arising from computability theory. Pp. 219–232. - Klaus Ambos-Spies, Resource-bounded genericity. Pp. 1–59. - Rod Downey, Carl G. Jockusch, and Michael Stob. Array nonrecursive degrees and genericity, Pp. 93–104. - Masahiro Kumabe, Degrees of generic sets, Pp. 167–183. [REVIEW]C. T. Chong - 1999 - Journal of Symbolic Logic 64 (3):1362-1365.

Analytics

Added to PP
2020-03-20

Downloads
24 (#639,942)

6 months
12 (#200,125)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Add more citations

References found in this work

Subsystems of Second Order Arithmetic.Stephen G. Simpson - 1999 - Studia Logica 77 (1):129-129.
Fraïssé’s conjecture in [math]-comprehension.Antonio Montalbán - 2017 - Journal of Mathematical Logic 17 (2):1750006.

View all 7 references / Add more references