# Countable Set

How big is infinity? The integers, the rationals, and the algebraic numbers are all infinite [sets](/page/Set), yet every one of them can be arranged into a single list indexed by the natural numbers. The real numbers cannot. This distinction — between infinities that can be enumerated and those that resist enumeration — is the starting point of the theory of [cardinality](/page/Cardinality), and the concept of a *countable set* sits at its heart.

This article develops the idea of countability from first principles. We begin by asking what it means for two infinite sets to have "the same size," arrive at Cantor's definition via [bijections](/page/Function), and then build up the basic toolkit: closure under subsets, products, and countable unions. With these tools in hand we prove that $\mathbb{Q}$ and the algebraic numbers are countable, and then show — via Cantor's diagonal argument — that $\mathbb{R}$ is not. The article closes with [Cantor's theorem](/theorems/758) on power sets, which reveals that there is no largest infinity, and with the Schroeder–Bernstein theorem, which provides the practical criterion most often used to establish that two sets have the same cardinality.

## Motivation

[motivation] ### Infinity is not one thing At first glance it is tempting to believe that all infinite sets are "the same size." After all, both $\mathbb{N}$ and $\mathbb{R}$ go on forever; neither one runs out. But this naive view — that infinity is a single, monolithic quantity — collapses the moment we try to make it precise. Consider the sets $\mathbb{N} = \{1, 2, 3, \ldots\}$ and $2\mathbb{N} = \{2, 4, 6, \ldots\}$. The even numbers form a proper subset of the naturals, so in one sense $2\mathbb{N}$ is "smaller." Yet the map $n \mapsto 2n$ pairs every natural number with a unique even number and vice versa, leaving nothing unmatched on either side. By the criterion of perfect pairing, the two sets have the same size. This tension — that an infinite set can be matched one-to-one with a proper subset of itself — was noticed already by Galileo, and it shows that our finite intuitions about "part versus whole" do not carry over to the infinite. ### Bijections as the measure of size Georg Cantor resolved this tension in the 1870s with a bold proposal: two sets $A$ and $B$ have *the same cardinality* if and only if there exists a bijection $f: A \to B$. For finite sets this reproduces the familiar notion of "same number of elements." For infinite sets it provides a rigorous, unambiguous definition that does not depend on how the sets are described or on any notion of "containment." The entire theory of countability flows from this single idea. ### The shocking discovery With Cantor's definition in hand, two results emerge that reshape our understanding of infinity. First, the rational numbers $\mathbb{Q}$ — which are densely packed along the number line, with infinitely many rationals between any two distinct reals — turn out to be countable. There is a bijection $\mathbb{N} \to \mathbb{Q}$, so the rationals are no more numerous than the natural numbers. Second, and far more surprising, the real numbers $\mathbb{R}$ are *not* countable. No list, no matter how cleverly arranged, can include every real number. These two facts together reveal that there are genuinely different sizes of infinity, and countability is the dividing line between the smallest infinity and all larger ones. [/motivation]

## Formal Definition

The fundamental question is: which infinite sets are "small" in the sense that their elements can be listed? The answer requires making the notion of "listing" precise. A set whose elements can be matched one-to-one with a subset of the natural numbers is one that can — at least in principle — be enumerated by a procedure that assigns a natural number label to each element. Sets that admit such an enumeration are called *countable*; sets that do not are genuinely larger.

[definition:Countable Set] A [set](/page/Set) $X$ is **countable** if there exists an injection from $X$ into $\mathbb{N}$. Equivalently, $X$ is countable if $X$ is finite or if there exists a bijection $f: \mathbb{N} \to X$. [/definition]

The definition splits countable sets into two species. A finite set $\{x_1, x_2, \ldots, x_n\}$ is countable because the map $x_k \mapsto k$ injects it into $\mathbb{N}$. A countably infinite set is one that can be written as a list $x_1, x_2, x_3, \ldots$ indexed by the natural numbers, with every element of the set appearing exactly once. The empty set $\varnothing$ is countable: it is finite, and the empty [function](/page/Function) $\varnothing \to \mathbb{N}$ is an injection.

Not every infinite set is countable, and the distinction between countable and uncountable infinities is the central theme of this article. The following definitions isolate the two cases.

[definition:Countably Infinite Set] A set $X$ is **countably infinite** if there exists a bijection $f : \mathbb{N} \to X$. Equivalently, $X$ is countably infinite if it is infinite and countable. [/definition]

[definition:Uncountable Set] A set $X$ is **uncountable** if $X$ is infinite and not countable — that is, there is no injection from $X$ into $\mathbb{N}$. [/definition]

The convention that $\mathbb{N} = \{1, 2, 3, \ldots\}$ starts at $1$ (not $0$) is used throughout this article.

## Equivalent Characterisations

The definition of countability via injection into $\mathbb{N}$ is clean, but in practice one often wants to verify countability by producing a surjection from $\mathbb{N}$, without worrying about constructing an injection or a bijection. The following theorem says that all three approaches are equivalent, giving the working mathematician flexibility to choose whichever is most convenient.

[quotetheorem:753]

The characterisation via surjection is especially useful. To show a set $X$ is countable, it suffices to describe a procedure that lists every element of $X$ — even with repetitions. Conversely, if a set is countable and non-empty, we can always produce a surjection from $\mathbb{N}$ onto it, which means we can "enumerate" its elements as a (possibly repeating) [sequence](/page/Sequence) $x_1, x_2, x_3, \ldots$ that eventually hits every element.

The characterisation via injection is the workhorse for proving countability indirectly: embed $X$ into a known countable set, and you are done.

## Closure Properties

Three closure properties underpin almost every countability argument: countability is inherited by subsets, preserved under finite products, and stable under countable unions. These properties together make the class of countable sets remarkably robust — they allow us to assemble countable sets from countable building blocks, and to verify countability of complicated sets by reducing to simpler ones.