Subcountability

This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (September 2020) (Learn how and when to remove this template message)

In constructive mathematics, a collection ${\displaystyle X}$ is subcountable if there exists a partial surjection from the natural numbers onto it. This may be expressed as

${\displaystyle \exists (I\subseteq \omega ).\,\exists f.\,(f\colon I\twoheadrightarrow X).}$

where ${\displaystyle \omega }$ is the set of natural numbers (${\displaystyle {\mathbb {N} }}$ with disregard for arithmetic) and where ${\displaystyle f\colon I\twoheadrightarrow X}$ denotes that ${\displaystyle f}$ is a surjective function from ${\displaystyle I}$ onto ${\displaystyle X}$. In other words, all elements of a subcountable collection ${\displaystyle X}$ are functionally in the image of an indexing set of counting numbers ${\displaystyle I\subseteq \omega }$ and thus the set ${\displaystyle X}$ can be understood as being dominated by the countable set ${\displaystyle \omega }$.

Discussion[]

Example[]

An important case is where ${\displaystyle X}$ denotes some subclass of a bigger class of functions as studied in computability theory.

Consider the total computable functions and note that being total is not a decidable property, i.e. there cannot be a constructive bijection between the total functions and the natural numbers. However, via enumeration of the codes of all possible partial computable functions (which also allows non-terminating programs), subsets of those, such as the total functions, are seen to be subcountable sets. Note that by Rice's theorem on index sets, most domains ${\displaystyle I}$ are not recursive. Indeed, no effective map between all counting numbers ${\displaystyle \omega }$ and the infinite (non-finite) indexing set ${\displaystyle I}$ is asserted here, merely the subset relation ${\displaystyle I\subseteq \omega }$. Being dominated by a constructively non-countable set of numbers ${\displaystyle I}$, the name subcountable thus conveys that the uncountable set ${\displaystyle X}$ is no bigger than ${\displaystyle \omega }$.

The demonstration that ${\displaystyle X}$ is subcountable also 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, which tie the existence of a function between infinite (non-finite) sets to questions of effectivity and decidability, the subcountability property splits from countability and is thus not a redundant notion. The indexing set ${\displaystyle I}$ of natural numbers may be posited to exist, e.g. as a subset via set theoretical axioms like the separation axiom schema, so that

${\displaystyle \forall (i\in I).(i\in \omega )}$.

But this set may then still fail to be detachable, in the sense that

${\displaystyle \forall (n\in \omega ).{\big (}(n\in I)\lor \neg (n\in I){\big )}}$

cannot be proven without assuming it as an axiom. One may fail to effectively count ${\displaystyle X}$ if one fails to map the counting numbers ${\displaystyle \omega }$ into the indexing set ${\displaystyle I}$, for this reason.

In classical mathematics[]

Asserting all laws of classical logic, the disjunctive property of ${\displaystyle I}$ discussed above indeed does hold for all sets. Then, for nonempty ${\displaystyle X}$, the properties numerable (${\displaystyle X}$ injects into ${\displaystyle \omega }$), countable (${\displaystyle \omega }$ has ${\displaystyle X}$ as its range), subcountable (a subset of ${\displaystyle \omega }$ surjects into ${\displaystyle X}$) and also not ${\displaystyle \omega }$-productive (a countability property essentially defined in terms of subsets of ${\displaystyle X}$, formalized below) are all equivalent and express that a set is finite or countably infinite.

Non-classical assertions[]

Not asserting the law of excluded middle

${\displaystyle (\phi \lor \neg \phi )}$ for all proposition ${\displaystyle \phi }$,

it can then also 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 ${\displaystyle {\mathbb {N} }^{\mathbb {N} }}$ out of the full set ${\displaystyle \omega }$, as in ${\displaystyle \omega \twoheadrightarrow {\mathbb {N} }^{\mathbb {N} }}$, may be disproven. But subcountability ${\displaystyle I\twoheadrightarrow {\mathbb {N} }^{\mathbb {N} }}$ of an uncountable set ${\displaystyle {\mathbb {N} }^{\mathbb {N} }}$ by a set ${\displaystyle I\subseteq \omega }$ that is not effectively detachable from ${\displaystyle \omega }$ may be permitted.

