Countable Sets

How many integers are there, compared to natural numbers? A first instinct says "twice as many." Yet a careful pairing shows the two collections match up perfectly, element for element. This surprising fact — that an infinite set can be placed in exact correspondence with a proper subset of itself — is the gateway to the modern theory of cardinality. Countable sets are the infinite sets that are, in a precise sense, the smallest kind of infinite: no bigger than the natural numbers ℕ. The idea matters because it draws a sharp, provable line inside the world of infinite collections. Not all infinities behave alike. Some sets, as later results show, are strictly larger than ℕ. But a remarkably wide class of familiar sets, including ℤ and ℚ, turn out to be exactly the same size as ℕ. This is not a philosophical opinion; it is a theorem. It is proved by exhibiting explicit bijections or injections. The big picture is a toolkit: once you know ℕ is countable, you get ℤ, ℚ, finite unions of countable sets, countable unions of countable sets, and finite products of countable sets all "for free." This happens via a handful of closure theorems. These closure properties are the engine behind an enormous amount of downstream mathematics. They range from the enumerability of algebraic numbers to the countability of the set of finite-length strings over a finite alphabet, which underlies computability theory. This article gives the precise definition of countability, and proves the central closure theorems with full rigor. It works through nontrivial examples (including the classical Cantor pairing enumeration of ℚ). It also shows exactly where the argument breaks if a hypothesis is dropped. This sets the stage for the discovery, via Uncountable Sets and Cantors Diagonal Argument, that not every infinite set is countable.

Key takeaways

A set is countable if it is finite or admits a bijection with ℕ; countably infinite means the latter.
Equivalently, a nonempty set $A$ is countable iff there is a surjection $\mathbb{N} \to A$ , or (for infinite $A$ ) an injection $A \to \mathbb{N}$ .
ℤ and ℚ are countably infinite, despite naive intuition suggesting they are "bigger" than ℕ.
Countable unions of countable sets are countable (using the Axiom of Countable Choice, or an explicit enumeration when one is given).
Finite (and countable) Cartesian products of countable sets are countable, proved via the Cantor pairing function.
Key idea: infinite size is measured by bijections, not by subset inclusion — a set can be in bijection with a proper subset of itself.

Where this lives today

Countability underlies computability theory: the set of all finite strings over a finite alphabet is countable (a countable union, over string lengths $n\in\mathbb{N}$ , of the finite sets of length- $n$ strings), which is why Turing machines, programs, and provable theorems can all be Gödel-numbered — assigned distinct natural number codes — a fact essential to the undecidability results of Turing and the incompleteness results of Gödel. In algebra and number theory, the countability of the algebraic numbers (roots of polynomials with integer coefficients) versus the uncountability of the reals gives, non-constructively, the existence of transcendental numbers without exhibiting a single one. In probability and measure theory, countable additivity of measures depends on countable (not arbitrary) unions of events being well-behaved, directly paralleling the closure theorem's index-set hypothesis. In topology and analysis, countable dense subsets (like $\mathbb{Q} \subset \mathbb{R}$ ) underlie the notion of separability, used throughout functional analysis. In cryptography and coding theory, the countability of the set of finite bit-strings guarantees that any countable message space can be injectively encoded into natural numbers, a prerequisite for hashing and enumeration schemes.

Ask the tutor: Why does the diagonal argument fail to show $\mathbb{N}\times\mathbb{N}$ is uncountable, yet succeed for $\{0,1\}^{\mathbb{N}}$ ?

A

Intuition

The naive way to compare two infinite collections is to check whether one contains the other. By that measure $\mathbb{N} \subsetneq \mathbb{Z}$ , so $\mathbb{Z}$ "should" be bigger. But cardinality compares sets by matching, not by containment: if every element of $A$ can be paired with exactly one element of $B$ and vice versa, with nothing left over on either side, then $A$ and $B$ have the same size, full stop — regardless of whether one happens to sit inside the other as a subset. This is exactly what happens with $\mathbb{Z}$ . Send $0 \mapsto 0$ , and then alternate: $1 \mapsto 1$ , $2 \mapsto -1$ , $3 \mapsto 2$ , $4 \mapsto -2$ , and so on, zig-zagging outward from $0$ . Every integer gets hit exactly once. The set " $\mathbb{Z}$ ," despite stretching infinitely in two directions, is not too big for a single one-directional list to capture. $\mathbb{Q}$ is more surprising still, since between any two rationals there are infinitely many others — $\mathbb{Q}$ is dense, while $\mathbb{N}$ is not. Cantor's trick is to stop thinking of $\mathbb{Q}$ as an ordered line and instead arrange all pairs $(p, q)$ on a two-dimensional grid, then snake through the grid diagonal by diagonal. Density is irrelevant to counting; only the existence of some systematic listing matters.

