𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Difference sets and computability theory

✍ Scribed by Rod Downey; Zoltán Füredi; Carl G. Jockusch Jr.; Lee A. Rubel

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
727 KB
Volume
93
Category
Article
ISSN
0168-0072

No coin nor oath required. For personal study only.

✦ Synopsis

For a set A of non-negative integers, let D(A) (the difference set of A) be the set of nonnegative 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.

📜 SIMILAR VOLUMES

Difference Sets and Recursion Theory
Difference Sets and Recursion Theory
✍ James H. Schmerl 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 411 KB

recursively enumerable set but which is not the difference set of any recursive set.

Planar Functions, Relative Difference Se
Planar Functions, Relative Difference Sets, and Character Theory
✍ S.L. Ma 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 192 KB

Planar functions from ‫ޚ‬ to ‫ޚ‬ are studied in this paper. By investigating the n n character values of the corresponding relative difference sets, we obtain some nonexistence results of planar functions. In particular, we show that there is no planar functions from Z to ‫ޚ‬ , where p and q are any