# Union of two countable set is also countable

This question is asked many time when I search it. But i didn't find what am I really looking for.

My approach:

Let $$A_1,A_2$$ be two countable sets. If they have some common elements then redefine it by $$B_2=A_1\setminus A_2=\{x\in A_2:x\notin A_1 \}$$. The point of this is that the union $$A_1 \cup A_2=A_1 \cup B_2$$ and the sets $$A_1,B_2$$ are disjoint. I guess three case be happen for $$B_2:$$

1. If $$B_2=\emptyset$$, then $$A_1\cup A_2=A_1 \cup B_2=A_1$$ which we already know to be countable.
2. If $$B_2=\{b_1,b_2,\cdots,b_m \}$$ has $$m$$ elements, then how can I define and make sure $$h:A_1 \cup B_2\to \mathbb{N}?$$ In order to satisfy the statement $$A$$ is countable iff there is a bijective $$(1-1$$ and onto$$)$$ mapping $$f: A \to \mathbb{N}$$, where $$\mathbb{N}$$ is the set of all natural numbers.
3. If $$B_2$$ is inﬁnite again the same problem faced.

I have no idea how to approach and fix all these things. Besides, I wanted to know Is this approach is enough to proof the statement or not? Any hint or solution will be appreciated.

• You started well by splitting the sets into two disjoint sets and this is often forgotten by new students. Now, to continue, you can think of a bijection to a subset of the natural numbers as a sequence (because that is how a sequence is actually defined). Now... to write the sequence with all elements of your two sets, if $B$ is finite, just write all of them out at the front of the sequence and then write out the elements of $A_1$ after that. If they are both infinite, then just alternate $b_1,a_1,b_2,a_2,b_3,a_3,\dots$. Now, just make those ideas rigorous. – JMoravitz Mar 17 '19 at 15:50
• I've fixed your formatting. A couple main pieces of advice. Firstly, in English, we put spaces after punctuation that precedes another word. I.e., instead of "[...] when I search it.But I [...]" use "[...] when I search it. But I [...]". Secondly, paragraph breaks and proper numbered lists greatly improve readability. Other than that, generally speaking a pretty good question, and I appreciate the use of LaTeX. – jgon Mar 17 '19 at 15:53
• Thanks @JMoravitz sir for your great advise.I guess you tell me $$h(n) = \begin{cases} b_n,n\le m \\ a_n\in A_1, n\gt m \end{cases}$$ but I can't think what have to do when they are both infinite? – emonHR Mar 17 '19 at 16:06
• Terminology: "Countable" means "finite or countably infinite". That is, $X$ is countable iff there exists an injective $f:X\to \Bbb N$. So that "uncountable" means "not countable". – DanielWainfleet Mar 18 '19 at 6:08

I would proceed like this:

1. We know that there is a bijection between $$A_1$$ and $$\Bbb{N}$$ and $$A_2$$ and $$\Bbb{N}$$. Let's call them $$f_1: A_1 \longrightarrow \Bbb{N}$$ and $$f_2: A_2 \longrightarrow \Bbb{N}$$.

2. We need to prove that there is $$g: B \longrightarrow \Bbb{N}$$ bijective ($$B = A_1 \cup A_2$$), or equivalently, a $$g': \Bbb{N} \longrightarrow B$$.

So define $$g'$$ as follows: $$g'(n) = \begin{cases} f_1^{-1}(n), & \text{if n is even} \\ f_2^{-1}(n), & \text{if n is odd} \end{cases}$$

Note that $$f_1$$ and $$f_2$$ are invertible because they are bijective. Now take $$g = g'^{-1}$$ and you have what you were looking for.

Note: a way to visualize it is to consider the following two sets: $$A = \{(+, n) : n \in \Bbb{N}\}, B = \{(-, n) : n \in \Bbb{N}\}$$ which union gives $$\Bbb{Z} \setminus {0}$$ and notice that $$h$$ defined as $$h(n) = \begin{cases} (+, n/2), & \text{if n is even} \\ (-, (n+1)/2), & \text{if n is odd} \end {cases}$$ is a bijection between $$A \cup B$$ and $$\Bbb{Z} \setminus {0}$$. And you know that $$\Bbb{Z} \setminus {0}$$ is countable.

Here is hint to show the way when taking the union of two disjoint, countably infinite sets; it examines a concrete example. But the constructions/mechanics of this example can be used to prove the OP's case 3 (infinite/infinite).

Let $$A = \{\, (m, 0) \, | \, m \in \mathbb N \, \}$$ and $$B = \{\, (m, 1) \, | \, m \in \mathbb N \, \}$$. Since both of these sets are subsets of $$\mathbb N \times \mathbb N$$, we can apply the functions $$\pi_1$$ and $$\pi_2$$, the projections onto the first and second coordinate:

$$\quad \pi_1: \mathbb N \times \mathbb N \to \mathbb N, \; \text{ with } \pi_1\left( (x,y) \right) = x$$

$$\quad \pi_2: \mathbb N \times \mathbb N \to \mathbb N, \; \text{ with } \pi_2\left( (x,y) \right) = y$$

For any $$z \in A \cup B$$, define

$$\tag 1 F(z) = 2 \, \pi_1(z) + \pi_2(z)$$

It is easy to demonstrate that $$F: A \cup B \to \mathbb N$$ is a bijection, sending the set $$A$$ to the even integers and $$B$$ to the odd integers.

• Thanks @CopyPasteIt sir but i can't get what you mean by "the projections onto the first and second coordinate" and Why $2 \, \pi_1(z) + \pi_2(z) \equiv \mathbb N$.It will teach me a totally new thing thanks again – emonHR Mar 17 '19 at 16:41
• Oops after a while accidentally again I read your answer and finally understood it.Thanks again for a nice intuitive answer – emonHR Apr 3 '19 at 14:04

Numberphile has a video on this:

summary is:

• first case is fine
• your second case, can be done by mapping the previous cases up m.
• your third case, can be done by noting both evens and odds are countably infinite sets, map n to 2n and place the rest in 2n-1

Sets are countable if you can enumerate the elements ($$=$$ assign an index to each), without omission.

Let $$C:=A\cup B$$. From the enumerations

$$a_1,a_2,a_3,\cdots$$ and $$b_1,b_2,b_3,\cdots,$$

we form the enumeration

$$a_1,b_1,a_2,b_2,a_3,b_3,\cdots$$

also written

$$c_1,c_2,c_3,c_4,c_5,c_6,\cdots$$

In other terms, the elements of $$A$$ get the odd indexes and those of $$B$$ the even ones. You can check that this is an enumeration without omission.

If $$A$$ and $$B$$ have common elements, they will be cited twice. But this doesn't matter. (If you want, you can just skip the duplicates, but it is not even required.)