# Countable Union of Finite Sets is Countable

## Theorem

The following statements are equivalent in $\mathrm{ZF}^-$:

- The Axiom of Countable Choice for Finite Sets holds.

- The union of any countable set of finite sets is countable.

## Proof

### Axiom of Countable Choice for Finite Sets implies Countable Union Condition for Finite Sets

Suppose that the Axiom of Countable Choice for Finite Sets holds.

Let $\FF$ be a countable set of finite sets.

Without loss of generality, assume that $\O \notin \FF$.

Then $\FF$ is either finite or countably infinite.

If $\FF$ is finite, then $\bigcup \FF$ is finite by Finite Union of Finite Sets is Finite, and thus countable.

Suppose instead that $\FF$ is countably infinite.

Then there is a bijection $f: \N \to \FF$.

For each $n \in \N$, let $\map e n$ be the set of all bijections from $\card {\map f n}$ to $\map f n$.

By Cardinality of Set of Bijections $\map e n$ is finite for each $n \in \N$.

$\Img e$, the image of $e$, is countable by Image of Countable Set under Mapping is Countable.

Thus by the Axiom of Countable Choice for Finite Sets, $\Img e$ has a choice function $c$.

Let $q = c \circ e$.

Then for each $n \in \N$, $\map q n$ is a bijection from some finite ordinal to $\map f n$.

Recursively define a mapping $g: \N \to \N \times \N$ thus:

- $\map g 0 = \tuple {0, 0}$
- $\map g {n^+} = \begin{cases} \tuple {\map {g_1} n, \map {g_2} n^+} & : \map {g_2} n^+ \in \Dom {\map q {\map {g_1} n} } \\ \tuple {\map {g_1} n^+, 0} & : \text{otherwise} \end{cases}$

where $\map {g_1} n$ and $\map {g_2} n$ are the first and second coordinates of $\map g n$.

Now define a mapping $h: \N \to \bigcup \FF$ by defining:

- $\map h n = \map {\map q {\map {g_1} n} } {\map {g_2} n}$

$\Box$

### Countable Union Condition for Finite Sets implies Axiom of Countable Choice for Finite Sets

Suppose that the union of every countable set of finite sets is countable.

Let $S$ be a countable set of non-empty finite sets.

Then $\bigcup S$ is countable.

Thus by Surjection from Natural Numbers iff Countable, there exists a surjection $f: \N \to \bigcup S$.

Define a mapping $g: S \to \bigcup S$ thus:

- $\map g x = \map f {\min \set {n \in \N: \map f n \in x} }$

This is a valid definition:

For each $x \in S$, $x$ is non-empty, so it has an element $y$.

Then by the definition of union, $y \in \bigcup S$.

Since $f$ is a surjection, $\set {n \in \N: \map f n = y}$ is non-empty.

Thus $\set {n \in \N: \map f n \in x}$ is non-empty.

Thus by the Well-Ordering Principle, $\set {n \in \N: \map f n \in x}$ has a smallest element.

But by the definition of smallest element:

- $\min \set {n \in \N: \map f n \in x} \in \set {n \in \N: \map f n \in x}$

so $\map g x \in x$.

Thus $g$ is a choice function for $S$.

As this holds for every countable set of finite sets, the Axiom of Countable Choice for Finite Sets holds.

$\blacksquare$