As ${\displaystyle {\mathbb {N} }^{\mathbb {N} }}$ is uncountable and classically in turn provably not subcountable, the classical framework with its large function space is incompatible with the constructive Church's thesis, an axiom of Russian constructivism.

Set theories[]

Cantorian arguments on subsets of the naturals[]

As reference theory we look at the constructive set theory ${\displaystyle {\mathsf {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 ${\displaystyle Y^{X}}$ is set, given ${\displaystyle X,Y}$ are also sets. In this theory, it is moreover consistent to assert that every set is subcountable.

The compatibility of various axioms is discussed in this section by means of possible surjections on an infinite set of counting numbers ${\displaystyle I\subseteq {\mathbb {N} }}$.

The situations discussed below—onto function spaces versus onto power classes—are different insofar as for functions ${\displaystyle f\colon X\to Y}$, by definition there exists a unique return value for every value ${\displaystyle x\in X}$ in the domain, ${\displaystyle \exists !(y\in Y).f(x)=y}$. As opposed to general predicates and their truth values (not necessarily just true and false), a function (which in programming terms is terminating) makes accessible information about data for all its subdomains (subsets of the ${\displaystyle X}$). Viewed as characteristic functions, they decide membership. As such, in ${\displaystyle {\mathsf {CZF}}}$, the (total) functions ${\displaystyle X\to \{0,1\}}$ are not automatically in bijection with all the subsets of ${\displaystyle X.}$ Constructively, subsets are a more involved concept than characteristic functions.

In fact, in the context of some non-classical axioms, even the power class of a singleton, e.g. the class ${\displaystyle {\mathcal {P}}\{0\}}$ of all subsets of ${\displaystyle \{0\}}$, is shown to be a proper class.

Onto function spaces[]

Asserting the permitted subcountability of all sets turns, in particular, ${\displaystyle {\mathbb {N} }^{\mathbb {N} }}$ into a subcountable set.

So here we consider a surjective function ${\displaystyle f\colon I\twoheadrightarrow {\mathbb {N} }^{\mathbb {N} }}$ and the set comprehended/separated as^[1]

${\displaystyle {\Big \{}\langle n,y\rangle \in {\mathbb {N} }\times {\mathbb {N} }\mid {\big (}n\in I\land D(n,y){\big )}\lor {\big (}\neg (n\in I)\land y=1{\big )}{\Big \}}}$

with the diagonalizing predicate defined as

${\displaystyle D(n,y)={\big (}\neg (f(n)(n)\geq 1)\land y=1{\big )}\lor {\big (}\neg (f(n)(n)=0)\land y=0{\big )}}$

which we can also phrase without the negations as

${\displaystyle D(n,y)={\big (}f(n)(n)=0\land y=1{\big )}\lor {\big (}f(n)(n)\geq 1\land y=0{\big )}}$.

This set is classically a function in ${\displaystyle {\mathbb {N} }^{\mathbb {N} }}$ and can classically be used to prove that the existence of the ${\displaystyle f}$ is actually contradictory. However, constructively, unless the proposition ${\displaystyle n\in I}$ in its definition is decidable so that the set actually defined a functional assignment, we just cannot draw this conclusion.

In this fashion, subcountability of ${\displaystyle {\mathbb {N} }^{\mathbb {N} }}$ is permitted. Nevertheless, also in the case of ${\displaystyle {\mathsf {CZF}}}$, the existence of a full surjection ${\displaystyle {\mathbb {N} }\twoheadrightarrow {\mathbb {N} }^{\mathbb {N} }}$, with domain ${\displaystyle {\mathbb {N} }}$, is indeed contradictory, since membership of ${\displaystyle I={\mathbb {N} }}$ is decidable.

Beyond these observations, also note that for any non-zero number ${\displaystyle d}$, the functions ${\displaystyle i\mapsto f(i)(i)+d}$ in ${\displaystyle I\to {\mathbb {N} }}$ involving the surjection ${\displaystyle f}$ cannot be extended to all of ${\displaystyle {\mathbb {N} }}$ by a similar contradiction argument. In other words, there are then partial functions that cannot be extended to full functions ${\displaystyle {\mathbb {N} }\to {\mathbb {N} }}$. Note that when given a ${\displaystyle n\in {\mathbb {N} }}$, one cannot necessarily decide whether ${\displaystyle n\in I}$, and so one cannot even decide whether the value of a potential function extension on ${\displaystyle n}$ is even already determined for a surjection ${\displaystyle f}$.

The subcountibility axiom, asserting all sets are subcountable, is incompatible with any new axiom making ${\displaystyle I}$ countable, including ${\displaystyle {\mathrm {LEM} }}$.

Onto power classes[]

Next we study possible postulates of the existence of a surjection ${\displaystyle f\colon I\twoheadrightarrow {\mathcal {P}}{\mathbb {N} }}$. (This, by Replacement in ${\displaystyle {\mathsf {CZF}},}$ would imply ${\displaystyle {\mathcal {P}}{\mathbb {N} }}$ is a set.) The violating subset of ${\displaystyle I}$ is

${\displaystyle \{n\in {\mathbb {N} }\mid n\in I\land D(n)\},}$

which, as ${\displaystyle I\subseteq {\mathbb {N} }}$, in this case simplifies to just

${\displaystyle \{n\in I\mid D(n)\}}$

where

${\displaystyle D(n)=\neg (n\in f(n)),}$

adapted from Cantors theorem about power sets. That subset exists via Separation. The existence of the surjection immediately implies the existence of a number ${\displaystyle c\in I}$ with

${\displaystyle c\in f(c)\iff \neg (c\in f(c))}$,

rendering membership necessarily undecidable and incompatible with any realization.^[2] Propositions of this form, ${\displaystyle P\iff \neg P}$, must be rejected according to the consequences of the negation introduction law. So such a surjection does not exist and ${\displaystyle {\mathcal {P}}{\mathbb {N} }}$ cannot be subcountable.

We conclude that the subcountability axiom, asserting all sets are subcountable, is incompatible with ${\displaystyle {\mathcal {P}}{\mathbb {N} }}$ being a set, as implied e.g. by the power set axiom.

The notion of size[]

As seen in the example of the function space considered in computability theory, not every infinite subset of ${\displaystyle \omega }$ necessarily is in constructive bijection with ${\displaystyle \omega }$, thus making room for a more refined distinction between uncountable sets in constructive contexts. The function space ${\displaystyle {\mathbb {N} }^{\mathbb {N} }}$ (and also ${\displaystyle \{0,1\}^{\mathbb {N} }}$) in a moderately rich set theory is always found to be neither finite nor in bijection with ${\displaystyle {\mathbb {N} }}$, 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. Motivated by the above sections, the infinite set ${\displaystyle {\mathbb {N} }^{\mathbb {N} }}$ may be considered "smaller" than the class ${\displaystyle {\mathcal {P}}{\mathbb {N} }}$. 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 out of ${\displaystyle X}$ and equality of cardinalities being defined in terms of bijections. Moreover, note that constructively, an ordering "${\displaystyle <}$" like that of cardinalities can be undecidable.

Models[]

The above analysis affects formal properties of codings of ${\displaystyle \mathbb {R} }$. Models for this non-classical extension of ${\displaystyle {\mathsf {CZF}}}$ theory have been constructed.^[3] 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.

More examples:

• There are models of ${\displaystyle {\mathsf {IZF}}}$ in which all sets with apartness relations are subcountable.^[4]
• In the constructive set theory ${\displaystyle {\mathsf {CZF}}}$, as discussed, it is indeed consistent to assert the Subcountability Axiom that all sets are (internally) subcountable. 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 validate that all sets are even countable.

Subcountable implies not ω-productive[]

Any countable set is subcountable and any subcountable set is not ${\displaystyle \omega }$-productive: A set ${\displaystyle X}$ is said to be ${\displaystyle \omega }$-productive if, whenever any of its subsets is the range of some partial function ${\displaystyle g}$ on ${\displaystyle \omega }$, there always remains at least one element that lies outside that range. This may be expressed as

${\displaystyle \forall g.\,{\big (}(g\colon \omega \to X)\implies \exists (x\in X).\,x\notin {\mathrm {rng} }(g){\big )}.}$

A set being ${\displaystyle \omega }$-productive speaks for how hard it is to generate its elements: They cannot be generated using a single function. As such, ${\displaystyle \omega }$-productive sets escape subcountability. Diagonal arguments often involve this notion, be it explicitly or implicitly.

See also[]

• Cantor's diagonal argument
• Computable function
• Constructive set theory
• Schröder–Bernstein theorem
• Subquotient
• Total order

References[]