2
$\begingroup$

Question

Is my proof that the union of countable sets is countable correct?

If $A_1, A_2, A_3,\dots, A_n$ is a collection of countable sets, then the union: $$A_1\cup A_2\cup A_3 \cup \dots A_n$$ is countable as well.

Attempted Proof

We attempt to prove the claim by induction.

  1. Base case: Consider the set $$B=A_2\setminus A_1$$ Clearly, $B\subseteq A_2$($B$ is countable) and $A_1\cup B$ = $A_1\cup A_2$.

  2. If $B$ is finite, then $$B= \{b_1, b_2, b_3, b_4, \dots, b_j \}\quad j\in\mathbb{N}_0$$ and so we can construct a bijection $$f(n)=\begin{cases} b_n\quad n\leq j\\ a_{n-j}\quad n> j \end{cases}$$ If $B$ is infinite, then we can construct a bijection $$f(n)=\begin{cases} b_{\frac n2}\quad n\text{ even}\\ a_{\frac{n+1}{2}}\quad n\text{ odd} \end{cases}$$

  3. Now, suppose the statement holds for $n= k\geq 2$, that is, $$A_1\cup A_2\cup A_3 \cup \dots A_k$$ is a countable set. Observe that $$(A_1\cup A_2\cup A_3 \cup \dots A_k)\cup A_{k+1}$$ is a union of two countable sets which, by the base case, is also countable.

  4. Thus, by induction, the statement holds for all $n\in\mathbb{N}.\qquad\square$

$\endgroup$
5
  • 1
    $\begingroup$ Your proof is okay if you are aiming to prove that a finite union of countable sets is countable (not an arbitrary union, as your title suggests). $\endgroup$
    – drhab
    Commented Mar 24, 2018 at 16:35
  • $\begingroup$ Yeah the exercise was concerning finite unions. Thank you very much. :) $\endgroup$
    – Adam
    Commented Mar 24, 2018 at 16:38
  • $\begingroup$ "Yeah the exercise was concerning finite unions. " Then it's a pretty toothless exercise. It's tempting to settle but it's usually a bad idea to. Be better to spruce this up to consider countable unions as that is also true and important (of course it's obviously not true for uncountable unions). $\endgroup$
    – fleablood
    Commented Mar 28, 2021 at 19:18
  • $\begingroup$ FYI : To obviate the need for worrying about set overlap - see this proof. $\endgroup$ Commented Aug 3, 2021 at 13:10
  • 1
    $\begingroup$ @fleablood Unlike the proof for finite unions, the proof for countable unions needs (a weak form of) the axiom of choice. $\endgroup$ Commented Jun 3, 2022 at 20:10

2 Answers 2

0
$\begingroup$

Your proof is indeed valid for a finite union of countable sets. A shorter, more immediate proof goes as follows.

For any integer $n \gt 2$, one can construct a bijection $\phi$ between $\mathbb N$ and a finite union of $n$ countable sets $A = \bigcup_{i=1}^n A_i$

$$\phi : i \mapsto A_{i \mod n} \left (\left \lfloor \frac{i}{n} \right \rfloor \right )$$

Where $i \mod n$ is the rest of the euclidean division of $i$ by $n$, and $A_m(n)$ is the $n$-th element of the set $A_m$.

$\endgroup$
2
  • $\begingroup$ It occurs to me that this is only valid for the union of disjoint sets. Will delete shortly, I can't on mobile $\endgroup$ Commented Mar 25, 2018 at 10:39
  • $\begingroup$ Did you forget to delete? $\endgroup$ Commented Nov 15, 2023 at 14:07
0
$\begingroup$

While an inductive approach can certainly work here, there is a more direct argument, outlined below:

Definition: A set $A$ is countable (either finite or countably infinite) if there exists an injective function $$\varphi : A \to \mathbb{N}. $$

For each $j \in \{1,2, \dotsc, n\}$, let $A_j$ be a countable set. Per the definition above, it is sufficient to show that there exists an injective function from $\bigcup_{j=1}^{n} A_j$ to $\mathbb{N}$. The intuition of the following approach is to first map the union into the disjoint union, then map the disjoint union into a disjoint union of copies of $\mathbb{N}$, and finish by mapping that into $\mathbb{N}$. One could do this all in one fell swoop, but I think that it is easier to see what is going on if the map is built up in pieces.

  1. Construct an injective function $\varphi_1$ from $\bigcup_{j=1}^{n} A_j$ to $\bigsqcup_{j=1}^{n} A_j$. That is, construct an injective function from the union of the sets to the disjoint union of the sets.

    Recall that $$\bigsqcup_{j=1}^{n} A_j = \{ (x,k) : x \in A_k \} \subseteq \left(\bigcup_{j=1}^{n} A_j\right) \times \{1,2,\dotsc,n\}. $$ That is, the disjoint union consists of order pairs, where the first term of each pair is an element $x$ of one of the $A_k$, and the second term of the ordered pair indicates which set $x$ belongs to. For example, $$ \{a,b,c\} \sqcup \{a,d\} = \{ (a,1), (b,1), (c,1), (a,2), (d,2) \}. $$

    An explicit function from the union to the disjoint union is given by $$ \varphi_1 : \bigcup_{j=1}^{n} A_j \to \bigsqcup_{j=1}^{n} A_j : x \mapsto \begin{cases} (x,1) & \text{if $x\in A_1$,} \\ (x,2) & \text{if $x\in A_2 \setminus A_1$,} \\ (x,3) & \text{if $x\in A_3 \setminus (A_1 \cup A_2)$,} \\ \dotso \\ (x,n) & \text{if $x \in A_n \setminus (A_1 \cup A_2 \cup \dotsb \cup A_{n-1})$.} \end{cases}$$ In other words, an element $x$ in the union gets sent to the ordered pair $(x,k)$, where $k$ is the smallest index such that $x \in A_k$.

    Exercise: verify that this function is injective.

  2. Construct an injective function $\varphi_2$ from $\bigsqcup_{j=1}^{n} A_j$ to $\bigsqcup_{j=1}^{n}\mathbb{N}$.

    For each $j$, the set $A_j$ is countable, so there is an injective function $\psi_j : A_j \to \mathbb{N}$. Define $$\varphi_2 : \bigsqcup_{j=1}^{n} A_j \to \bigsqcup_{j=1}^{n}\mathbb{N} : (x, k) \mapsto (\psi_k(x),k). $$

    Exercise: verify that this function is injective.

  3. Construct an injective function $\varphi_3$ from $\bigsqcup_{j=1}^{n} \mathbb{N}$ to $\mathbb{N}$.

    There are a lot of ways to do this, but a fairly straightforward approach is to define $$\varphi_{3} : \bigsqcup_{j=1}^{n} \mathbb{N} \to \mathbb{N} : (m,k) \mapsto nm + k.$$

    Exercise: verify that this function is injective.

It then follows that the function $$ \varphi = \varphi_3 \circ \varphi_2 \circ \varphi_1 : \bigcup_{j=1}^{n} A_j \to \mathbb{N}$$ is injective (the composition of injective functions is injective), hence $\varphi$ is the desired map.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .