Subcountability

In constructive mathematics, a collection

X

{\displaystyle X}

is subcountable if there exists a partial surjection from the natural numbers onto it.

This may be expressed as

∃

(

I

⊆

N

)

.

∃

f

.

(

f

:

I

↠

X

)

,

{\displaystyle \exists (I\subseteq {\mathbb {N} }).\,\exists f.\,(f\colon I\twoheadrightarrow X),}

where

f

:

I

↠

X

{\displaystyle f\colon I\twoheadrightarrow X}

denotes that

f

{\displaystyle f}

is a surjective function from

I

{\displaystyle I}

onto

X

{\displaystyle X}

. The surjection is a member of

N

⇀

X

{\displaystyle {\mathbb {N} }\rightharpoonup X}

and here the subclass

I

{\displaystyle I}

of

N

{\displaystyle {\mathbb {N} }}

is required to be a set.

In other words, all elements of a subcountable collection

X

{\displaystyle X}

are functionally in the image of an indexing set of counting numbers

I

⊆

N

{\displaystyle I\subseteq {\mathbb {N} }}

and thus the set

X

{\displaystyle X}

can be understood as being dominated by the countable set

N

{\displaystyle {\mathbb {N} }}

.

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

X

{\displaystyle X}

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

N

{\displaystyle {\mathbb {N} }}

in the definition can also be abstracted away, and in terms of the more general notion

X

{\displaystyle X}

may be called a subquotient of

N

{\displaystyle {\mathbb {N} }}

.