A well studied case is where the image denotes a subclass of functions in computability theory, such as the total functions. Note that being total is not a decidable property and there cannot be a constructive bijection between the total functions and the natural numbers. However, via enumeration of the codes of all possible partial functions, subsets of those, such as the total functions, are seen to be a subcountable sets. Note that by Rice's theorem on index sets, most domains are not recursive. Indeed, no effective map between all counting numbers and the infinite indexing set is asserted here, merely the subset relation. Being dominated by a constructively non-countable set of numbers, the name subcountable thus conveys that the uncountable set is no bigger than.
Subcountable implies not -productive
Any countable set is subcountable and any subcountable set is not -productive: A set is said to be -productive if, whenever any of its subsets is the range of some partial function, there always remains at least one element that lies outside that range. This may be expressed as A set being -productive speaks for how hard it is to generate its elements: They cannot be generated using a single function. As such, -productive sets escape subcountability. Diagonal constructions often involve this notion, be it explicitly or implicitly.
Set theories
Subcountability shall not be confused with the standard mathematical definition of cardinality relations as defined by Cantor, with smaller cardinality being defined in terms of injections out of and equality of cardinalities being defined in terms of bijections. Moreover, note that constructively, an ordering "" like that of cardinalities can be undecidable. As seen in the example of the function space considered in computability theory, not every infinite subset of necessarily is in constructive bijection with, thus making room for a more refined distinction between uncountabile sets in constructive contexts. The function space in a modestly richset theory is always found to be neither finite nor in bijection with, by Cantor's diagonal argument. This is what it means to be uncountable. But a demonstration that the cardinality of that set would thus exceed that of the natural numbers relies on the law of excluded middle, as it concludes an ordering just from the rejection of some alternatives. Consequently, it can be consistent to assert the subcountability of some uncountable collections. Such axioms can be seen as choice principles which, however, don't tend to increase the proof-theoretical strengths of the theories much. Models for such theories have been obtained. Some examples are:
Cantor's diagonal argument establishes that the real numbers are uncountable, but in some constructive theories they can be asserted to be subcountable.
In the constructive set theoryCZF, it is indeed consistent to assert the Subcountability Axiom that all sets are subcountable. The resulting theory is in contradiction to the Axiom of power set and thus in contradiction with the law of excluded middle.
