Union of Countable Sets of Sets/Proof 2

Theorem

Let $\AA$ and $\BB$ be countable sets of sets.

Then:

$\set {A \cup B: A \in \AA, B \in \BB}$

is also countable.

Proof

Both $\AA$ and $\BB$ are countable.

Enumerate their elements by the sequences $\sequence {A_n}_{n \mathop \in \N}$ and $\sequence {B_n}_{n \mathop \in \N}$ respectively.

When one of $\AA$ and $\BB$ would be finite, achieve such sequences by allowing elements to occur multiple times.

Define $\CC := \set {A \cup B: A \in \AA, B \in \BB}$.

For each $C \in \CC$, define the set $N_C := \set {\tuple {i, j} \in \N \times \N: A_i \cup B_j = C}$.

The definition of $\CC$ ensures that $N_C \ne \O$ for all $C \in \CC$.

Consider the lexicographic ordering $\preccurlyeq_l$ on $\N \times \N$.

Combining the Well-Ordering Principle with Finite Lexicographic Order on Well-Ordered Sets is Well-Ordering, $\preccurlyeq_l$ is a well-ordering on $\N \times \N$.

As $N_C \subseteq \N \times \N$ is non-empty, it thus has a smallest element; call it $n_C$.

Define now the map $\phi: \CC \to \N \times \N$ by $\map \phi C = n_C$.

Well-Ordering Minimal Elements are Unique ensures that $\phi$ is well-defined.

Now suppose that $C_1, C_2 \in \CC$ satisfy:

$\map \phi {C_1} = \map \phi {C_2}$

that is, $n_{C_1} = n_{C_2}$, which in turn equal some $\tuple {i, j} \in \N \times \N$.

As $\tuple {i, j} \in N_{C_1}$ and $\tuple {i, j} \in N_{C_2}$, $C_1 = A_i \cup B_j = C_2$.

It follows that $\phi$ is an injection.

Finally, $\N \times \N$ is countable by Cartesian Product of Countable Sets is Countable.

Let $\psi: \N \times \N \to \N$ be an injection.

Then $\psi \circ \phi: \CC \to \N$ is also an injection by Composite of Injections is Injection.

Hence $\CC$ is countable.

$\blacksquare$