# Countable Union of Finite Sets is Countable

## Contents

## 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 $\mathcal F$ be a countable set of finite sets.

Without loss of generality, assume that $\varnothing \notin \mathcal F$.

Then $\mathcal F$ is either finite or countably infinite.

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

Suppose instead that $\mathcal F$ is countably infinite.

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

For each $n \in \N$, let $e \left({n}\right)$ be the set of all bijections from $|f \left({n}\right)|$ to $f \left({n}\right)$.

By Cardinality of Set of Bijections $e \left({n}\right)$ is finite for each $n \in \N$.

$\operatorname{Img} \left({e}\right)$, 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, $\operatorname{Img} \left({e}\right)$ has a choice function $c$.

Let $q = c \circ e$.

Then for each $n \in \N$, $q \left({n}\right)$ is a bijection from some finite ordinal to $f \left({n}\right)$.

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

- $g \left({0}\right) = \left({0, 0}\right)$
- $\displaystyle g \left({n^+}\right) = \begin{cases} \left({g_1 \left({n}\right), g_2 \left({n}\right)^+}\right) & : g_2 \left({n}\right)^+ \in \operatorname{Dom} \left({q \left({n}\right)}\right) \\ \left({g_1 \left({n}\right)^+, 0}\right) & : \text{otherwise} \end{cases}$

where $g_1 \left({n}\right)$ and $g_2 \left({n}\right)$ are the first and second components of $g \left({n}\right)$.

Now define a mapping $h: \N \to \mathcal F$ by defining:

- $h \left({n}\right) = q \left({g_1 \left({n}\right)}\right) \left({g_2 \left({n}\right)}\right)$

$\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:

- $g \left({x}\right) = f \left({\min \left\{{n \in \N: f \left({n}\right) \in x}\right\}}\right\}$

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, $\left\{{n \in \N: f \left({n}\right) = y}\right\}$ is non-empty.

Thus $\left\{{n \in \N: f \left({n}\right) \in x}\right\}$ is non-empty.

Thus by the Well-Ordering Principle, $\left\{{n \in \N: f \left({n}\right) \in x}\right\}$ has a smallest element.

But by the definition of smallest element:

- $\min \left\{{n \in \N: f \left({n}\right) \in x}\right\} \in \left\{{n \in \N: f \left({n}\right) \in x}\right\}$

so $g \left({x}\right) \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$