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.

Course convention

In Math II: Linear Algebra, countable includes finite sets. Use countably infinite when the set must be infinite and in bijection with $\mathbb{N}\text{.}$

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.

A zigzag through a grid of positive-integer pairs, numbered along finite diagonals; subtracting one from each coordinate includes zero coordinates.

The figure lists pairs of positive integers 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$ , and the diagonal with $i+j=4$ gets $4$ , $5$ and $6$ . Each diagonal is finite, so every positive-integer pair receives exactly one number. Here $\mathbb{N}$ includes $0$ : subtracting $1$ from both coordinates and from every list label gives a bijection from $\mathbb{N}$ to $\mathbb{N}\times\mathbb{N}$ $N$ , including all pairs with a zero coordinate. Thus the product 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¶

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: 27 October 2026 11:52