Countable and Uncountable Sets¶

Definition¶

A set is countably infinite if it has the same cardinality as the natural numbers, equivalently if there is a bijection between the set and $\mathbb{N}\text{.}$

A set is countable if it is finite or countably infinite. A set that is not countable is called uncountable.

Interpretation¶

A countable set is one whose elements can be listed as a first, a second, a third element and so on, with every element appearing somewhere. An uncountable set is too large for this: every sequence indexed by the natural numbers misses some of its elements.

The zigzag runs through the pairs $(i,j)$ along the diagonals on which $i+j$ is constant. The pair $(1,1)$ gets the number $1$, the pairs $(2,1)$ and $(1,2)$ get $2$ and $3$, the diagonal with $i+j=4$ gets $4$, $5$ and $6$, and so on. Each diagonal is finite, so every pair receives a number, and different pairs receive different numbers. This is a bijection between the numbers $1,2,3,\ldots$ and the pairs, so $\mathbb{N}\times\mathbb{N}$ is countably infinite, although it looks larger than $\mathbb{N}$.

Repeated entries in a list can be skipped: reading $(i,j)$ as the fraction $i/j$ and skipping repeats such as $2/2=1/1$$1/1$, the zigzag lists every positive rational number; adding $0$ and the negatives shows that $\mathbb{Q}$ is countable. Uncountability is harder to show, since every possible list must fail: Cantor's diagonal argument builds, from any list of numbers in $[0,1]$, a number not on it.

A common slip is to treat infinite and uncountable as the same. $\mathbb{N}$, $\mathbb{Z}$ and $\mathbb{Q}$ are infinite but countable, of size aleph null; $\mathbb{R}$ is strictly larger and has the cardinality of the continuum.

Key Results¶

• Every finite set is countable.
• Every subset of a countable set is countable.
• $\mathbb{N}$, $\mathbb{Z}$, and $\mathbb{Q}$ are countably infinite.
• Cantor's diagonal argument shows that $[0,1]$ and $\mathbb{R}$ are uncountable.

Examples¶

• $\{1,2,3\}$ is countable because it is finite.
• The even natural numbers are countably infinite: $n\mapsto 2n$ gives a bijection from $\mathbb{N}$.
• The real interval $[0,1]$ is uncountable.

Prerequisites¶

• Cardinality
• Natural Number

Related Concepts¶

• Aleph Null
• Cardinality of the Continuum
• Finite and Infinite Sets
• Infinity
• Continuum Hypothesis

Sources¶

• Math II: Linear Algebra · Week 1

Aliases: countable set, uncountable set, uncountably infinite, at most countable Symbols: integers, natural numbers, rational numbers, real numbers

Last updated: 20 October 2026 03:02