Difference Splittings of Recursively Enumerable Sets
Asat Arslanov · 2020
We study here the degree-theoretic structure of set-theoretical splittings of recursively enumerable (r.e.) sets into di#erences of r.e. sets. As a corollary we deduce that the ordering of wtt--degrees of unsolvability of di#erences of r.e. sets is not a distributive semilattice and is not elementarily equivalent to the ordering of r.e. wtt--degrees of unsolvability. Keywords: Recursively enumerable sets, degrees of unsolvability, weak truth table reducibility. 1 Introduction and Notation We review here the main notation and notions which will be used in this paper. All other notation and notions can be found in [27] and [26]. Recursively enumerable (r.e.) sets are the sets for which there exist Turing machines that e#ectively enumerate them. The set of all natural numbers is denoted by #. A set A # # is called d--r.e. (di#erence of r.e. sets) if there are r.e. sets of natural numbers A 1 ,A 2 ## such that A = A 1 -A 2 . Let be {W e } e## and {# e } e## be, respect...