The uniform Martin's conjecture for many-one degrees

2016/08/17 by Takayuki Kihara, Kihara, Takayuki, Antonio Montalbán +1 · 1 citation
Mathematics · #FOS: Mathematics #Logic (math.LO) #math.LO

paper · pdf · doi:10.48550/arxiv.1608.05065

arxiv created 2016/08/17 · arxiv updated 2016/08/18

Abstract

We study functions from reals to reals which are uniformly degree-invariant from Turing-equivalence to many-one equivalence, and compare them "on a cone." We prove that they are in one-to-one correspondence with the Wadge degrees, which can be viewed as a refinement of the uniform Martin's conjecture for uniformly invariant functions from Turing- to Turing-equivalence. Our proof works in the general case of many-one degrees on Q^ω and Wadge degrees of functions ω^ω\toQ for any better quasi ordering Q.

Cited by

• Martin's Conjecture in the Enumeration Degrees

Related

• Martin's Conjecture in the Enumeration Degrees
• Uniform Martin's conjecture, locally
• Part 1 of Martin's Conjecture for order-preserving and measure-preserving functions
• On a question of Slaman and Steel
• Harrington's Solution to McLaughlin's Conjecture and Non-uniform Self-moduli