1
$\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
    Mar 24, 2018 at 16:35
  • $\begingroup$ Yeah the exercise was concerning finite unions. Thank you very much. :) $\endgroup$
    – Adam
    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
    Mar 28, 2021 at 19:18
  • $\begingroup$ FYI : To obviate the need for worrying about set overlap - see this proof. $\endgroup$ Aug 3, 2021 at 13:10
  • $\begingroup$ @fleablood Unlike the proof for finite unions, the proof for countable unions needs (a weak form of) the axiom of choice. $\endgroup$ Jun 3 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$
1
  • $\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$ Mar 25, 2018 at 10:39
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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.