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 $\FF$ be a countable set of non-empty finite sets.

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 $\mathbf f: \N \to \FF$.

Written in the family notation, this means that $\mathbf f = \family {F_m}_{m \mathop \in \N}$, with the properties that:

$\forall m \in \N: F_m \in \FF$
for all $F \in \FF$ there is exactly one $m \in \N$ such that $F = F_m$

Hence $\ds \bigcup \FF$ is the same thing as $\ds \bigcup \limits_{m \mathop \in \N} F_m$.


Each $F \in \FF$ is finite..

Also, by hypothesis, each $F \in \FF$ is non-empty.

Hence the cardinality $k$ of $F$ is a (strictly) positive integer $k \ge 1$.

By definition of set equivalence, there exists a bijection $\set {0, \ldots, k - 1} \to F$.

Let $\map \BB F$ be the (non-empty) set of all such bijections $\set {0, \ldots, k - 1} \to F$.

Then by Cardinality of Set of Bijections:

$\map \BB F$ is finite.

The family $\family {\map \BB {F_m} }_{m \mathop \in \N}$ is then a countable family of non-empty finite sets.

By the axiom of countable choice for finite sets the family $\family {\map \BB {F_m} }_{m \mathop \in \N}$ has a choice function:

$\mathbf q = \family {q_m}_{m \mathop \in \N}$

Each $q_m$ is thus a bijection $\set {0, \ldots, \card {F_m} - 1} \to F_m$.


Define a mapping $\ds \gamma: \N^2 \to \bigcup_{m \mathop \in \N} F_m$ as:

$\forall m, n \in \N: \map \gamma {m, n} = \begin {cases} \map {q_m} n & : n \le \card {F_m}-1 \\ \map {q_0} 0 & : \text {otherwise} \end {cases}$

Every $\ds x \in \bigcup_{m \mathop \in \N} F_m$ is element of some $F_m \in \FF$.

Thereby $x$ is the image of some integer $n \le \card {F_m} - 1$ under the map $q_m$.

$x$ is then of the form $\map \gamma {m, n}$ for some $\tuple {m, n} \in \N^2$.

Since $x \in \bigcup_{m \mathop \in \N} F_m$ is arbitrary, $\gamma$ is surjective.


Finally, let $\sigma$ be some surjection $\N \to \N^2$.

From Cartesian Product of Countable Sets is Countable, such a map exists.

By Composite of Surjections is Surjection $\gamma \circ \sigma$ is a surjection $\N \to \bigcup \FF$.

Hence $\gamma \circ \sigma$ is countable.

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