Proof of the union of two countable sets is countable I think I have got some clues for how to prove that for two disjoint countable sets, but I don't know how to deal with two ordinary countable sets. I would like to ask for some advice. Thanks. It also would be nice to have a rigorous proof.
 A: Nice problem. This problem lays the foundation for solving many problems, so I will write a very detailed solution.
Let's start with agreeing.

Definition 1: We say that the set $A$ has the same cardinality as set $B$ is there exists $f: A \to B$ that is one-to-one and onto. In this case, we write $A\sim B$.


Definition 2: We say that $A$ is countable if $\mathbb{N}\sim A$. An infinite set that is not countable is called an uncountable set.

For example, we can see that:

The set $\mathbb{Q}$ is countable but the set $\mathbb{R}$ is uncountable.

Your problem, we can write as:

Let $A$ and $B$ countable set. Prove that $A\cup B$ is countable.

Proof: By definition $\color{blue}{(2)}$, we need to show that $\mathbb{N}\sim A\cup B$, so by definition $\color{blue}{(1)}$ we need to prove that $\color{blue}{\text{there exists}}$ a function $f: \mathbb{N}\to A\cup B$ and that $f$ is a function $\color{blue}{\text{one-to-one}}$ and $\color{blue}{\text{onto}}$.

In mathematics it is important, as I have done above to write what you must proof in terms of the results you want to use. Now, let's go back to the hypotheses of the problem.

Since that $A$ is countable set, so $\color{blue}{\text{there exists}}$ a function $g: \mathbb{N}\to A$ such that $g$ is is a function $\color{blue}{\text{one-to-one}}$ and $\color{blue}{\text{onto}}$. Similar, since that $B$ is countable set, so $\color{blue}{\text{there exists}}$ a function $h: \mathbb{N}\to B$ such that $h$ is a function $\color{blue}{\text{one-to-one}}$ and $\color{blue}{\text{onto}}$.

Something common in mathematics is to try to use proofs of already proven theorems, as models to build new proofs. If you have ever proved that naturals are countable, then you will remember that something like "separate the odd and even numbers and then join them by a correspondence rule (a function)" was done.

Let, $$f: \mathbb{N}\to A\cup B$$
defined by $$f(x):=\left\{\begin{aligned}h\left( \frac{n}{2}\right), \quad \text{n is even}\\
g\left( \frac{n+1}{2}\right), \quad \text{n is odd} \end{aligned} \right.$$
It's clear that $f$ is a function $\color{blue}{\text{one-to-one}}$ and $\color{blue}{\text{onto}}$.

Now, it is time for you to work. You must prove that the function $f$ is really $\color{blue}{\text{one-to-one}}$ and $\color{blue}{\text{onto}}$.

