View source for Direct counting

The counting of the elements of a set of natural numbers in order of increasing magnitude. More precisely, a direct counting of a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d032/d032710/d0327101.png" /> of natural numbers is a strictly-increasing function from the natural numbers onto <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d032/d032710/d0327102.png" />. In the theory of algorithms the important characteristics of a direct counting of a set are recursiveness and rate of growth. E.g., the general recursiveness (primitive recursiveness) of the direct counting of an infinite set is equivalent to the solvability (primitive recursive solvability) of this set. Sets of natural numbers whose direct countings are not majorized by any general recursive function are called hyper-immune sets; they play an important role in the theory of [[Truth-table reducibility|truth-table reducibility]].

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  V.A. Uspenskii,   "Leçons sur les fonctions calculables" , Hermann  (1966)  (Translated from Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  H. Rogers jr.,   "Theory of recursive functions and effective computability" , McGraw-Hill  (1967)  pp. 164–165</TD></TR></table>