Embeddings between well-orderings: Computability-theoretic reductions

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


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.

Download options


    Upload a copy of this work     Papers currently archived: 72,722

External links

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

Through your library


Added to PP

12 (#816,361)

6 months
1 (#387,390)

Historical graph of downloads
How can I increase my downloads?

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 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.
The Veblen Functions for Computability Theorists.Alberto Marcone & Antonio Montalbán - 2011 - Journal of Symbolic Logic 76 (2):575 - 602.
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.
A Recursion Principle for Linear Orderings.Juha Oikkonen - 1992 - Journal of Symbolic Logic 57 (1):82-96.