Countability and Uncountability

Let $A$ and $B$ be sets (Injection, surjection, bijection for the terminology).

• $A$ and $B$ are equinumerous, written $A \approx B$, if there exists a bijection $f : A \to B$.
• $A$ is dominated by $B$, written $A \preceq B$, if there exists an injection $f : A \to B$.
• $A \prec B$ abbreviates: $A \preceq B$ and not $A \approx B$.

• $\approx$ behaves like an equivalence relation. It is reflexive ($\mathrm{id}_A$ is a bijection), symmetric (the inverse of a bijection is a bijection) and transitive (a composition of bijections is a bijection). The careful statement is that these three properties hold for all sets, and that $\approx$ restricted to any set of sets is an equivalence relation on that set. It is not a relation on "the set of all sets", which does not exist; the reflexivity, symmetry and transitivity statements are schemas about arbitrary sets, which is all any argument below uses.

• $\preceq$ is reflexive and transitive, for the same reasons, and $A \approx B$ implies both $A \preceq B$ and $B \preceq A$. The converse, that $A \preceq B$ and $B \preceq A$ together give $A \approx B$, is a theorem and not a triviality: it is The Schröder-Bernstein theorem, and it is proved without any use of choice.

• Subsets. $A \subseteq B$ implies $A \preceq B$, since the inclusion map is injective. The reverse fails badly for infinite sets: the successor map $\sigma$ is a bijection $\mathbb{N} \to \mathbb{N} \setminus \{0\}$, being injective and never zero (The von Neumann naturals form a Peano system) and hitting every nonzero natural (Every nonzero natural number is a successor), so $\mathbb{N} \approx \mathbb{N} \setminus \{0\}$ and a proper subset can be equinumerous with the whole.

• $\approx$ is the library's substitute for "has the same number of elements", stated without introducing cardinal numbers. Everything on this page is phrased with $\approx$, $\preceq$ and $\prec$ alone, so no theory of cardinals is presupposed.

Let $\mathbb{N} = \omega$ be the von Neumann naturals, with $0 = \varnothing$ and $\sigma(n) = n \cup \{n\}$ (The natural numbers $\mathbb{N}$ (von Neumann)), and let $\le$ and $<$ be the order defined additively by $m \le n \iff \exists k \in \mathbb{N}\ (m + k = n)$ and $m < n \iff (m \le n$ and $m \ne n)$ (Order on the natural numbers). Then $\mathbb{N}$ is a transitive set: every element of a natural number is itself a natural number. Moreover, for all $m, n \in \mathbb{N}$:

1. $m < n \iff m \in n$;
2. $m \le n \iff m \subseteq n$;
3. $n < \sigma(n)$, and $m < \sigma(n) \iff m \le n$;
4. $0 \le n$, and $0 \in n$ whenever $n \ne 0$.

Consequently $n = \{\, m \in \mathbb{N} : m < n \,\}$ for every $n$: a natural number is exactly the set of the naturals below it.

Why this is proved here. Order on the natural numbers defines the order additively and records the identification with membership only as an orienting remark, without proof. The countability arguments on this page use that identification as a working fact, so it is established here, from the additive order and induction alone. Nothing below uses ordinals or any later material.

• Nothing here is circular. The order used throughout is the additive one of Order on the natural numbers, and every fact quoted about it, linearity ($\le$ is a linear order on $\mathbb{N}$), trichotomy (Trichotomy of the order on $\mathbb{N}$) and discreteness (Discreteness: $\sigma(n)$ is the immediate successor), is proved on the naturals page from addition and induction, with no appeal to membership. The two set-theoretic inputs, that each $n$ is transitive with $n \notin n$ (Every natural number is a transitive set and is not a member of itself), are likewise proved there by induction on the von Neumann encoding alone.

• Step 5.2 is where irreflexivity of membership does real work: without $n \notin n$ the inclusion $m \subseteq n$ would not exclude $n < m$.

• The duplication with the ordinals page is deliberate. There, membership is made the order by fiat: Ordinal (von Neumann) ↗ defines $\alpha < \beta$ to mean $\alpha \in \beta$, and $\omega$ is the least limit ordinal ↗ then re-derives claim 1 while identifying $\mathbb{N}$ with the ordinals below $\omega$. That page comes far later in the library, so nothing here may cite it without circularity, and building the ordinals would be a very expensive way to obtain a fact this page needs only for the naturals. The two proofs are independent and agree.

Let $\mathbb{N}$ be the von Neumann naturals, with $0 = \varnothing$ and $\sigma(n) = n \cup \{n\}$ (The natural numbers $\mathbb{N}$ (von Neumann)), and let $<$ be the order of Order on the natural numbers, so that $m < n \iff m \in n$ and $n = \{\, m \in \mathbb{N} : m < n \,\}$ (On $\mathbb{N}$ the order is membership: $m < n \iff m \in n$). Write $\approx$ for equinumerosity (Equinumerous sets, $A \approx B$ and $A \preceq B$). Then:

