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.
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/j.apal.2020.102789
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 50,241
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

No references found.

Add more references

Citations of this work BETA

No citations found.

Add more citations

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 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.


Added to PP index

Total views
7 ( #960,680 of 2,325,146 )

Recent downloads (6 months)
7 ( #108,957 of 2,325,146 )

How can I increase my downloads?


My notes