Saturday, 28 May 2016

elementary set theory - Union of countable sets is countable.

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.



Proof. 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$.




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}$$
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. Thus, by induction, the statement holds for all $n\in\mathbb{N}.\qquad\square$

No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...