1. for every $n \in \mathbb{N}$ there is no injection $\sigma(n) \to n$;
2. if $m < n$ then there is no injection $n \to m$;
3. if $n \approx m$ with $n, m \in \mathbb{N}$, then $n = m$;
4. $\mathbb{N} \not\approx n$ for every $n \in \mathbb{N}$;
5. no natural number is equinumerous with a proper subset of itself: if $A \subseteq n$ and $n \approx A$, then $A = n$.

Claim 1 is the pigeonhole principle in its sharpest form, that $n + 1$ pigeons do not fit injectively into $n$ holes; the other four are the consequences the library actually quotes. Claim 3 says a finite set is equinumerous with exactly one natural number, so "the number of elements" is well defined. Claim 4 says $\mathbb{N}$ is infinite. Claim 5 says no natural number is Dedekind-infinite.

Why this is proved here. The next item on this page defines finiteness as equinumerosity with a natural number, and the three size classes it introduces are exhaustive by construction but mutually exclusive only because of claim 4. Several later items also need claim 3 or claim 5. The principle is elementary and belongs with the naturals, but it is about counting rather than about order, so it is proved here, immediately before finiteness is defined, from induction and the identification of the order with membership alone. Nothing below uses ordinals, cardinals, or any later material.

• Where the work is. Everything rests on claim 1, and claim 1 rests on one device: a map into $\sigma(n)$ can be modified by a transposition of the codomain so that the top point $\sigma(n)$ goes to the top value $n$, after which the rest of the map misses $n$ and lands in $n$. Without that normalisation the inductive hypothesis does not apply, since an arbitrary injection $\sigma(\sigma(n)) \to \sigma(n)$ need not send anything to $n$.

• No choice is used. Every map built above is defined by an explicit rule: the transposition is given by three cases, and the only element selected anywhere is a single $j \in n \setminus A$ in step 5.3, a single choice from a nonempty set, which needs no choice principle.

• Claim 5 and the two notions of infinity. A set is Dedekind-infinite when it is equinumerous with a proper subset of itself. Claim 5 says no natural number is, and transporting along a bijection extends this to every finite set, which is the ZF half of the comparison discussed in FALSE: every infinite set has a countably infinite subset, in ZF: Dedekind-infinite implies infinite outright in ZF, while the converse is not a theorem of ZF unless ZF is inconsistent, that item's conclusion being conditional on the consistency of ZF and resting on an external independence result quoted rather than proved. The successor map $\sigma : \mathbb{N} \to \mathbb{N} \setminus \{0\}$ shows $\mathbb{N}$ itself is Dedekind-infinite, so the restriction to natural numbers in claim 5 is essential.

• Relation to the ordinals page. Cardinal (initial ordinal) and cardinality ↗ calls an ordinal $\kappa$ a cardinal when no $\alpha \in \kappa$ satisfies $\alpha \approx \kappa$. Claim 3 makes every natural number a cardinal and claim 4 makes $\omega$ one, which is what licenses the traditional $\aleph_0 = \omega$. That page comes much later in the library; the pointer here is orientation only, and nothing above rests on it.

Recall that a natural number is a von Neumann natural (The natural numbers $\mathbb{N}$ (von Neumann)): $0 = \varnothing$ and $\sigma(n) = n \cup \{n\}$, so that

$n = \{\, m \in \mathbb{N} : m < n \,\} = \{0, 1, \dots, n-1\}$

is itself the set of its predecessors. Here $<$ is the order of Order on the natural numbers, which is defined additively, so the displayed identity is a theorem and not a convention: it is On $\mathbb{N}$ the order is membership: $m < n \iff m \in n$, proved immediately above. Let $A$ be a set, and let $\approx$ be equinumerosity (Equinumerous sets, $A \approx B$ and $A \preceq B$).

• $A$ is finite if $A \approx n$ for some $n \in \mathbb{N}$.
• $A$ is countably infinite if $A \approx \mathbb{N}$.
• $A$ is at most countable if it is finite or countably infinite.
• $A$ is uncountable if it is not at most countable.

• Convention: in this library "countable" alone always means "at most countable", so a finite set is countable. This is the convention of Halmos and of Tao, and it is the one that makes the theorems on this page read cleanly: subsets, products and unions of countable sets are countable, with no finite/infinite case split in the statement. The competing convention, used by Rudin among others, reserves "countable" for "countably infinite" and says "at most countable" for the disjunction. Under that convention every statement below still holds after replacing "countable" with "at most countable", but several would become false as literally written. Where the distinction matters, the long forms "countably infinite" and "at most countable" are used in full, and "uncountable" always means "not at most countable", on which the two conventions agree.

