2014/11/06 by Ludovic Patey, Patey, Ludovic
Computer Science · Mathematics · #03B30 #03F35 #Benford’s Law and Fraud Detection #Computability, Logic, AI Algorithms #FOS: Mathematics #Logic (math.LO) #Mathematical and Theoretical Analysis
paper · pdf · doi:10.48550/arxiv.1411.1599
openalex publication_date 2014/11/06 · openalex created_date 2022/10/03 · openalex updated_date 2026/07/28
A Turing degree d bounds a principle P of reverse mathematics if every\ncomputable instance of P has a d-computable solution. P admits a universal\ninstance if there exists a computable instance such that every solution bounds\nP. We prove that the stable version of the ascending descending sequence\nprinciple (SADS) as well as the stable version of the thin set theorem for\npairs (STS(2)) do not admit a bound of low2 degree. Therefore no principle\nbetween Ramsey's theorem for pairs RT22 and SADS or STS(2) admit a universal\ninstance. We construct a low2 degree bounding the Erd Hos-Moser theorem\n(EM), thereby showing that previous argument does not hold for EM. Finally, we\nprove that the only Delta02 degree bounding a stable version of the rainbow\nRamsey theorem for pairs (SRRT22) is 0'. Hence no principle between the stable\nRamsey theorem for pairs SRT22 and SRRT22 admit a universal instance. In\nparticular the stable version of the Erd Hos-Moser theorem does not admit\none. It remains unknown whether EM admits a universal instance.\n