Nonlowness is independent from fickleness

Article type: Research Article

Authors: Ko, Liling^{; *}

Affiliations: Department of Mathematics, University of Notre Dame, IN, United States of America. lko@nd.edu

Correspondence: [*] Corresponding author. lko@nd.edu.

Abstract: It was recently shown that the computably enumerable (c.e.) degrees that embed the critical triple and the M5 lattice structure are exactly those that are sufficiently fickle. Therefore the embeddability strength of a c.e. degree has much to do with the degree’s fickleness. Nonlowness is another common measure of degree strength, with nonlow degrees expected to compute more degrees than low ones. We ask if nonlowness and fickleness are independent measures of strength. Downey and Greenberg (A Hierarchy of Turing Degrees: A Transfinite Hierarchy of Lowness Notions in the Computably Enumerable Degrees, Unifying Classes, and Natural Definability (AMS-206) (2020) Princeton University Press) claimed this to be true without proof, so we present one here. We prove the claim by building low and nonlow c.e. sets with arbitrary fickle degrees. Our construction is uniform so the degrees built turn out to be uniformly fickle. We base our proof on our direct construction of a nonlow array computable set. Such sets were always known to exist, but also never constructed directly in any publication we know.

Keywords: Computably enumerable sets and degrees, α-computably approximable, array computable, nonlow, fickle

DOI: 10.3233/COM-190269

Journal: Computability, vol. 10, no. 4, pp. 271-288, 2021