Subcountability

In constructive mathematics, a collection is subcountable if there exists a partial surjection from the natural numbers onto it. This may be expressed as where denotes that is a surjective function from a onto . The surjection is a member of and here the subclass of is required to be a set. In other words, all elements of a subcountable collection are functionally in the image of an indexing set of counting numbers and thus the set can be understood as being dominated by the countable set . Note that nomenclature of countability and finiteness properties vary substantially - in part because many of them coincide when assuming excluded middle. To reiterate, the discussion here concerns the property defined in terms of surjections onto the set being characterized. The language here is common in constructive set theory texts, but the name subcountable has otherwise also been given to properties in terms of injections out of the set being characterized. The set in the definition can also be abstracted away, and in terms of the more general notion may be called a subquotient of . Important cases are where the set in question is some subclass of a bigger class of functions as studied in computability theory. There cannot be a computable surjection from onto the set of total computable functions , as demonstrated via the function from the diagonal construction, which could never be in such a surjections image. However, via the codes of all possible partial computable functions, which also allows non-terminating programs, such subsets of functions, such as the total functions, are seen to be subcountable sets: The total functions are the range of some strict subset of the natural numbers. Being dominated by an uncomputable, and so constructively uncountable, set of numbers, the name subcountable thus conveys that the constructively uncountable set is no bigger than . Note that no effective map between all counting numbers and the unbounded and non-finite indexing set is asserted here, merely the subset relation .