What's the difference
For a set \(A\) of natural numbers its difference set \(D(A)\) is defined by \(D(A)=\{{x-y}:y\leq x\) and \(x,y\in A\}\). The author proves that the set of all difference sets is a \(\Sigma^1_1\)-complete set of reals. This gives a solution to a goal stated by \textit{Z. Füredi, C. G. Jockusch jun.} and \textit{L. A. Rubel} [Combinatorica 16, 87-106 (1996; Zbl 0865.05021)] ``to characterize the family of all difference sets or else show that the set of difference sets is not Borel. In fact, the author proves a stronger theorem concerning recursion theory, which also implies that for each cardinal \(m\leq\omega\) there is a recursive infinite set \(C\subseteq\omega\) which is the difference set of exactly \(m\) different sets of natural numbers.
- Difference sets and computability theory
- scientific article; zbMATH DE number 4087649 (Why is no real title available?)
- Difference Sets and Recursion Theory
- What difference \textit{might} and \textit{may} make
- Collection of infinite difference sets and its application
- Normal numbers and completeness results for difference sets
This page was built for publication: What's the difference
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1295379)
