Union of Countable Sets of Sets

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 1

Since $\AA$ is countable, its contents can be arranged in a sequence:

$\AA = \set {A_1, A_2, \ldots}$

Let $B \in \BB$.

Consider the sequence of sets:

$\sequence {A_1 \cup B, A_2 \cup B, \ldots}$

We may leave out any possible repetitions, and obtain a countable set:

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

for every $B \in \BB$.

Thus as $B$ varies over all the elements of $\BB$, we obtain the countable family:

$\sequence {A \cup B: A \in \AA}_{\paren {B \mathop \in \BB} }$

From Countable Union of Countable Sets is Countable, their union is countable.

$\blacksquare$

Axiom of Choice

This proof depends on the Axiom of Choice, by way of Countable Union of Countable Sets is Countable.

Because of some of its bewilderingly paradoxical implications, the Axiom of Choice is considered in some mathematical circles to be controversial.

Most mathematicians are convinced of its truth and insist that it should nowadays be generally accepted.

However, others consider its implications so counter-intuitive and nonsensical that they adopt the philosophical position that it cannot be true.

Proof 2

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$

Proof 3

Since $\AA$ and $\BB$ are countable, $\AA \times \BB$ is countable by Cartesian Product of Countable Sets is Countable.

Thus by Surjection from Natural Numbers iff Countable there is a surjection $f: \N \to \AA \times \BB$.

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

Let $g: \AA \times \BB \to \CC$ be defined by letting $\map g {A, B} = A \cup B$.

$g$ is a surjection:

Let $C \in \CC$.

Then there exist $A \in \AA$ and $B \in \BB$ such that $C = A \cup B$.

By the definition of Cartesian product:

$\tuple {A, B} \in \AA \times \BB$

Then:

$\map g {A, B} = A \cup B = C$

It follows that $g$ is a surjection.

By Composite of Surjections is Surjection, $g \circ f: \N \to \CC$ is surjective.

Hence $\CC$ is countable.

$\blacksquare$