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 infinite 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.

Thanks in advance.

  • 2
    $\begingroup$ 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. $\endgroup$ – JMoravitz Mar 17 '19 at 15:50
  • $\begingroup$ 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. $\endgroup$ – jgon Mar 17 '19 at 15:53
  • $\begingroup$ 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? $\endgroup$ – emonHR Mar 17 '19 at 16:06
  • $\begingroup$ 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". $\endgroup$ – 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.

  • $\begingroup$ 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 $\endgroup$ – emonHR Mar 17 '19 at 16:41
  • 1
    $\begingroup$ Oops after a while accidentally again I read your answer and finally understood it.Thanks again for a nice intuitive answer $\endgroup$ – 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


also written


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.)


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.