Subcountability

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 }$ are the counting numbers (${\displaystyle {\mathbb {N} }}$ with disregard for arithmetic) and where ${\displaystyle f\colon I\twoheadrightarrow X}$ denotes that the intersection of ${\displaystyle f}$ and ${\displaystyle I\times X}$ gives a total relation that is surjective. 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 subclass of total 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 functions (which also includes non-terminating 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 ${\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, 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 Separation axiom, 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 ${\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.

Set theories

Into function spaces

As an example, the theory CZF has Bounded Separation, Infinity, is agnostic towards the existence of power sets, but it includes the axiom that asserts that any function space ${\displaystyle X^{Y}}$ is set, given ${\displaystyle X,Y}$ are also sets. In this theory, it is moreover consistent to assert that every set is subcountable.

Asserting the permitted subcountability of all sets, ${\displaystyle {\mathbb {N} }^{\mathbb {N} }}$ is subcountable in particular. For a function on an infinite subset of the counting numbers, ${\displaystyle f\colon I\twoheadrightarrow {\mathbb {N} }^{\mathbb {N} }}$, consider the set comprehended 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 there be used to argue that ${\displaystyle f}$ cannot be a surjection. However, constructively, unless the propositions ${\displaystyle n\in I}$ in its definition are decidable so that the set actually defined a functional assignment, we cannot draw this the conclusion about the surjectivity of ${\displaystyle f}$.

For any non-zero number ${\displaystyle d}$, the functions ${\displaystyle i\mapsto f(i)(i)+d}$ in ${\displaystyle I\to {\mathbb {N} }}$ cannot be extended to all of ${\displaystyle {\mathbb {N} }}$ for the same reason. Note that when given a ${\displaystyle n\in {\mathbb {N} }}$, one cannot necessarily decide whether ${\displaystyle n\in I}$, i.e. whether the value of a potential function extension on ${\displaystyle n}$ is already determined by ${\displaystyle f}$. In other words, there are then partial functions that cannot be extended to full functions ${\displaystyle {\mathbb {N} }\to {\mathbb {N} }}$.

Nevertheless, even in this case, 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.

The subcountibility axiom is incompatible with any new axiom making ${\displaystyle I}$ countable, including LEM.

Into power classes

Assuming ${\displaystyle {\mathcal {P}}{\mathbb {N} }}$ is a set, the set violating a possible surjection ${\displaystyle f\colon I\twoheadrightarrow {\mathcal {P}}{\mathbb {N} }}$, given by

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

where

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

in Cantors theorem about power sets exists via Separation and indeed immediately leads to a contradiction.[2] This demonstrates that ${\displaystyle {\mathcal {P}}{\mathbb {N} }}$ can actually not be a set and is thus a proper class.

The two discussed situations are different in that a function makes accessible the data for all its subdomains (subsets of the superset). Naturally, in CZF, the total functions ${\displaystyle X\to \{0,1\}}$ are not in bijection with the subsets of ${\displaystyle X}$, a more involved concept. In fact, even the power set of a singleton, e.g. ${\displaystyle {\mathcal {P}}\{0\}}$, is shown to be a proper class in this context (there are provably not just the two truth values ${\displaystyle 0}$ and ${\displaystyle 1}$).

The notion of size

Motivated by the above, the infinite set ${\displaystyle {\mathbb {N} }^{\mathbb {N} }}$ may be considered "smaller" than the class ${\displaystyle {\mathcal {P}}{\mathbb {N} }}$. 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 ${\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. 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 uncountabile 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.

Models

The above analysis affects formal properties of codings of ${\displaystyle \mathbb {R} }$. Models for this non-classical extension of 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 IZF in which all sets with apartness relations are subcountable.[4]
• In 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 ${\displaystyle \omega }$-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}$, 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
• Total order

References

1. John L. Bell "Russel's Paradox and Diagonalization in a Constructive Context"
2. Daniel Méhkeri "A simple computational interpretation of set theory"
3. Rathjen, M. "Choice principles in constructive and classical set theories", Proceedings of the Logic Colloquium, 2002
4. McCarty, J. "Subcountability under realizability", Notre Dame Journal of Formal Logic, Vol 27 no 2 April 1986