Wikipedia / Subcountability
Wikipedia / Subcountability
In constructive mathematics is subcountable if there exists a partial surjection from the natural numbers.
Discussion
Nomenclature
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.
may be called a subquotient.
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 onto the set of total computable functions from the diagonal construction, which could never be in such a surjections image. However, via the codess of all possible partial computable functions of the natural numbers. Being dominated by an uncomputable set of natural numbers, the name subcountable is provenly not computably enumerable is then also not countable.
is subcountable at the same time implies that it is classically (non-constructively) 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 (non-finite) sets to questions of decidability and possibly of effectivity of natural numbers may be posited to exist, e.g. as a subset via set theoretical axioms like the separation axiom schema, 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. In particular, constructively this converse direction does not generally hold.
In classical mathematics
Asserting all laws of classical logic) 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 (i.e. non-constructively) exceed the cardinality of the natural numbers. Note that in a constructive setting, a countability claim about the function space may be permitted.
, 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
-productive is the range of some partial function that remains in the complement of that range.
, then its corresponding compliment as described would equal the empty set-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 by considering only the computably enumerable's to be the image of a total recursive so called production function.
may be used to characterize the space of partial functions one finds
with any surjective (possibly partial) 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 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 shall denote a model of the standard natural numbers.
in the domain,
. Constructively, fewer such existential claims will be provable than classically.
). When as characteristic functions are not automatically in bijection, is shown to be a proper class.
Onto power classes
of the negation introduction law is contradictory.
. Further, as in Cantor's theorem about power sets, define into a set, via Replacement in CZF, and so this function existence is unconditionally impossible.
We conclude that the subcountability axiom, asserting all sets being a set, as implied e.g. by the power set axiom.
.
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..
Onto function spaces
into a subcountable set.
separated as in its definition is decidable so that the set actually defined a functional assignment, we cannot prove this set to be a member of the function space. And so we just cannot draw the classical conclusion.
makes the set also not countable, i.e. uncountable.
.
countable, including LEM.
Models
. Models for the non-classical extension of CZF theory by subcountability postulates have been constructed. Such non-constructive axioms can be seen as choice principles which, however, do not tend to increase the proof-theoretical strengths of the theories much.
There are models of IZF in which all sets with apartness relations are subcountable.
CZF has a model in, for example, the Martin-Löf type theory. In this constructive set theory with classically uncountable function spaces, it is indeed consistent to assert the Subcountability Axiom, saying that every set is subcountable. As discussed, the resulting theory is in contradiction to the axiom of power set and with the law of excluded middle.
More stronger yet, some models of Kripke–Platek set theory, a theory without the function space postulate, even validate that all sets are countable.
The notion of size
Subcountability as judgement of small size shall not be conflated with the standard mathematical definition of cardinality relations as defined by Cantor, with smaller cardinality being defined in terms of injections and equality of cardinalities being defined in terms of bijections. Constructively, the preorder, by Cantor's diagonal argument. This is what it means to be uncountable. But the argument that the cardinality of that set would thus in some sense exceed that of the natural numbers relies on a restriction to just the classical size conception and its induced ordering of sets by cardinality.
As seen in the example of the function space considered in computability theory.
Related properties
A subcountable set has alternatively also been called subcountably indexed" in the definition is replaced by the existence of a set that is a subset of some finite set. This property is variously called subfinitely indexed.
In category theory all these notions are subquotients.