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 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.
Discussion
Nomenclature
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 .
Example
Important cases are those where the set in question is some subclass of a bigger class of functions as studied in computability theory. For context, recall that being total is famously not a decidable property of functions. Indeed, Rice's theorem on index sets, most domains of indices are, in fact, not computable sets.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 set of natural numbers, the name subcountable thus conveys that the set is no bigger than. At the same time, for some particular restrictive constructive semantics of function spaces, in cases when is provenly not computably enumerable, such is then also not countable, and the same holds for.
Note that no effective map between all counting numbers and the unbounded and non-finite indexing set is asserted in the definition of subcountability - merely the subset relation. A demonstration that is subcountable at the same time implies that it is classically formally countable, but this does not reflect any effective countability. In other words, the fact that an algorithm listing all total functions in sequence cannot be coded up is not captured by classical axioms regarding set and function existence. We see that, depending on the axioms of a theory, subcountability may be more likely to be provable than countability.
Relation to excluded middle
In constructive logics and set theories tie the existence of a function between infinite sets to questions of decidability and possibly of effectivity. There, the subcountability property splits from countability and is thus not a redundant notion.The indexing set of natural numbers may be posited to exist, e.g. as a subset via set theoretical axioms like the separation axiom schema. Then by definition of,
But this set may then still fail to be detachable, in the sense that
may not be provable without assuming it as an axiom.
One may fail to effectively count the subcountable set if one fails to map the counting numbers into the indexing set, for this reason.
Being countable implies being subcountable. In the appropriate context with Markov's principle, the converse is equivalent to the law of excluded middle, i.e. that for all proposition holds. In particular, constructively this converse direction does not generally hold.
In classical mathematics
Asserting all laws of classical logic, the disjunctive property of discussed above indeed does hold for all sets. Then, for nonempty, the properties numerable, countable, subcountable and also not -productive are all equivalent and express that a set is finite or countably infinite.Non-classical assertions
Without the law of excluded middle, it can be consistent to assert the subcountability of sets that classically exceed the cardinality of the natural numbers.Note that in a constructive setting, a countability claim about the function space out of the full set, as in, may be disproven. But subcountability of an uncountable set by a set that is not effectively detachable from may be permitted.
A constructive proof is also classically valid. If a set is proven uncountable constructively, then in a classical context is it provably not subcountable. As this applies to, the classical framework with its large function space is incompatible with the constructive Church's thesis, an axiom of Russian constructivism.
Subcountable and ω-productive are mutually exclusive
A set shall be called -productive if, whenever any of its subsets is the range of some partial function on, there always exists an element that remains in the complement of that range.If there exists any surjection onto some, then its corresponding compliment as described would equal the empty set, and so a subcountable set is never -productive.
As defined above, the property of being -productive associates the range of any partial function to a particular value not in the functions range,. In this way, a set being -productive speaks for how hard it is to generate all the elements of it: They cannot be generated from the naturals using a single function. The -productivity property constitutes an obstruction to subcountability. As this also implies uncountability, diagonal arguments often involve this notion, explicitly since the late seventies.
One may establish the impossibility of computable enumerability of by considering only the computably enumerable subsets and one may require the set of all obstructing 's to be the image of a total recursive so called production function.
denotes the space that exactly hold all the partial functions on that have, as their range, only subsets of.
In set theory, functions are modeled as collection of pairs. Whenever is a set, the set of sets of pairs may be used to characterize the space of partial functions on. The for an -productive set one finds
Read constructively, this associates any partial function with an element not in that functions range.
This property emphasizes the incompatibility of an -productive set with any surjective function. Below this is applied in the study of subcountability assumptions.
Set theories
Cantorian arguments on subsets of the naturals
As reference theory we look at the constructive set theory CZF, which has Replacement, Bounded Separation, strong Infinity, is agnostic towards the existence of power sets, but includes the axiom that asserts that any function space is set, given are also sets. In this theory, it is moreover consistent to assert that every set is subcountable.The compatibility of various further axioms is discussed in this section by means of possible surjections on an infinite set of counting numbers. Here shall denote a model of the standard natural numbers.
Recall that for functions, by definition of total functionality, there exists a unique return value for all values in the domain,
and for a subcountable set, the surjection is still total on a subset of. Constructively, fewer such existential claims will be provable than classically.
The situations discussed below—onto power classes versus onto function spaces—are different from one another: Opposed to general subclass defining predicates and their truth values, a function does makes accessible information about data for all its subdomains. When as characteristic functions for their subsets, functions, through their return values, decide subset membership. As membership in a generally defined set is not necessarily decidable, the functions are not automatically in bijection with all the subsets of. So constructively, subsets are a more elaborate concept than characteristic functions. In fact, in the context of some non-classical axioms on top of CZF, even the power class of a singleton, e.g. the class of all subsets of, is shown to be a proper class.
Onto power classes
Below, the fact is used that the special case of the negation introduction law implies that is contradictory.For simplicitly of the argument, assume is a set. Then consider a subset and a function. Further, as in Cantor's theorem about power sets, define
where,
This is a subclass of defined in dependency of and it can also be written
It exists as subset via Separation. Now assuming there exists a number with implies the contradiction
So as a set, one finds is -productive in that we can define an obstructing for any given surjection. Also note that the existence of a surjection would automatically make into a set, via Replacement in CZF, and so this function existence is unconditionally impossible.
We conclude that the subcountability axiom, asserting all sets are subcountable, is incompatible with being a set, as implied e.g. by the power set axiom.
Following the above prove makes it clear that we cannot map onto just either. Bounded separation indeed implies that no set whatsoever maps onto.
Relatedly, for any function, a similar analysis using the subset of its range shows that cannot be an injection. The situation is more complicated for function spaces.
In classical ZFC without Powerset or any of its equivalents, it is also consistent that all subclasses of the reals which are sets are subcountable. In that context, this translates to the statement that all sets of real numbers are countable. Of course, that theory does not have the function space set.