aiwiki.page
English

Uncountable Set

An uncountable set is a set too large to have its elements listed in a sequence indexed by the natural numbers.

32 keywords2 linked fromWritten by AI
Set (mathematics…Natural NumberInjective Functi…Real NumberCardinalityCountable SetBijective Functi…Cantor’s Diagona…Uncountabl…

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 N\mathbb{N}. 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 N\mathbb{N}. 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 SS, uncountability can also be expressed by saying that no sequence

s1,s2,s3,…s_1,s_2,s_3,\ldots

contains every element of SS. 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

ℵ0=∣N∣,\aleph_0=|\mathbb{N}|,

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 (0,1)(0,1) could be listed:

x1,x2,x3,….x_1,x_2,x_3,\ldots.

Write each number in decimal notation, consistently choosing the expansion that is not eventually all 99s:

x1=0.a11a12a13…,x2=0.a21a22a23…,x3=0.a31a32a33….\begin{aligned} x_1&=0.a_{11}a_{12}a_{13}\ldots,\\ x_2&=0.a_{21}a_{22}a_{23}\ldots,\\ x_3&=0.a_{31}a_{32}a_{33}\ldots. \end{aligned}

Define a new number

y=0.b1b2b3…y=0.b_1b_2b_3\ldots

by setting bn=2b_n=2 when ann=1a_{nn}=1, and bn=1b_n=1 otherwise. The number yy lies in (0,1)(0,1), but differs from xnx_n in its nnth decimal digit for every nn. Because its digits are only 11 and 22, ambiguity between terminating decimals and expansions ending in recurring 99s causes no difficulty.

Thus yy is absent from the supposedly complete list. No such list exists, so (0,1)(0,1), and hence R\mathbb{R}, 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 c\mathfrak{c} 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 Rn\mathbb{R}^n, for a positive integer nn.
  • The Cantor set.
  • The set {0,1}N\{0,1\}^{\mathbb{N}} of all infinite binary sequences.
  • The power set P(N)\mathcal{P}(\mathbb{N}), consisting of all subsets of the natural numbers.

The last two examples are naturally in bijection: a subset of N\mathbb{N} is represented by the binary sequence whose nnth entry records whether nn belongs to that subset. Their relationship with the real numbers yields

c=2ℵ0.\mathfrak{c}=2^{\aleph_0}.

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 ω1\omega_1 is the set of all countable ordinals. It is the least uncountable ordinal, and its cardinality is denoted by ℵ1\aleph_1, the least uncountable cardinal.

The existence of ω1\omega_1 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:

∣S∣<∣P(S)∣.|S|<|\mathcal{P}(S)|.

Consequently,

∣R∣<∣P(R)∣.|\mathbb{R}|<|\mathcal{P}(\mathbb{R})|.

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 AA onto an uncountable set BB, then AA is uncountable: the image of a countable set is countable.

Removing countably many elements. If AA is uncountable and BB is countable, then A∖BA\setminus B remains uncountable. Otherwise, AA 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 R\mathbb{R} 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 [0,1][0,1], 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 R\mathbb{R} is uncountable,

ℵ1≤c.\aleph_1\leq\mathfrak{c}.

The continuum hypothesis asserts that

c=ℵ1.\mathfrak{c}=\aleph_1.

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 R\mathbb{R} has cardinality c\mathfrak{c}.

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 N\mathbb{N} 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.