Denseness
editIn computability theory, denseness or density is c classification of sets of natural numbers in terms of their resprective rates of growth.
Definition
editFor 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
for a recursive function f.
Properties
edit- 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.
See also
editReferences
edit- 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.
Further reading
editExternal links
edit