Learning path

Full curriculum

Full curriculum

Unit content

Countable infinite sets

An infinite set is countably infinite when its elements can be placed in one-to-one correspondence with the natural numbers.

Equivalently, its elements can be arranged in a sequence

$$a_0,a_1,a_2,\ldots$$

that eventually lists every element exactly once.

Integers are countable

Although the integers extend infinitely in both directions, they can be enumerated as

$$0,1,-1,2,-2,3,-3,\ldots$$

so $\mathbb Z$ is countable.

Rational numbers are countable

Pairs of integers can be arranged in a grid and traversed diagonally. After skipping duplicate fraction representations and zero denominators, this produces an enumeration of $\mathbb Q$.

Thus the rational numbers are dense on the real number line yet still have the same cardinality as the natural numbers.

Countable unions

A countable union of countable sets is countable under the ordinary set-theoretic assumptions used here.

Countability distinguishes infinite sets whose elements can still be indexed one by one from larger infinities that no sequence can exhaust.