nonenumerability

Nonenumerability, or non-enumerability, refers to the property of a set that cannot be put into a one-to-one correspondence with the natural numbers. A set is enumerable if it is finite or countably infinite; equivalently, there exists a bijection between the set and the natural numbers. If no such bijection exists, the set is non-enumerable.

The most familiar example is the set of real numbers, or any interval such as [0,1]. These sets are uncountable; in particular, their cardinality is strictly greater than aleph-null. In contrast, the natural numbers, integers, and rational numbers are enumerable, even though the rationals are dense in the reals.

Cantor’s diagonal argument shows that the real numbers are not countable, hence non-enumerable. The argument constructs a real number that differs from every number in a given listing at some decimal (or binary) position, ensuring it cannot appear in that list. More generally, Cantor’s theorem implies that for any set A, the power set P(A) has strictly greater cardinality than A, so P(A) is non-enumerable if A is infinite.

Consequences and variants: Non-enumerability is a central concept in set theory and cardinal arithmetic. The cardinality of the continuum (the size of the real numbers) is 2^{aleph-null}, and there exist uncountable sets with even larger cardinalities, such as certain function spaces or power sets of larger sets. In computability theory, enumerable can refer to recursive enumerability; non-enumerable in that context means not recursively enumerable, a stronger notion than being noncountable.