User:Deltahedron/sandbox

Denseness

In computability theory, denseness or density is c classification of sets of natural numbers in terms of their resprective rates of growth.

Definition

For subset A of the natural numbers, let A(x) denote the number of elements of A which are less than or equal to the natural number x. We define a density order on subsets of the natural numbers by

$A\preceq B\ \Leftrightarrow \ B(x)\leq f(A(x))\$

for a recursive function f.

Properties

• An infinite set is of lower density than the whole set of natural numbers if anf only if it is a hyperimmune set.
• The density order defines a distributive lattice on equivalence classes of subsets.

References

• Medvedev, Ju.T. (1955). "On nonisomorphic recursively enumerable sets". Dokl. Akad. Nauk SSSR (in Russian). 102: 211–214. Zbl 0064.28802.
• Pavlova, E.A. (1961). "Densities of hyperimmune sets". Dokl. Akad. Nauk SSSR (in Russian). 139: 814–817. Zbl 0119.01302.