---
tag: 0Z8FM54P86
kind: statement
role: theorem
name: Countable union of countable sets is countable
msc: ["03E10"]
uses: [0ZG61TFBES, 05GK32H72H, 08G4XH86JC, 0HTGB13FE2]
sources:
  - url: https://en.wikipedia.org/wiki/Countable_set
    locator: Formal overview
---

## Statement

Assume the [[axiom of choice|0HTGB13FE2]].
Let $I$ be a [[countable|0ZG61TFBES]] set and let $(A_i)_{i \in I}$ be a [[family of sets|05Q6G4EH2G]] such that each $A_i$ is countable.
Then the [[union|05GK32H72H]] $\bigcup_{i \in I} A_i$ is countable.

## Remarks

Proof: choose for each $i$ a surjection from $\mathbb{N}$ onto $A_i$, when $A_i$ is nonempty. Together they give a surjection from a subset of $\mathbb{N} \times \mathbb{N}$ onto the union, and $\mathbb{N} \times \mathbb{N}$ is countable.
The proof uses the axiom of countable choice to choose the surjections. Without any choice, the statement cannot be proved in ZF.
When the enumerations of the $A_i$ are given, no choice is needed.

## Explanations

### L1 human

List each set $A_i$ as a row of a grid.
Then list the grid diagonal by diagonal.
Each element of the union appears in the list.