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.

For a countably infinite set, countability means that its members can be arranged as a sequence in which every member occurs exactly once. The order need not resemble the order already present in the set. For example, the integers can be listed as $0,1,-1,2,-2,\dots$. Simply increasing through positive values would never reach a negative one.

The Cartesian product ${\mathbb{N}}^2$ needs a similar change of strategy. Listing a whole horizontal row first would never finish that row, so later rows would be missed. Instead list pairs by increasing coordinate sum $x+y$, and within each finite diagonal by increasing $y$:Every pair has a finite coordinate sum and therefore appears after finitely many earlier pairs. This is the construction made explicit by the Cantor pairing function. It explains why having two infinite coordinates does not, by itself, mean a larger cardinality.

A family of pairwise disjoint real intervals of positive length is countable. Each interval contains a rational number in its interior by the density of the rational numbers. Fix an enumeration of the rational numbers and select the first member lying inside each interval. Disjointness makes this selection an injection into a countable set. The argument also applies to disjoint nonempty open subsets of the real line.

A finite subset $A$ of the natural numbers, numbered from one, has the binary code ${\sum }_{j\in A}{2}^{j-1}$. Distinct finite subsets give distinct codes, because the largest differing exponent exceeds the sum of all smaller powers of two. Thus the finite subsets form a countable set, although the entire power set is an uncountable set by the Cantor diagonal argument. An enumeration transfers this coding to any countable set.

Nondecreasing functions $\mathbb{N}\to \mathbb{N}$ form an uncountable set: every subset $A$ is encoded by the strictly increasing function $n+{\sum }_{k=1}^n{1}_A(k)$. In contrast, nonincreasing functions form a countable set because each is determined by a finite initial segment and its eventual constant value.

// Target: classical-mechanics.bigb

For every fixed positive integer $d$, the polynomial ring with integer coefficients in $d$ indeterminates is countably infinite. Polynomials of bounded total degree have only finitely many possible monomials, so they are encoded by a finite Cartesian power of the integers. Taking a countable union of countable sets over degree bounds proves countability; constant polynomials supply an infinite subset. Nonzero one-variable polynomials have finitely many real roots, so the real algebraic numbers form a countable set as well.

Every countable set $B$ of real numbers is contained in a countable set closed under taking all real roots of a polynomial with coefficients in that set. Let $\varphi (A)$ consist of these roots of a polynomial, excluding the zero polynomial. There are countably many finite coefficient lists over a countable set, and each nonzero polynomial has finitely many roots of a polynomial; hence $\varphi (A)$ is countable. Define $B_0=B$ and $B_{n+1}=B_n\cup \varphi (B_n)$. The countable union of countable sets theorem shows that $X={\bigcup }_n{B}_n$ is countable. Every finite coefficient list in $X$ belongs to one stage $B_N$, so its real roots of a polynomial belong to $B_{N+1}\subseteq X$. Retaining $B_n$ at the next stage matters: $\varphi (A)$ need not contain $A$.

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}$, with the natural numbers numbered from zero:If $d=x+y$, there are $1+2+\cdots +d=d(d+1)/2$ pairs on earlier diagonals, and the pair $(x,y)$ is at offset $y$ along diagonal $d$. The formula therefore gives exactly the enumeration above. For example, $\pi (2,3)=5\cdot 6/2+3=18$.

For the inverse at an index $k$, find the unique $d$ satisfying $d(d+1)/2\le k<(d+1)(d+2)/2$, then put $y=k-d(d+1)/2$ and $x=d-y$. At $k=18$, these are $d=5$, $y=3$, and $x=2$. Thus both the encoding and decoding are explicit. The bijection is useful for assigning a single natural number to a pair of indices, and iterating it does the same for fixed-length tuples.

Cantor's diagonal argument shows that the set of all infinite binary sequences is an uncountable set. Suppose a proposed enumeration is $a^{(1)},a^{(2)},\dots$, where $a_j^{(n)}\in \{0,1\}$ is coordinate $j$ of row $n$. Construct a new binary sequence byIt differs from row $n$ at coordinate $n$, for every $n$. It is consequently absent from the entire proposed list, regardless of how that list was chosen. The failure of an enumeration of all binary sequences follows from this precise point of disagreement, rather than from a claim that the list looks too small.

For the displayed window, the first six diagonal bits are $1,0,0,0,1,1$, so the new sequence starts $0,1,1,1,0,0$. The drawing shows only finitely many rows, but the rule defines every coordinate and excludes every row of an infinite list. This distinguishes the argument from the Cantor pairing function: that construction lists all pairs of finite indices, whereas this one concerns an entire infinite sequence as each object to be listed. Finite binary strings form a countable set; all infinite binary sequences do not.

The connection with power sets is exact: a subset $A\subseteq \mathbb{N}$ corresponds to its indicator function, with a one in position $n$ exactly when $n\in A$. Changing the diagonal membership bit is the same mechanism as the Cantor's theorem construction $D=\{x:x\notin f(x)\}$. This reusable method turns a purported complete list into an explicit omitted object.

In his paper ^[ref], presented in 1891 and printed in the 1890–91 volume in 1892, Cantor uses infinite sequences of two symbols for the diagonal construction and then gives the broader comparison of cardinalities. The binary notation here is a modern presentation of that construction.