I need to prove that the union of two countable sets is countable. I have seen some solutions on this website and others, but they are all too complicated for my background. Could someone suggest a basic proof for this and explain the intuition?
[Math] Union of two countable sets
elementary-set-theory
Related Solutions
A formal proof would be something like this. If $A$ and $B$ are countable (and disjoint) sets, then there exist injective functions $f$ and $g$ from $A$ and $B$, respectively, to $\mathbb{N}$. Let $C=A\cup B$ and define a function $h:C\rightarrow\mathbb{N}$ as follows:
$$h(z) = \begin{cases}2f(z) & \text{if } z\in A\\ 2g(z)+1 & \text{if } z\in B\end{cases}$$
Then, if $x\neq y$, we clearly have $h(x)\neq h(y)$ since if $x,y\in A$ this follows from the fact that $f$ is injective (analogously for $x,y\in B$) and if $x\in A$ and $y\in B$, we have that $h(x)$ is even while $h(y)$ is odd (analogously for $x\in B$, $y\in A$). Hence $h$ is an injective function from $C$ to $\mathbb{N}$ and thus, by definition, $C$ is countable.
First of all, let me assure you there is no general "explicit" bijection. The reason is that the axiom of choice is needed to choose enumerations for each countable set (separately). In its absence, it is consistent that a countable union of countable sets can be uncountable (in fact, it could be equal to the real numbers!).
But suppose that we are given enumerated sets, namely $S_n$ and $f_n$ which is an injection from $S_n$ to $\Bbb N$. In this case we can explicitly define an bijection from $\bigcup S_n$ into $\Bbb N$.
But why? That would be working quite hard to make all the indices fall into place. Instead we want to use the following theorems:
- The product of two countable sets is countable. Therefore $\Bbb{N\times N}$ is countable.
- An infinite subset of a countable set is countable.
So it suffices to show that there is an injection into a countable set, and we're done.
We might want to say, map $s_{n,m}$ to the ordered pair $(n,f_n(s_{n,m}))$, which will be an injection from $\bigcup S_n$ into $\Bbb{N\times N}$. But what if the $S_n$'s are not pairwise disjoint? Then you might have an element mapped into two places at once.
To overcome this difficulty we can do one of two things:
Make then $S_n$'s disjoint, by considering, perhaps $S_n\times\{x_n\}$, where $x_n$ is a set which will guarantee that these are disjoint. We can prove that such $x_n$'s exist. Or perhaps by redefining $S_n'=S_n\setminus\bigcup_{k<n}S_k$, which will remove the duplicates and perhaps empty out a few of the sets. Either option works.
Just do the second option implicitly, by mapping $s_{n,m}$ to $(n,f_n(s_{n,m}))$ if $n$ is the smallest number such that $s_{n,m}\in S_n$.
In either case, this makes the above injection into $\Bbb{N\times N}$ well-defined. So now either that $\bigcup S_n$ is finite or has a bijection with an infinite subset of a countable set, so it is countable.
Best Answer
I think a basic proof would show that the odd and even numbers are countable, and then map the odd numbers onto one set in the union, and the even numbers onto the other set (you get a map from the odds/evens to the naturals, then you compose with the map sending the naturals to one of the sets in the union). This is sort of just saying that if you have an infinite thing you can divide it into subsets that are the same size as it (the definition of being infinite). You would have to handle the special case where the two sets share all but finitely many points with this proof, but that should be easy.