• The three classes are exhaustive by construction: every set is finite, countably infinite, or uncountable, since "uncountable" is defined as the negation of the disjunction. That they are also mutually exclusive, that is, that no set is both finite and countably infinite, is a genuine theorem amounting to $\mathbb{N} \not\approx n$ for every $n \in \mathbb{N}$, and it is proved immediately above as claim 4 of The pigeonhole principle on $\mathbb{N}$. So a countably infinite set is never finite, and "$A$ is infinite", meaning not finite, is implied by $A \approx \mathbb{N}$. The same lemma pins down finiteness itself: by its claim 3 a finite set is equinumerous with exactly one natural number, so the number of elements of a finite set is well defined, and by its claim 5 no finite set is equinumerous with a proper subset of itself.

• What the exclusivity is and is not used for below. Nothing on this page needs it in order to run: the infinitude of $\mathbb{Q}$, for instance, is obtained by exhibiting a bijection $\mathbb{Q} \approx \mathbb{N}$ directly ($\mathbb{Q}$ is countably infinite) rather than by ruling out finiteness. It is used where the two notions of infinity are compared (FALSE: every infinite set has a countably infinite subset, in ZF) and where the continuum hypothesis is instantiated at $\mathbb{N}$ (The continuum hypothesis, and what this page does not prove), both of which need $\mathbb{N}$ to be infinite as a fact rather than as a convention.

• $0$ and the empty set. $0 = \varnothing$, and $A \approx 0$ holds exactly when $A = \varnothing$, so the empty set is finite. This matters in the proofs below, where the empty case is always separated out: a surjection $\mathbb{N} \to A$ cannot exist when $A = \varnothing$, which is why A nonempty set is at most countable iff it is a surjective image of $\mathbb{N}$ assumes $A$ nonempty.

• Countability is a property of a set alone, not of a set with structure. In particular $\mathbb{Q}$ is countable while carrying a dense order, and $\mathbb{R}$ is uncountable; neither statement says anything on its own about the order or the arithmetic those sets carry.

Let $A$ and $B$ be sets with $A \preceq B$ and $B \preceq A$ (Equinumerous sets, $A \approx B$ and $A \preceq B$). Then $A \approx B$.

Equivalently: if there is an injection $A \to B$ and an injection $B \to A$, then there is a bijection $A \to B$ (Injection, surjection, bijection).

The proof uses no choice principle. The bijection is written down explicitly from the two given injections, and the only "selections" it makes are of the unique preimage of a point under an injection, which is determined, not chosen. The single infinite construction is an application of the recursion theorem (The recursion theorem), whose data are a set, a starting point and one function.

• The set $C$ is exactly the set of points of $A$ reachable from the "unmatched" part $A \setminus g[B]$ by applying $g \circ f$ finitely often. On $C$ the bijection follows $f$ forwards; off $C$ it runs $g$ backwards. Both halves are forced: a point outside $g[B]$ cannot be an image of $g$, and once one point is handled by $f$ its $g \circ f$ image must be handled by $f$ too.

• Why the choice-freeness is worth stating. Many textbook proofs phrase the construction as "follow the chain of preimages backwards until it stops", which sounds like an infinite sequence of selections. It is not: the preimage under an injection is unique when it exists, and the recursion above is a single application of The recursion theorem to one explicitly given function $S \mapsto g[f[S]]$. The theorem is a theorem of ZF.

• With this theorem, $\preceq$ behaves like an order on equinumerosity classes: $A \preceq B$ and $B \preceq A$ give $A \approx B$. Comparability, that $A \preceq B$ or $B \preceq A$ holds for any two sets, is a different matter entirely: over ZF it is equivalent to the Axiom of Choice (The Axiom of Choice), a classical result quoted here and proved nowhere on this page, the harder half of it going back to Hartogs. Nothing on this page uses comparability.

Let $A$ be at most countable (Finite, countably infinite, countable, uncountable) and let $B \subseteq A$. Then $B$ is at most countable.

The proof establishes the sharper statement about subsets of $\mathbb{N}$ from which this follows: a subset $S \subseteq \mathbb{N}$ is finite if it is bounded above, and countably infinite if it is not.

No choice principle is used. This is the point of the lemma rather than a footnote to it. The enumeration of an unbounded $S \subseteq \mathbb{N}$ is built by always taking the least element of $S$ above the previous one, and the least element of a nonempty set of naturals is canonical (The well-ordering principle): it is determined by $S$, not selected from it. Replacing "least" by "some" would turn the construction into an appeal to dependent choice.