Use-Bounded Strong Reducibilities

computability;degree structure;Pure Mathematics

Belanger, David

University of Waterloo

关键词: computability;    degree structure;    Pure Mathematics;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/4564/1/Belanger_David.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

We study the degree structures of the strong reducibilities $(leq_{ibT})$ and $(leq_{cl})$, as well as $(leq_{rK})$ and $(leq_{wtt})$.We show that any noncomputable c.e. set is part of a uniformly c.e. copy of $(BQ,leq)$ in the c.e. cl-degrees within a single wtt-degree; that there exist uncountable chains in each of the degree structures in question; and that any countable partially-ordered set can be embedded into the cl-degrees, and any finite partially-ordered set can be embedded into the ibT-degrees.We also offer new proofs of results of Barmpalias and Lewis-Barmpalias concerning the non-existence of cl-maximal sets.