Figure

Enumerating ℤ by zig-zagging outward from 0, matched against ℕ

Central results

A

\Rightarrow

A

\Rightarrow

A

\mathbb{N}

Worked examples

Example 1: $\mathbb{Z}$ is countably infinite, via an explicit closed-form bijection. Define $f : \mathbb{N} \to \mathbb{Z}$ by

f(n) = \begin{cases} \dfrac{n}{2} & n \text{ even} \\[4pt] -\dfrac{n+1}{2} & n \text{ odd.} \end{cases}

So $f(0)=0, f(1)=-1, f(2)=1, f(3)=-2, f(4)=2,\dots$ Injectivity. Suppose $f(n) = f(n')$ . If $n, n'$ are both even, $n/2 = n'/2$ gives $n = n'$ . If both odd, $-(n+1)/2 = -(n'+1)/2$ gives $n=n'$ . If $n$ even and $n'$ odd, then $f(n) = n/2 \ge 0$ while $f(n') = -(n'+1)/2 \le -1/2 < 0$ (since $n' \ge 1$ when odd and $\ge 0$ ), so $f(n) \ne f(n')$ , contradiction — this case cannot occur. Hence $n, n'$ have the same parity and $n = n'$ . Surjectivity. Given $k \in \mathbb{Z}$ : if $k \ge 0$ , take $n = 2k$ (even, and $n/2 = k$ ); if $k < 0$ , take $n = -2k - 1$ (check parity: $-2k$ is even so $-2k-1$ is odd, and $n \ge 0$ since $k \le -1$ gives $-2k-1 \ge 1$ ; then $f(n) = -(n+1)/2 = -(-2k)/2 = k$ ). So every integer is hit. Hence $f$ is a bijection, and $\mathbb{Z}$ is countably infinite. Notice this also illustrates part (2) of the closure theorem directly: $\mathbb{Z} = \mathbb{N} \cup \{-1,-2,-3,\dots\}$ , a union of two countably infinite sets, so countability of $\mathbb{Z}$ also follows abstractly from the closure theorem — the explicit $f$ above is one concrete instantiation of that abstract argument.

Example 2: $\mathbb{Q}$ is countably infinite, via Cantor's grid argument, done carefully with signs. We show $\mathbb{Q}$ is countable using the closure theorem rather than reinventing an ad hoc bijection. Step 1. $\mathbb{Z}^+ \times \mathbb{Z}^+$ (positive integers) is countable, being in bijection with $\mathbb{N} \times \mathbb{N}$ via $(m,n) \mapsto (m-1,n-1)$ , and $\mathbb{N}\times\mathbb{N}$ is countable by part (4) of the closure theorem (via the pairing function $\pi$ ). Step 2. Define $\sigma : \mathbb{Z}^+ \times \mathbb{Z}^+ \to \mathbb{Q}^+$ (positive rationals) by $\sigma(p,q) = p/q$ . This is surjective: every positive rational equals $p/q$ for some positive integers $p, q$ (by definition of $\mathbb{Q}$ as ratios of integers). It is far from injective ( $\sigma(2,4) = \sigma(1,2)$ ), but surjectivity alone suffices: by the Corollary, since there is a surjection $\mathbb{N} \to \mathbb{Z}^+\times\mathbb{Z}^+$ (Step 1, composed appropriately) and then a surjection $\mathbb{Z}^+\times\mathbb{Z}^+ \to \mathbb{Q}^+$ , the composite is a surjection $\mathbb{N} \to \mathbb{Q}^+$ . Hence $\mathbb{Q}^+$ is countable. Step 3. $\mathbb{Q}^- = \{-q : q \in \mathbb{Q}^+\}$ is countable, being the image of the countable set $\mathbb{Q}^+$ under the bijection $q \mapsto -q$ (a bijective image of a countable set is countable — restrict the enumerating bijection of $\mathbb{Q}^+$ and post-compose with negation). Step 4. $\mathbb{Q} = \mathbb{Q}^+ \cup \{0\} \cup \mathbb{Q}^-$ is a union of three countable sets ( $\{0\}$ finite, hence countable), so by part (2) of the closure theorem (extended trivially from 2 to 3 sets by associativity), $\mathbb{Q}$ is countable. Since $\mathbb{Q}$ is visibly infinite (it contains the infinite set $\mathbb{N}$ ), $\mathbb{Q}$ is countably infinite: there exists a bijection $\mathbb{N} \to \mathbb{Q}$ . (Existence of some bijection follows abstractly: we exhibited an injection $\mathbb{Q}\to\mathbb{N}$ via the surjection-to-injection construction in the Corollary's proof, and combined with the trivial injection $\mathbb{N} \to \mathbb{Q}$ , a Schwarz–Cantor–Bernstein-style argument — the content of Comparing Cardinalities — upgrades the pair of injections to a genuine bijection.)

I

Scope, edge cases & common traps

Situation	Status	Why
$\emptyset$	Countable (finite)	Vacuously satisfies the finite case of the definition
$\mathbb{N}, \mathbb{Z}, \mathbb{Q}$	Countably infinite	Explicit bijections/surjections constructed above
$\mathbb{R}$ , $\mathcal{P}(\mathbb{N})$	Uncountable	Diagonal argument — see Uncountable Sets and Cantors Diagonal Argument
Countable union of countable sets, countable index	Countable	[[Central results	Closure Theorem]] part 3
Uncountable union of nonempty (even singleton) sets	Can be uncountable	Counterexample above
Finite product of countable sets	Countable	Closure Theorem part 4, via Cantor pairing
Countably infinite product ( $A^{\mathbb{N}}$ ) of countable sets, $\|A\|\ge2$	Generally uncountable	Diagonal argument applies; this is not covered by the theorem, which is stated only for finite products

Common trapThe classic error: sliding from "finite products" to "infinite products"

A very common mistake is to assume the closure-under-products theorem extends to countably infinite products, i.e. that $\prod_{n\in\mathbb{N}} A_n$ is countable whenever each $A_n$ is countable. This is false in general: even $\{0,1\}^{\mathbb{N}}$ , the set of infinite binary sequences, is uncountable, by exactly the diagonal argument used to show $\mathcal{P}(\mathbb{N})$ is uncountable. The finite-product theorem proved here relies essentially on encoding finitely many coordinates into a single natural number via iterated pairing; this encoding does not extend to infinite tuples, since there is no way to recover infinitely many independent pieces of information from one natural number while preserving injectivity. Always check whether "product" in a claim means finite or infinite before invoking closure.

The mathematician behind it

Origins · 1 minGeorg Cantor and how this was discovered

Georg Cantor

1845–1918 · Founder of set theory, Halle, Germany

Georg Cantor developed the theory of transfinite cardinal numbers in the 1870s–1880s, against considerable resistance from contemporaries such as Leopold Kronecker. His 1874 paper proving that the algebraic numbers are countable while the real numbers are not — the seed of the diagonal argument — marked the beginning of set theory as a mathematical discipline in its own right, rather than a mere convenience of language.

History

- 1874 — Cantor proves the algebraic numbers are countable and the reals are not, in his first paper on transfinite set theory.

- 1878 — Cantor defines cardinal equivalence via bijection and introduces the notion that infinite sets can have different "sizes."

- 1891 — Cantor publishes the diagonal argument in its modern, general form.

- 1895–1897 — Cantor's Beiträge zur Begründung der transfiniten Mengenlehre systematizes cardinal and ordinal arithmetic, including the countable/uncountable distinction used today.

- 1908–1922 — Zermelo and Fraenkel axiomatize set theory (ZF, later ZFC), placing Cantor's countability arguments — including the Axiom of Choice used implicitly in closure under countable unions — on a fully formal footing.

Is every infinite subset of a countable set countably infinite?

Yes, and this is exactly the key claim proved inside the Lemma: Injection Characterization: every infinite subset of $\mathbb{N}$ is countably infinite, constructed via the strictly increasing "take the next smallest unused element" function. Since any countable set injects into $\mathbb{N}$ , an infinite subset of a countable set injects into an infinite subset of $\mathbb{N}$ , hence is countably infinite by the same reasoning transported across the injection. This is part of why "countable" is such a robust, easy-to-use notion — subsets never cause surprises, unlike with uncountable sets where subsets can be countable, uncountable, or anything in between.

Does ℕ have the same cardinality as a proper subset of itself, and is that a contradiction?

Yes, and no — this is a defining feature of infinite sets, not a paradox. The even numbers $2\mathbb{N} = \{0,2,4,\dots\}$ are a proper subset of $\mathbb{N}$ , yet $n \mapsto 2n$ is a bijection $\mathbb{N} \to 2\mathbb{N}$ . Richard Dedekind in fact defined infinite sets as precisely those that can be placed in bijection with a proper subset of themselves — finite sets can never do this, since a bijection between a finite set and a proper subset would force the subset to have both fewer and equally many elements, which contradicts basic counting. So this "paradox" is really the theorem that distinguishes infinite from finite.

If A and B are both countably infinite, must A ∪ B be countably infinite, or could it be finite?

If $A$ and $B$ are both countably infinite, $A \cup B$ is always countably infinite (never finite), because $A \subseteq A \cup B$ and a set containing an infinite subset is itself infinite; combined with the closure theorem showing $A \cup B$ is countable, and infinite plus countable forces countably infinite by definition. The only way to get something finite from a union is if both original sets were finite to begin with.

Why does the Cantor pairing function need to be a bijection, rather than just a surjection or injection, for the product theorem?

Technically the full closure theorem only strictly needs $\pi:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ to be injective (to build an injection $A\times B \to \mathbb{N}$ by composing with injections $A\to\mathbb{N}$ , $B\to\mathbb{N}$ ). Proving it is a full bijection is slightly more work but gives a stronger, cleaner, and independently useful fact: it shows $\mathbb{N}\times\mathbb{N}$ and $\mathbb{N}$ are not just comparable in size but exactly the same size, which is needed elsewhere, e.g. when one wants an actual enumeration (not just an injective code) of pairs, as in explicitly listing rational numbers or Turing machine configurations.

Is the set of all finite subsets of ℕ countable?

Yes. For each $n \in \mathbb{N}$ , the set $[\mathbb{N}]^n$ of $n$ -element subsets of $\mathbb{N}$ injects into $\mathbb{N}^n$ (list the elements in increasing order to get an $n$ -tuple), and $\mathbb{N}^n$ is countable by finite products (Closure Theorem, part 4, extended to $n$ factors). So each $[\mathbb{N}]^n$ is countable. The set of all finite subsets of $\mathbb{N}$ is $\bigcup_{n\in\mathbb{N}} [\mathbb{N}]^n$ , a countable union (indexed by $\mathbb{N}$ , which is countable) of countable sets, hence countable by part (3) of the Closure Theorem. Note this is a genuinely different, much smaller set than $\mathcal{P}(\mathbb{N})$ , the set of all subsets (finite and infinite), which is uncountable.

Does this article's closure theorem tell us anything about ℝ or 𝒫(ℕ)?

Only indirectly, by contrast. Nothing in the Closure Theorem produces uncountable sets — quite the opposite, it shows how surprisingly hard it is to escape countability using unions and finite products of countable pieces. The existence of uncountable sets like $\mathbb{R}$ or $\mathcal{P}(\mathbb{N})$ requires a fundamentally different argument, the diagonal argument, covered in Uncountable Sets and Cantors Diagonal Argument. That article shows no surjection $\mathbb{N} \to \mathcal{P}(\mathbb{N})$ can exist, which is precisely the failure of the Corollary's condition for countability.

How does countability connect to cardinal arithmetic more generally?

Countability is the arithmetic statement $|A| \le \aleph_0$ , where $\aleph_0 = |\mathbb{N}|$ is the smallest infinite cardinal. The closure theorems proved here are special cases of general cardinal arithmetic facts: $\aleph_0 + \aleph_0 = \aleph_0$ (finite unions), $\aleph_0 \cdot \aleph_0 = \aleph_0$ (finite products via pairing), and $n \cdot \aleph_0 = \aleph_0$ for any countable index set (countable unions). These identities look bizarre compared to finite arithmetic — doubling or squaring an infinite quantity leaves it unchanged — and they are explored more systematically, alongside operations like $2^{\aleph_0}$ , in Cardinal Arithmetic.