Countably infinite set

Definition · applies to sets · also called denumerable

High school

Consider an infinite set, and try to list its elements in an infinite sequence $a_1, a_2, a_3, \dots$ The set is countably infinite if this can be done so that the list eventually reaches every element.

Undergraduate

Consider a set $S$. The set $S$ is countably infinite if $S$ is in bijection with $\nats$, so its elements can be listed as $a_1, a_2, a_3, \dots$ without missing any.

Examples

The integers $\mathbb{Z}$ High school
The integers are countably infinite, because they can be listed as $0, 1, -1, 2, -2, \dots$
$\nats$ High school
$\nats$ is countably infinite, and so infinite, because it can be listed as $0, 1, 2, \dots$.
$\mathbb{Q} \cap [0, 1]$ High school
$\mathbb{Q} \cap [0, 1]$ is countably infinite, and so infinite, because its infinitely many fractions can be listed.

Non-examples

Things that may be mistaken for examples.

$[0, 1]$ High school
$[0, 1]$ is not countably infinite, because it is uncountable.
The empty set $\emptyset$ (definition) High school
The set of real numbers, $\reals$ High school
The set of all subsets of $\nats$ Undergraduate

Properties

$\nats$, $\mathbb{Z}$, and $\mathbb{Q}$ are countably infinite, but $\reals$ is not.
Every infinite subset of a countably infinite set is countably infinite, and a countable union of countable sets is countable (assuming the axiom of countable choice).

Notes

“Countable” is ambiguous: some authors mean countably infinite, and others mean finite or countably infinite.

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.

All definitions · All distinctions · All examples