Sincere request, don't forget to address my doubt at the end of the proof

I have assumed my sets to be disjoint at first but I have also addressed the general scenario as the proof progresses.

Set $A$ is said to be countable if there exists a bijection from $A$ to $\mathbb{N}$. Every countable set is infinite

To show that : Union of two countable sets is countable

Suppose $A$ and $B$ are countable. Assume at first that $A\cap B=\phi$

$A $ countable $\Rightarrow \exists f:A\to \mathbb{N} $ a bijection.

$B $ countable $\Rightarrow \exists g:B\to \mathbb{N} $ a bijection.

define. $h:A\cup B \to N$ as

$x\mapsto 2f(x) \; $ if $x\in A$

$x\mapsto 2g(x)+1$ if $x\in B$

Because $A\cup B$ is infinite, it is sufficient to show that $h$ is injective in order to show that $A\cup B$ is countable.

if $x=y$, where $x,y\in A\cup B$, since $A$ and $B$ are disjoint, so, either both $x$ and $y$ belong to $A$ or both belong to $B$, and because $f$ and $g$ are well defined, so is $h$

Now let $h(x)=h(y)$ where $x,y \in A\cup B$

again, $x$ and $y$ can both belong to $A$ or can both belong to $B$. Hence injectivity of $h$ on $A\cup B$ follows directly from the injectivity of $f$ and $g$ on $A$ and $B$ respectively

Hence, $A\cup B$ is countable.

Now, let $A$ and $B$ be arbitrary countable sets,

then by above method, $A\cup B = [A\setminus (A\cap B)]\cup[A\cap B]\cup [B\setminus (A\cap B)]$ is countable.

Doubt : Is it safe to assume $A\cap B = \phi$ in the beginning of the proof? I am doubtful here because $A$ and $B$ are countable. Please address this problem first

  • $\begingroup$ title says product but body says union !? $\endgroup$ – J. W. Tanner Sep 11 '19 at 21:40
  • $\begingroup$ I am sorry, edited $\endgroup$ – Abhay Sep 11 '19 at 21:41
  • $\begingroup$ If you are breaking into cases you do Case 1: $A$ and $B$ can do what ever you darned well want and Case 2: $A$ and $B$ don't do the stuff. So there is nothing wrong with saying Case 1: $A$ and $B$ are disjoint. Case 2: they are not disjoint. $\endgroup$ – fleablood Sep 11 '19 at 22:31
  • 1
    $\begingroup$ But how do you know $A\setminus (A\cap B), B \setminus (A\cap B)$ and $A \cap B$ are countable? And you defined countably infinite. What if some of these are finite? $\endgroup$ – fleablood Sep 11 '19 at 22:33
  • $\begingroup$ It is customary that "countable" means "finite or countably infinite" so that "uncountable" and "not countable" both mean "uncountably infinite". $\endgroup$ – DanielWainfleet Sep 12 '19 at 1:07

Your proof is just about fine. It's perfectly acceptable to start with the case $A \cap B = \emptyset$ as long as you later address the possibility that $A \cap B \neq \emptyset$, which you do.

The one quibble is that you only proved that the union of two disjoint countable sets is countable, yet the end of your proof requires you to use this result for the union of three disjoint countable sets. (I assume you've already separately proved that any subset of a countable set is countable, which is how you know that each of your three components really is countable.) It's a tiny step, but for completeness you probably should show why the result for a union of three (or any finite) number of disjoint sets follows immediately from the result for a union of two disjoint sets.

Edited to add: Tuvasbien is correct to note that the final step of your proof can be simplified. $A \cup B = A \cup (B \setminus A)$, and $A \cap (B \setminus A) = \emptyset$.


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.