On the Nonexistence of a Strong Minimal Pair

2022/11/21 by Mingzhong Cai, Cai, Mingzhong, Yiqun Liu +6
Computer Science · Mathematics · #Computability, Logic, AI Algorithms #Advanced Topology and Set Theory #Complexity and Algorithms in Graphs

paper · pdf · doi:10.48550/arxiv.2211.11157

Abstract

Two nonzero recursively enumerable (r.e.) degrees a and b form a strong minimal pair if a \wedge b=0 and b\vee x≥ a for any nonzero r.e. degree x≤ a. We prove that there is no strong minimal pair in the r.e. degrees. Our construction goes beyond the usual 0'''-priority arguments and we give some evidence to show that it needs 0⁽⁴⁾-priority arguments.

Related

• On the existence of a strong minimal pair
• A (ω)-REA Set Forming A Minimal Pair With \0'
• Nonexistence of Minimal Pairs for Generic Computability
• An inside/outside Ramsey theorem and recursion theory
• A Direct Construction of Primitive Formally Dual Pairs Having Subsets with Unequal Sizes