Countable Union of Finite Sets is Countable

From ProofWiki
Jump to navigation Jump to search


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$