Countable set

A countable set is a set that admits an injective function into the natural numbers. It is therefore either a finite set or a countably infinite set.

Every family of pairwise disjoint nonempty open disks in the plane is countable. The density of the rational numbers gives each disk a point of the countable set ${\mathbb{Q}}^2$. Fixing an enumeration and taking the first point in each disk yields an injection from disks to labels. This argument requires no countable choice of representatives and is useful when geometric separation would otherwise produce an uncountable family.

A family of countable sets indexed by a linear order is increasing if $i\le j$ implies $X_i\subseteq X_j$. Its union has cardinality at most ${\aleph }_1$, by the cardinal bound for an increasing chain of countable sets. The index order need not be a well-order.

An increasing chain of countable sets has union of cardinality at most ${\aleph }_1$. If the union is uncountable, select ${\aleph }_1$ of its points and one containing member for each. Every countable member misses one selected point, so linear comparison puts it below that point's chosen member. The chosen subfamily is cofinal, and its union has size at most ${\aleph }_1$ by infinite cardinal arithmetic.

A finite Cartesian product of countable sets is countable. For a fixed finite exponent $m$, index tuples in ${\mathbb{N}}^m$ can be listed by increasing maximum coordinate, with each group finite. If $B$ is countably infinite and $m>0$, its power $B^m$ is also countably infinite.

Given finite lists ${\ell }_0,{\ell }_1,\dots$ in a set $X$, their union of entries has an explicit enumeration from a subset of ${\mathbb{N}}^2$: use the existing positions in each list and a Cantor pairing function. If the union is infinite, successively take the first occurrence of an entry not previously taken, in the order of its natural-number code. The well-order on natural numbers makes each step uniquely determined and yields an injection $\mathbb{N}\to X$. No axiom of choice is needed. This does not assert that an arbitrary countable family of unordered finite sets has a countable union in ZF without the axiom of choice.

If every sequence of distinct elements of a positive-real set $A$ has arithmetic averages tending to zero, then $A$ is a countable set. For each positive integer $n$, the threshold set $\{a\in A:a\ge 1/n\}$ must be finite: an infinite sequence inside it would have averages at least $1/n$. The Archimedean property makes $A$ their union, so the countable union of countable sets theorem applies. The hypothesis concerns every distinct-element sequence, not merely one enumeration.

A countably infinite set admits a bijection with the natural numbers.

For an infinite subset $A\subseteq \mathbb{N}$, repeatedly selecting the least element not yet used gives a bijection $f:\mathbb{N}\to A$. The well-order ensures each minimum exists, infinitude ensures the remaining set is nonempty, and strict increase gives injectivity. If $a\in A$ were omitted forever, all selected values would be at most $a$, impossible inside the finite set $\{0,\dots ,a\}$.

A countable union of countable sets is countable, using a diagonal enumeration.

A parabola parametrized by $(t,t^2)$ is in bijection with $\mathbb{R}$ and is an uncountable set. Every affine line meets it in at most two points. A countable family of affine lines could therefore cover only countably many points of this parabola, and cannot cover the plane. More generally, an uncountable curve with finite intersection with every permitted member obstructs a countable covering by those members.

The Cantor pairing function is an explicit bijection between ${\mathbb{N}}^2$ and $\mathbb{N}$, obtained by enumerating lattice points along successive diagonals.

Cantor's diagonal argument proves that the infinite binary sequences form an uncountable set: a sequence obtained by changing the $n$th digit of the $n$th listed sequence differs from every sequence in the list.