An uncountable set is a set that is neither finite nor countably infinite: its elements cannot all be listed in a sequence indexed by the natural numbers. Equivalently, there is no injective function from it into . The real numbers are the standard example. Uncountability is a property of a set’s size, or cardinality, rather than its geometric extent, density, or the ease with which its elements can be described.
Definition and comparison with countability
A set is called countable if it is finite or admits a bijection with . Some authors reserve “countable” for countably infinite sets and use “at most countable” for the broader class; the meaning of uncountable is the same under either convention.
For a nonempty set , uncountability can also be expressed by saying that no sequence
contains every element of . Repetitions are allowed in this formulation: even a list with repetitions cannot exhaust an uncountable set.
In the usual framework of set theory with the axiom of choice, an uncountable set has cardinality strictly greater than
the cardinality of a countably infinite set. Uncountability therefore distinguishes different sizes of infinity, not merely infinite sets from finite ones.
Why the real numbers are uncountable
The most familiar proof uses Cantor’s diagonal argument. Suppose, for contradiction, that every real number in the interval could be listed:
Write each number in decimal notation, consistently choosing the expansion that is not eventually all s:
Define a new number
by setting when , and otherwise. The number lies in , but differs from in its th decimal digit for every . Because its digits are only and , ambiguity between terminating decimals and expansions ending in recurring s causes no difficulty.
Thus is absent from the supposedly complete list. No such list exists, so , and hence , is uncountable.
This argument does not merely show that a particular listing fails. It provides a way to construct a missing element from any proposed listing.
Principal examples
Sets with the cardinality of the continuum
The cardinality of the real numbers is denoted by and called the cardinality of the continuum. Several apparently different sets have this same size:
- Every real interval containing two distinct points.
- The set of all irrational numbers.
- The set of complex numbers.
- Every finite-dimensional Euclidean space , for a positive integer .
- The Cantor set.
- The set of all infinite binary sequences.
- The power set , consisting of all subsets of the natural numbers.
The last two examples are naturally in bijection: a subset of is represented by the binary sequence whose th entry records whether belongs to that subset. Their relationship with the real numbers yields
Although individual real numbers can have two binary expansions, this ambiguity can be handled when establishing the cardinal equality.
By contrast, the rational numbers are countable. Their occurrence throughout every real interval does not make them uncountable.
The first uncountable ordinal
The ordinal is the set of all countable ordinals. It is the least uncountable ordinal, and its cardinality is denoted by , the least uncountable cardinal.
The existence of supplies a fundamental example of uncountability arising from order structure rather than from the real line.
Sets larger than the continuum
Cantor’s theorem states that every set has strictly smaller cardinality than its power set:
Consequently,
Taking successive power sets produces indefinitely larger infinite cardinalities. There is therefore no single “size of uncountability” and no largest cardinality.
Basic properties and proof methods
Several standard principles make it possible to establish uncountability without constructing a diagonal argument each time.
Containment. Any set containing an uncountable subset is uncountable. More generally, an injection from a known uncountable set into another set proves that the latter is uncountable.
Surjections. If there is a surjection from onto an uncountable set , then is uncountable: the image of a countable set is countable.
Removing countably many elements. If is uncountable and is countable, then remains uncountable. Otherwise, would be a union of two countable sets and would itself be countable.
Countable unions. In standard set theory with choice, a countable union of countable sets is countable. Therefore, if an uncountable set is expressed as a countable union, at least one member of that union must be uncountable.
Products. A Cartesian product with an uncountable factor and a nonempty other factor is uncountable, because fixing an element of the other factor gives an injection of the uncountable factor into the product.
These principles are frequently used in mathematical analysis and other branches of mathematics.
Uncountability, measure, and topology
Uncountability must be distinguished from other notions of mathematical size.
Measure
In measure theory, every countable subset of has Lebesgue measure zero. It follows that any subset of positive Lebesgue measure is uncountable.
The converse fails. The Cantor set is uncountable but has measure zero. Thus a set can contain as many points as the whole real line while occupying no positive length in the measure-theoretic sense.
A related distinction appears in probability. Under the uniform distribution on , every individual outcome has probability zero, while the entire interval has probability one. There is no contradiction: probability measures are countably additive, not additive over arbitrary uncountable families.
Topological structure
In topology, uncountability does not imply that a set contains an interval or has nonempty interior. The Cantor set again provides a counterexample.
Conversely, a dense set need not be uncountable. The rational numbers are dense in the real line but countable. The real line is also a separable space because it has a countable dense subset, despite being uncountable itself.
The continuum hypothesis
Because is uncountable,
The continuum hypothesis asserts that
Equivalently, it states that there is no set whose cardinality lies strictly between that of the natural numbers and that of the real numbers.
This assertion is independent of the standard axioms of Zermelo–Fraenkel set theory together with the axiom of choice, abbreviated ZFC, assuming those axioms are consistent. It is therefore important to distinguish uncountable, meaning larger than countable, from having the cardinality of the continuum. ZFC does not prove that every uncountable subset of has cardinality .
Historical development and foundational qualifications
Georg Cantor established the uncountability of the real numbers in work published in 1874. His original proof differed from the diagonal argument, which he published in 1891. These results helped establish the study of infinite cardinalities as a central part of set theory.
Most standard treatments assume ZFC. Without the axiom of choice, some familiar statements about infinite sets require qualification. In particular, a countable union of countable sets need not be countable, and an infinite set need not contain a countably infinite subset. The definition of uncountability as the absence of an injection into remains meaningful, but identifying it with a position in a hierarchy of well-ordered cardinalities requires additional care.
Uncountability is also relative to the sets and functions available within a model of set theory. A model that is countable from an external perspective may contain a set it regards as uncountable because it contains no function enumerating that set. This distinction underlies the apparent paradox associated with the Löwenheim–Skolem theorem; it does not produce a contradiction in the definition of uncountability.