Uncountable set
High school
Consider an infinite set $S$. The set is uncountable if it is impossible to list the elements of $S$ in an (infinite) list $a_1, a_2, a_3, \dots$. The set is so large that every such list must leave out some elements of $S$.
Undergraduate
Consider an infinite set $S$. The set $S$ is uncountable if there does not exist a surjection from $\nats$ onto $S$.
Examples
Examples
-
$[0, 1]$
High school
$[0, 1]$ is uncountable because Cantor’s diagonal argument shows that no list of numbers in $[0, 1]$ contains them all.
- The set of real numbers, $\reals$ High school
-
The set of all subsets of $\nats$
Undergraduate
By Cantor’s theorem, no set is in bijection with the set of all of its subsets.
-
The Cantor set
Undergraduate
Even though its total length is $0$, its points correspond to the infinite sequences of $0$s and $2$s in base $3$, which are uncountable.
Non-examples
Things that may be mistaken for examples.
-
The empty set $\emptyset$
(definition)
High school
The empty set is not uncountable, because it is finite.
- The integers $\mathbb{Z}$ High school
- $\nats$ High school
- The set of rational numbers, $\mathbb{Q}$ High school
-
$\mathbb{Q} \cap [0, 1]$
High school
$\mathbb{Q} \cap [0, 1]$ is bounded, because all of its elements are between $0$ and $1$, and it is not uncountable.
-
$\setdef{1, 2, 3}$
High school
$\setdef{1, 2, 3}$ is not uncountable, because it is finite.
Properties
- $\reals$ is uncountable (Cantor’s diagonal argument), and so is every interval with more than one point.
Distinctions involving this term
- Types of infinity: Infinity appears in several different senses: as the size of a set, as unboundedness, and as the limit of a divergent sequence. An infinite set has infinitely many elements, but it can be bounded. Infinite sets come in different sizes: countable and uncountable. A divergent sequence does not converge, but it doesn’t necessarily go to infinity.