Difference sets and computability theory Export

@article{citeulike:565330, abstract = {For a set A of non-negative integers, let D(A) (the difference set of A) be the set of non-negative differences of elements of A. Clearly, if A is computable, then D(A) is computably enumerable. We show (as partial converses) that every simple set which contains 0 is the difference set of some computable set and that every computably enumerable set is computably isomorphic to the difference set of some computable set. Also, we prove that there is a computable set which is the difference set of the complement of some computably enumerable set but not of any computably enumerable set. Finally, we show that every arithmetic set is in the Boolean algebra generated from the computable sets by the difference operator D and the Boolean operations.}, author = {Downey, Rod and Furedi, Zoltan and Jockusch, Jr and Rubel, Lee A.}, booktitle = {Computability Theory}, citeulike-article-id = {565330}, citeulike-linkout-0 = {http://dx.doi.org/10.1016/S0168-0072(97)00053-5}, citeulike-linkout-1 = {http://www.sciencedirect.com/science/article/B6TYB-3TT00C3-3/2/5a1c112c098ad633e242ab1f6944927c}, day = {28}, doi = {10.1016/S0168-0072(97)00053-5}, journal = {Annals of Pure and Applied Logic}, keywords = {computably\_enumerable, difference\_set}, month = {April}, number = {1-3}, pages = {63--72}, posted-at = {2006-03-27 11:38:18}, priority = {0}, title = {Difference sets and computability theory}, url = {http://dx.doi.org/10.1016/S0168-0072(97)00053-5}, volume = {93}, year = {1998} }

TY - JOUR ID - citeulike:565330 L3 - citeulike-article-id:565330 N2 - For a set A of non-negative integers, let D(A) (the difference set of A) be the set of non-negative differences of elements of A. Clearly, if A is computable, then D(A) is computably enumerable. We show (as partial converses) that every simple set which contains 0 is the difference set of some computable set and that every computably enumerable set is computably isomorphic to the difference set of some computable set. Also, we prove that there is a computable set which is the difference set of the complement of some computably enumerable set but not of any computably enumerable set. Finally, we show that every arithmetic set is in the Boolean algebra generated from the computable sets by the difference operator D and the Boolean operations. IS - 1-3 JF - Annals of Pure and Applied Logic EP - 72 TI - Difference sets and computability theory VL - 93 T2 - Computability Theory SP - 63 KW - computably_enumerable KW - difference_set AU - Downey, Rod AU - Furedi, Zoltan AU - Jockusch, Jr AU - Rubel, Lee PY - 1998/04/28/ UR - http://dx.doi.org/10.1016/S0168-0072(97)00053-5 ER -